Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

On the Fly Authenti ation and Signature

De
28 pages
On the Fly Authenti ation and Signature S hemes based on Groups of Unknown Order Mar Girault 1 , Guillaume Poupard 2 , and Ja ques Stern 3 1 Fran e Tele om Resear h & Development, 42 rue des Coutures BP 6243, F-14066 Caen Cedex 4, Fran e mar .giraultfran etele om. om 2 DCSSI Crypto Lab, 51 boulevard de La Tour-Maubourg F-75700 Paris 07 SP, Fran e Guillaume.Poupardm4x.org 3 É ole normale supérieure, Département d'informatique 45 rue d'Ulm, F-75230 Paris Cedex 05, Fran e Ja ques.Sternens.fr Abstra t. In response to the urrent need for fast, se ure and heap publi -key ryp- tography, we propose an intera tive zero-knowledge identi ation s heme and a derived signature s heme that ombine provable se urity based on the problem of omputing dis rete logarithms in any group, short keys, very short transmission and minimal on- line omputation. This leads to both e ient and se ure appli ations well suited to implementation on low ost smart ards. We introdu e GPS, a S hnorr-like s heme that does not require knowledge of the order of the group nor of the group element.

  • heap publi -key

  • identi ation

  • ation time

  • appli ations

  • zero-knowledge

  • signature

  • international organization

  • ele tromagneti indu


Voir plus Voir moins


On
strong
the
smart
Fly
Sev
Authen


heme,
and
authen
Signature
b
Sc
pro
hemes
a
based
less
on
In
Groups
tialit
of
v
Unkno
man
wn

Order
v
Marc
the
Girault
ossible
1
an
,
authen
Guillaume
equipmen
P
on-line
oupard
elopmen
2
heap
,
e
and
in

w
Stern
those
3
of
1
o
F
prop
rance
of
T

elecom
y

heme.
h
of
&
rameters
Dev
the
elopmen
on
t,
a
42
e
rue
with
des
ords.
Coutures
logarithm
BP

6243,
rapid
F-14066

Caen
fast,
Cedex
y
4,
tographers
F
imp
rance
viding

ho
2
tit
DCSSI
a
Crypto
ha
Lab,
ard
51
based
b
tro
oulev

ard
to
de
sc
La
e
T
ortan
our-Maub
.
ourg
limited
F-75700
pap
P

aris
ofs
07
tication
SP
rom
,
oin
F
the
rance
of
Guillaume.Poupard@m4x.org
discussed
3
ort
?cole

normale
implemen
sup?rieure,

D?partemen
is
t
and
d'informatique

45
erformed
rue
20
d'Ulm,
w
F-75230
Key
P
tication
aris
signature,
Cedex
min-
05,
lo
F

rance


orld-wide

of
In
ulates
resp
mand
onse
and
to
ey
the
Besides

,
t
to
need
w
for
t
fast,
and

signatures
and
w

to
heap
one's
public-k
and
ey
digitally


tograph
prop
y
e
,
putting
w
t
e
of
prop
the
ose
wledge
an
in
in
Goldw


e
In
zero-kno
the
wledge
prop
iden
three
tication
ha
sc
b
heme
most
and

a

deriv
viously
ed
ery
signature

sc
This
heme
er
that
vides


bine
pro
pro
of
v
iden
able
sc

F
y
a
based
p
on
t
the
view,
problem
p
of
range

pa-
discrete
is
logarithms
and
in
rep
an
on
y
p
group,
of
short
actual
k
tation
eys,
a
v
heap
ery

short

transmission

and

minimal

on-
b
line
p

in
This
than
leads
milliseconds
to
lo
b

oth
t.

w
t
Iden
and
sc

digital
applications
discrete
w
problem,
ell
imal
suited

to
w
implemen
smart
tation
1
on
tro
lo
The
w
w

dev
smart
t

electronic
W
stim
e
a
in
de-
tro
for


GPS,

a
public-k
Sc

hnorr-lik
.
e

sc
y
heme

that
need
do
solv
es
t
not
o
require
ortan
kno
problems:
wledge

of
pro
the
digital
order
or,
of
plain
the
ords,
group
w
nor
pro
of
e
the
iden
group
y
elemen
ho
t.
to
As
sign
a
do

t.
it
eral

osals
b
v
e
addressed
used
questions,
with
forw
most
elegan

solutions,
group
y

them

on
those

of
zero-kno
unkno
in
wn

order.
1985
F
y
urthermore,
asser,
the
and

k
of
[30].
the
order
pro
assess
v
p
er's
of
resp
osed
onse
hemes,
is
main
done
erties
o
v
v
to
er
e
the
The
in
imp
tegers,
t
hence
is,


b
y
e
Ob
done
,
witha
a
authen
system
on

for
b
the
e
e
supp
to
orted
Ev
b
study
y
implemen
the
tenna.

stored
that
y
nob
signature
o
mo
dy
describ
has
impro
b
a
een
and
able

to
they
jeopardize
unit
it
that
so
v
far.
is
This
used.
is
ons
of
t.

is
imp
m
ortan
osed
t
signature
but,
b
in
auman
man
tication
y
bine
applications,
arbitrary
it

is
tication
not
the
a
just
satisfactory

enough

guaran
Con
tee.
et
A
p
m
and
uc
e
h

b
ottlenec
etter
when
paradigm
al.
tries
thr
to
mak
pro
uc
v
er
e
y

it
y
Another
in
general
a
and
mathematical
on-line/o-line
sense,
to
i.e.

to
of
establish
This
theorems
y

pap
that
e
illegal
GPS
actions
sc


h
o
as
k
imp
minimal
ersonation
GPS
are
sig-
as
lo
dicult
Another
as

solving

a
e
sp
an

em
problem,
ts
whose
with
dicult
ph
y
the
is
distinguish
w
een
ell-established.
b
Among
o-line
these
memory
problems
that
are
to
in
on-line
teger
or

The
or
the
the
of

esp
of

discrete
he
logarithms
prop
in
use
a

nite
order
group.
the
Half

w
more
a
w
y
at-
b
on
et
sc
w
optimal
een
requires

m
v
h
alidation
h
and

formal
Goldreic
pro
[15]
ofs

are
signature
pro
a
ofs
an
in
heme
a
a
mo
that
del

where
done

as
ob
ed

and
are
In
replaced
w
b
in
y
wledge
some
heme,
ideal
short,
substitutes:
ed
applying
They
this
v
paradigm
based
to
logarithm
hash
er
functions
group,
yields
short
the
size
so-called

random
signature
oracle
ws
mo
public-k
del
or
describ
hemes
ed

b

y
application
Bellare
tation
and
sc
Roga

w
h
a
ok
y

in
v

mi-
Although
and
this
edded


h
w
ma

y
an
not
an
b

e


v
as
to
oering
b
absolute
w
pro
precomputations
ofs

of
e

erformed
y
and
for
in

,
sc

hemes,
ha
it
e
pro
b
vides
done
a
during
strong

guaran
signature
tee
tation.
that
latter
their
often
general
b
design
k
is
man
not
applications,
a
ecially
w
smart
ed.
are
Next,

the
et
size
[34]
of
osed
the
precompute
data
&
in
ow
v
oup
olv
in
ed
to
in
e
the
DSA
sc
pro
heme
m
is
h
of


Ho

ev

this
W
tempt
e
designing
usually
the
need
signature
short
hemes
public
not
and
since
priv
still
ate
a
k
dular
eys,
ultiplication.
mainly

when
is
they
uc
ha
more
v
in
e

to
en,
b
h
e

stored
prop
in
the
p
of
ortable
digital

and
lik
ed
e


transform
hip
y

sc
whic
in
h
h
ma
w
y
y
ha
most
v
the
e

small
e
storage
o-line.

w
W
further
e
v
also
b
w
Shamir
an
T
t
[44].
to
this

er,
the
e
amoun
an
t

of
zero-kno
transmissions
iden
and
sc
the

length
for
of
and
the
deriv
signatures.
signature
The
heme.
latter

is
pro
an
able
imp
y
ortan
on
t
discrete
parameter
problem
in
v
applications
an
for
nite
whic
short
h
eys,
man
transmissions
y
signature
signatures
and
ha
on-line
v
The
e
on-based
to
algorithm
b
allo
e
to
stored
t
(e.g.
ey
electronic
nature

iden
or
sc
transmitted
on
(e.g.
w
pa
smart
y
without
TV).

Another
promising
k
is
ey
implemen
prop
of
ert
h
y
hemes
is

the
smart
time



y
lo
,
lik
since

it
but

ha

e
trols
electronic
the


hip
of
an
the
b

an
on
These
whic
onen
h
allo
a
the
sc
to
heme
unicate
ma
an
y

b
without
e
y
implemen
ysical
ted.

Here,

w
are
e
2
haapplications.
ideal
only
solution
in
when
heme

and
m
hnical
ust
b
b
P
e
and
pro
discrete

app
v

ery
GPS
quic
mo
kly
h-
,
es
as
of
in
heme.
mass-transit
pro
or
the
toll
Then,

at
but,
mo
since
v
the
discrete
p
the
o
a
w
[26].
er
(In
supply
heme

w
from
erties

the

describ
hea
b
vy-consumption
our

the

activ
hardly
is

sc
b
design.
e
of
used.
preliminary
A
[40].
t
more
ypical

application
y
of
streamlined
GPS
tractabilit
is
exp
on
b
the
pro
y
this
authen
e

are
at
GPS
a
standardized
toll.
Standardization/
The
while

at
idea
In
is
that
to
of
equip
demand

w
h
heme
authorized
ts.

iden
with
ho
a
to
lo
w
w
del

the

sc

GPS
smart
pro

exp
When
4,
a
the

random
go
alidate
es
is
through
main
a
pap
toll,
in
it
er-
do

es
main
not
are
ha

v
and
e
of
to
.
stop
hnicalities
but
b
just
w
p
the
erforms
of
a
with
GPS
ts.
authen
heme

submitted
in
ean
order
and
to
b
pro

v

e
V
that
of
it
ed
is
,
a
tication
legitimate
b
user.
y
In
Organization

ternational
h
Commission)
an
signature
application,

the
earlier
time
er
allo
pap
w
sho
ed
ac
to

transmit
strongest
data
one
and
authen
to

p
rst
erform
hnorr
on-line
sev

v
is
w
v
the
ery
sc
short,
e
ab
it
out
turned
100
signature
milliseconds.

The
dev
main
y
feature
iden
of
e
GPS
y
is
iden
to
W
use
e
public

k
adv
ey
the

with
y
ts
in
In
this
e
setting
y
(v
ed
ery
using
short
mo
authen
to

prop
time
last
and

lo
the
w
results

this

er
th
eared
us
a
ac
v
hieving
sion
a
Euro
high
'98
lev
The
el

of
dierences

a
y
precise
.
y
F
del
urthermore,
a
in
pro

of
h
y
an
Man
indep

enden
ha
t
e
application
een
that
and
do
e
es
assume
not
in
require
y
in

terop
logarithms
erabilit
short
y
onen
with
The
other
sc
systems,
has
the
een

to
ons
Europ

NESSIE
b

e
la-

elled
and
y
stored
pro
in
as
the
strong

primitiv
b
[12].
y
arious
the
des
authorit
use
y
describ
who
in
also
Finally
acts
the
as
iden
a
sc
v
has
erier.
een

b
that
ISO/IEC

ternational

for
y
In

Electrotec
also

b
[32],
e
the
used
sc
to
is
solv
tly
e
an
this
stage.
problem
ap

organization.
tly
this
.
er,
But
e
the
w
adv
GPS
an
hiev
tage
a
of
bination
using
the
public
prop
k
that
ey


in
y

is
In
that
2
no
e


master
Sc
k
sc
ey
and
has
eral
to
its
b
arian
e
Then
stored
e
b
e
y
GPS
the
tication
v
heme
erier
w
(here

the
w
toll).

Consequen
e
tly
in
,
a
the
sc
system
In
is
3,
m
e
uc
elop
h

more
mo

for
against
tication,

w
.
study
Earlier


of
ts.
GPS
The
tication
GPS
heme.
sc
e
heme
v
w
that
as
is
rst
against
prop
e
osed
ersaries
b
vided
y
so-called
Girault
logarithm
at
short
Euro-
onen

problem
'91
hard.
[22]

as
w
an
establish
example

of
of
a
deriv
sc
signature
heme
heme
with
the
self-c
oracle
ertie
del
d
order
public
v
k
the
eys
osed
but
The
without


more
y
3
analysis.greater
in
and

of

v
w
in
e
order
discuss
;
ho
b
w
erier
to
e

of
ho
of
ose
who

v
parameters
p
in
the
order
the
to
b
resist

the
a
kno
in
wn
the

In
ks
generates
against
r


and
publicly
the
mo
discrete
x
logarithm
e
problem.
of
Then
v
w
w
e
sound.
explain
out
ho
e,
w
to
to
the
optimize
een
size
prime
of
the
the
ma
data
also
and,
order
nally
mo
,
v
rep
pro
ort

on
t
the
to
p


in
of
where
a
parameter.
smart
=

sends
application.

2
I
Description
tary
of
tially;
GPS
n
2.1

Iden
ws
tication
probabilit
sc
`
hemes
of
based
the
on
en
the
y
discrete
er
logarithm

problem
`
In
parameter,
1989,
pro
C.
y
Sc
heme,
hnorr
ha
[42]
,
prop
dulus
osed
k
a


m
pro

of
F
of
wn
kno
or
wledge
heme,
of
the
a
are
discrete
p
logarithm
to
in
kno
groups
,
of
er
kno
2
wn
at
prime
the
order.
=
This
d
pro
v
of
ers
is

a
in
more
al

1]
t
is
v
wn
ersion
the
of

previous
+
prop
q
osals
to
of
who
Chaum
the
et
g
al.
mo
[11,
This


and
eated
Beth
e

`

b
h
etitions.
a
analysis
pro
heme
of
a


b
substan
e
1
used
ust
as
discrete
an
,
iden-
s
tication
of
sc
urthermore,
heme,
dishonest
and
learn
also
information


v
n
erted
of
in
y
to
B
a
p
signature

sc
asymptotically
heme
large;
using
is
the
wledge.
Fiat-Shamir
dications
paradigm
hnorr
[18].
ac
In
prop
these
e
sc
osed.
hemes,

the
osite
size
of
of
dulus
the
the
data
mo
is
a
short,
of
and
e
the
h

p
load
remain
is
the
quite
publicly

g
T
e
o
ate.
w
hnorr
ards
oth
a
1
more
and
precise
of
description,
1
w
d
e
.
let
order
p
pro
b
e
e
wledge
a
s
prime
the
n
v
um
rst
b
r
er.
Z
W
q
e
random
denote
sends
b

y
x
Z
g

mo
p
p
the
the
set
erier
of
answ
in
a
v
hallenge
ertible
randomly
elemen
hosen
ts
the
mo
terv
dulo
[0
p
B
.
,
Let
B
q
a
b
kno
e
system
a
Next,
large
pro
prime
er
divisor
y
of
r
p
sc
1
d
and
and
g
y
an
the
elemen
erier
t

of
ks
Z
equation

=
p
y
of

order
d
q
.
,
elemen
i.e.
round

b
h
rep
that
sequen
g
w
q
denote
=
y
1
the
mo
um
d
er
p
rep
but
The
g
y
6
of
=
sc
1
sho
.
that
The
pro
pro
er
v
with
er
y
kno
tially
ws
than
a
=B

m
elemen
kno
t
the
s
logarithm
in
I
Z
i.e.
q

and
;
he
pro
w
is
an
F
ts
ev
to
a
pro
v
v

e
an
that
additional
he
ab
kno
the
ws
whatev
the
the
discrete
um
logarithm
er
of
authen
I
ma
=
b
g
if
s
and
mo
are
d
olynomial
p
a
in
y
base
i.e.
g
not
.
o
W
the
e
of
rst
p

zero-kno
that
Man
an
mo
y
of
v
Sc
erier
sc

that
immediately
hiev

additional

erties,
k
v
that
b
p
prop
is
Firstly
prime,
one
q
use
is

a
mo
prime
instead
divisor
a
of
mo
p
and
1
eep
,

g
the
is
dulus
of
As
order

q
order
and
the
that
ultiplicativ
I
group
b
whic
elongs
the
to
are
the
erformed
subgroup
y
of

Z
urthermore,

order
p
the
generated
kno
b
base
y

g
b
.
public
This
priv
last
In
v
Sc

sc
just
b

the
in
p

of

group
king
the
that
q
I
g
q
4
=um
kno
is
wn.

W
In
e
tication
will
h
see
is
that
wn
in
to
the
remark
GPS
e
sc
While
heme,
of
b
(note
oth
prime
of
divisible
those

parameters
out

observ
remain
solution
unkno
1
wn
(
to
g
pro
en
v
pro
ers
dulo
and
adv
v

eriers.
the
Other
of
sc

hemes,
w

heme
in
q
gure
in
1,
of
ac
adv
hiev

e
GPS
dieren
y
t
w

and
binations.
of
W
s
e
g
no
mo
w
is
briey
zero-kno
review
[17].
those
of
proto
base

tractable,
Order

of
for
the
GPS,
m
k
ultiplicativ
prop
e
done
group
er
kno
g
wn
,
unkno
that
wn
pro
Order
o
of
rest
g
the
kno
base
wn
er
Chaum,
mo
Ev
rev
ertse,
main
v
t
an
passiv
de
who
Graaf
regular
and
the
P
to
eralta
heme.
[11,
osed

amoto
Beth
using

bases
Sc
g
hnorr
pro
[42],
kno
Ok
represen
amoto
1
[36]
)
Girault
I
[21],
1
Biham
2
and
p
Sh
proto
ulman
pro

b
Order
it
of
indistin-
g
a
unkno
the
wn
discrete
Bric
1
k
2
ell
is
and
sc
McCurley
v

activ
GPS
ev
[22,


so
RDSA
explained

The
P
sc
oupard
proto
and
in
Stern
are
[41]
dulo
Fig.
um
1.
but
Discrete
a
logarithm
publicly
related
order
sc
parameters
hemes


1

y
to
q
the
t
need
prime
for
ers.
the
the
order
similar
of
hnorr
the
uses
group
of
and/or
the
of
is
the
+
base
p
g
not
to
information
b
.
e
an
kno
v
wn
to
b
against
y
e
pro
ersaries
v
just
ers
e
and
authen
v
Exactly
eriers
same
The
applies
Ok
the
amoto
sc
sc
A
heme.
prop
The
b
Sc
Ok
hnorr
[36]
sc
in
heme
t
is
o
kno
g
wn
and
to
2
b
to
e
v
p
the

wledge
zero-kno
a
wledge
tation
if
s
the
;
parameters
2
B

and
that
`
=
remain
s
p
1
olynomial
s
in
2
a
d

.
y
this
parameter.

The
not
one-round
v
(
to
`
e
=
wledge,
1
nonetheless
)
witness
v
guishable
arian
As
t

remains
vided
sound

if
the
B
logarithm
is
g
sup
in
er-p
g
olynomial,
mo
but,
p
as
in
a
the

heme
this
pro
v
ably
arian
against
t
e
is
ersaries,
p
en

large
zero-kno
hallenges
wledge
that
only
is
w.r.t
as
a
in
honest
3).
v
Bric
erier,
ell-McCurley
i.e.
heme.
a
the
v

erier
osed
who

ran-

domly
still

mo
ho
a
oses
n
the
b

p
hallenges.
instead
Ho
using
w
base
ev
of
er
kno
it
prime
is
q
unkno
the
wn
are
ho
hosen
w
h
to
p
pro
is
v
b
e
the
the

zero-kno

wledge
of
prop
w
ert

y
n
if
b
the
The
v
of
erier
sc

is
bias
to
the
Sc
distribution
proto
of
it
his
a

g
hallenges.
order
This
but
means
answ
that,
y
for
equal
large
r

sc
hallenges,
d
w
1
e
order

to
only
eal
pro
ab
v
q
e
The
the
adv

tage
y
this
of
arian
Sc
is
hnorr
5
idensc
base
Other
the
y

order
y
of
on
sub
the
ed
in
osed,
tractabilit
and
y
sc
of
y
the
[24],
discrete
in
logarithm

problem
the
mo
GPS
dulo
underlying
p

or
ts
on
q
the
This

analysis
of
in
p
a
1
GPS,
.

This
tractabilit
means
of
that
the
it
another
is
is

w
if
ears
at
heme
least
the
one
w
of
,
those
where
t
the
w
erforming
o
sc
problems
een
is
and
dicult.

The
presen
Girault
setting.
sc
eration
heme.
uc
The
v
idea
b
of
in
[21]
the
is
based
to


as
ho
discrete
ose
and
a
o

More
osite
has
mo
the
dulus
ey
n
heme
=
the
(2
y
f

p
GPS
+
a
1)


G
(2
of
f
the
q
in
+
,
1)
[0
where
public
2
to
f
mo
p
y
+
op
1
r
,
Z
2
rst
f
osed
q
in
+

1
this
,
precisely
p
of
,
pap
q
more
and
that
f
on-line
are

prime.
but
The
longer,
in
hemes.
teger
t
f
RDSA,
is
prop
public,
and
the
W
base
note
g
heme
has
[41]
order
the
f
of
and
but
the
e
answ
pro
er
wledge
y
where
is
the

order
mo
are
dulo
b
f
v
.
tly
A
sc
public
een
k
whic
ey
ey
of
RSA
a
[25].
pro
tication
v
e
er
e
of
iden
iden
The
tit
ap-
y
the
Id
of
is

obtained
tication
with
dened
the
group
form
a
ula
t,
I
g
=
In
Id
y
1
next
=e
only
g
tractabilit
s
discrete
mo
group
d
base
n
exp
where
the
the
S
e
is
-th
of
ro
6
ot
eliminate
of

Id
dulus
is
b

p
b
the
y
erations
an
=
authorit
+
y
in
who
.
kno
has
ws
b
the
prop

b
of
Girault
n
[22]
and
the
s
y
is
of
a
proto

is
k
the
ey


the
hosen
t
b
er
y
a
the
general
pro
Note
v
in
er.
the
In
op
this
is
setting,
to
an
single,
iden
m
tication,
h
in
addition.
spirit,
sc
is
A
a
arian
Sc
of
hnorr

pro
has
of
een
of
osed
kno

wledge
analyzed
of
[19].
the
e
discrete
also
logarithm
that
(
sc
e
describ

in
s
is
)
on
of
in
I
y
e
the
=
problem,
Id
it
mo
b
d
seen
n
a
in
of
base
kno
g
of
.
logarithm
The
the
GPS
of
sc
group
heme.
the
A
of
w
base
a

y
wned
of
y
impro
pro
ving
er.
the

Sc
,
hnorr

proto
heme

b

prop
is
in
to
h
get
k
rid
pair
of
a
mo
k
dular
pair

2.2
during
iden
iden
sc
tication
W
or
no
signature.
describ
Exp
precisely
onen
GPS
tiation
tication
mo
heme.
dulo

p
analysis

p
b
in
e
next
p

erformed
the
o-line
mathematical
b
The
y
iden
the
sc
user's
is

on
or

precomputed
G
b
uses
y
sp
an
elemen
authorit
namely
y
base
in
2
a
.
use
the
&

thr
analysis
ow
the


oup
e
ons
assume
[34]
in-
setting.
y
Therefore,

in
logarithms
order
the
to
G
further
in

g
the
for
on-line
onen

in
to
range
a
;
v
1]
ery
S
simple
a
op
parameter
eration,
the
it
heme.
is
naturalin
More
problem
precisely
,
,
b
w
1]
e
[13].
assume
eys,
the
meaning
existence
the
of
=
a

randomized
strain
algorithm
in
P
elemen
P
W
(
the
!

pp
priv
;
the
k
v
)

that
a
generates

public
the
parameters

G
er
and
are
g
teger

een
to
these
a
imp

in
y
in
parameter
larger
k
mask
using

a
are
random

tap
round
e
in
!
ed
pp
GPS
.
b
In
manner;

more
sev
used;
eral
in
mathematical
short

groups.

h
b
parameters.
e
for
used;
the
the
b
most
t
in
and
teresting
relations

analyzed
hoices
some
for
to
G
the
are
=B
listed
logarithms
b
m
elo
onen
w:
;

b
G
B
=
random
Z
ate

s
p
range
with
public
p
group
a
g
prime
W
n
S
um

b

er
[0
s.t.
e
p
an
1
Analogs
has
the
a
setting
large
dened
prime
tforw

for
q

;
mathematical
the
b
order
only
of
is
the
y
base
logarithm
g
onen
should

b
example
e
an
q
prop
.
Other
W
the
e
ound
obtain

a
parameters
v
sc
arian
n
t
`
of
rounds
the
o
Sc
ounds
hnorr
,
iden
w.
tication
et
sc
parameters
heme

in
just
whic
ab
h
in
on-line
e

explicit:
is
y
t
is

,
as
of
fast
base
for
group
the
b
same
for

in
y
al
.
1]

m
the

set
S
G
it
=
of
Z
used


n
eys.
of
k
in
in
v
in
ertible
;
elemen
the
ts
eys
mo
in
dulo
b
an
I
RSA
.
mo
gure
dulus
let
n
B
,
.
i.e.
iden
a
the

in
osite
osing
in
r
teger
A
with

t
deriv
ypically
from
t
elliptic
w
e.
o
of
prime
in

elliptic
of
e
almost

the
e
same
in
size.
straigh
Note
ard
that
see
the
example


of
h
n

are

no
also
longer
e
required
the
so

they
t

the
b
tractabilit
e
of
discarded
discrete
after
with
the
exp
generation
t
of
is
n
h
.
An
Then
of
g
h


b
is
e
osed
randomly


public
hosen.
Besides
Ho
upp
w
b
ev
S
er,
the
the
k
generation
additional
of
of
n
GPS
and
heme
g
the
m
um
ust
er
b
of
e
tary
done
and
b
w
y
in
a
b
trusted
A
part
B
y
dened
since
elo
the
The

b
of
w
short
those
exp
are
onen
in
ts,
3.
t
e
ypically
summarize
of

160
out
bits,
parameters

order
b
mak
e
their
done
more
v

ery
probabilit
easily
of
using
ersonation
partial
1
P
`
ohlig-Hellman



hniques
discrete
[45]
in
if
g
the
the
order
G
of
ust
g
e
is
tractable
kno
exp
wn
ts
and
the
if
terv
it
[0
has
S
man
,
y
A
small
ust
prime
e

tly
In
than


w
since
e
denes
advise
size
the
some
use
data
of
to
mo
the
dulus
Public/priv
n
k
whic
The
h
ate
is
eys
the
are
pro
tegers

hosen
of
the
t
[0
w
S
o
and
strong
related
primes,
k
i.e.
I
primes

p
the
s.t.
G
(
y
p
relation
1)
=
=
s
2
Proto
is
(see
also
2).
prime.
e
W

e
(
also
1)(
advise
1)
the
A
use
of
of
tication
the
for
base
pro
g
er
=
randomly
2
ho
for
an

teger
reasons.
in

;
G
1]

and
also
7
bB
the
man

and/or
ommitment
and
x
sc
=
heme
g
B
r
ma
.
;
Next,
arian
he
the
sends
prop
x
erier
to
a
the
=
v
equations
erier,
x
who
S
answ
sc
ers
as
a
with

W
lenge
y

and
randomly
longer

hash
hosen
the
in
a
[0
=
;
the
B
b
1]
,
.
g
The
and
pro
B
v
2.
er
in

straigh

e
ks
I


2
on
[0
GPS
;
the
B
signature
1]

and
Fiat

Sc
the
hallenges
in
b
teger
y
y
output
=
B
r
heme.
+


[0

g
s
x
.
.
He

sends

y
o
to
(
the
;
v
S
erier

who
I

2

+
ks

g
1]
y
iden
=
As
x
kind

man
I
ard


and

y
ho
2
g
[0
=
;
s
A
trivial
+
rest


1]
sc
.

A
tication

to
iden
heme
tication
wing

nique
in
b
rep
Shamir
eating
b
`
[42]
times
others:
the
are
elemen

tary
a
round.

The
of

h
analysis
[0
sho
,
ws
than
that
tication
`
signature
should
m
b
y
e
r
sup
A
er-logarithmic
x
in
,
the
(

and
y
+
parameter
pro
in
(
order
)
to
b
b
k
e
an
able
using
to
=
pro
x
v
2
e
+
the


1]
y
=
of
8
the

sc

heme
y
against
[0
activ
A
e
(
adv
1)
ersaries,
(
as
1)
in
Fig.
the
GPS
Sc
tication
hnorr
heme
sc
usual
heme.
this
Ho
of
w
heme,
ev
y
er,
tforw
in
v
man
ts
y
b

designed,
applications,
h
`

will
osing
often
=
b
s
e
y
equal
r
to

`
,
=
some
1

.
the
P
of
arameters:
proto
`
2.3
,
signature
A
heme
,
e
B
turn
and
iden
S
sc
in
in
tegers
a
g
sc
an
b
elemen
follo
t
the
of
h-
a
originally
m
osed
ultiplicativ
y
e
and
group
[18],
G
used

y
k
hnorr
ey:
and
s
y
2

[0

;
no
S
randomly
1]
hosen
Public
y
k
v
ey:
but
I
b
=
means
g
a
s
function
Pro
with
v
range
er
;
V
1]
erier
with
Rep
larger
eat
in
`
iden
times
sc

The
ho
of
ose
message
r
is
in
b
[0
taking
;
random
A
in
1]
;
x
1]
=

g
=
r
r
x

!
h

m;

)
k
y

r
2

[0
This
;

B
signature
1]
x;

y

that

y
ho
e
ose


ed
in
y
[0
yb
;
dy
B
the
1]

y
h
=
m;
r
)
+
y

[0

A
s
(
y
1)
!
(

1)

and
k
y
g
xI
y
.
?
=not
F
adv
urthermore,
v
w
prop
ell
0
kno
sc
wn
e
optimizations,
shall
describ
B
ed
0
in
this

order
5.2,
pro

P
h
ey;
as
wing

is
the
in
signature
Compute
to

the
GPS
pair
the
(
y

of
y
h
)
strategy

that
b
that
e
G
applied.
otherwise
This
b
leads
1.
to
B
the
;
follo
S
wing
stop.
signature
=I
sc
h
heme:
If
Input:
alid

y
public
heme
parameters
formally
(
the
G
rst
;
e
g
e
;

A;
follo
B
Fiat
;
wledge
S

)
to

indistinguishable
hash
al
function
heme
h
some
(
2
:
v
)
erations:
,
e
with
the
output
of
range

[0
[0
;
or
B
in
1]
+


signer's
1]
priv
alid
ate
Compute
k
g
ey
.
s
0

m;
message
.

0
ded
output
as
output
an
3
in
of
teger
tication
m
aim
Op
is
erations:
v
signature
y
(
iden

W
y
the
)
del
shall
Next,
b
pro
e


GPS
b
activ
y
w
the
the
follo
F
wing
Shamir


of
soundness.
steps:
demonstrate
1.
against
Randomly
ersaries
generate
v
an
is
in
In
teger
tc
r
v
from
GPS
the
ys
range
y
[0

;
base
A
.
1]
in
.
alid
2.
Op
Compute
output
x
b
=

g
y
r
follo
.

3.
steps:
Compute
If

is
=
in
h
;
(
1]
m;
y
x
not
)
[0
.
A
4.
(
Compute
1)
y
(
=
1)
r
output
+
v

and

2.
s
x
.
=
5.
y
Output

(
3.


y
=
)
(
.
x
A
)
signature
4.
is

v
=
eried
then
using
v
the
else
follo
in
wing
alid.
sc

heme:
analysis
Input:
the

iden
public
sc
parameters
The
(
of
G

;
to
g
pro
;
e
S;

A;
of
B
GPS
)
tication

heme.
hash
e
functions
dene
h

(
mo
:
w
)
use.

in
signer's
to
public
v
k
the
ey
y
I
the

proto
message
against

e
ded
ersaries,
as
e
an
w
in

teger
of
m
eige,

and
signature
[16],
to
ving
b
zero-kno
e
and
v
Another
eried
to
(
the

y
y
activ
)
adv
,
is
a
pro
pair
e
of
GPS
in
witness
tegers
[17].
Output:
[38],
v
oin
alid
hev
if
pro
m
ed
and
the
(
sc

enjo
y
this
)
ert
are
for

sp
t
group
giv
and
en
g
the
G
public
9
kb
3.1
v

with
y

mo
do
del
N
By
v
means
p
of

an
ks
iden
is
tication
random
sc
activ
heme
out
a

pro
in
v
as
er


k
vinces
urthermore,
a
dene
v
(
erier

of
,
his
et
iden
e
tit
order
y
.
.
v
Both
er
the
rst
pro
sequen
v
one,
er
imp
and
some
the
that
v
t
erier
the
are
er
mo
p
deled
the
as


y
p
b
olynomial
0
time
y
T
the
uring
e

erier.
hines
passiv
(
is
Pptm

).
the
They
extract
ha
er's
v
e
e
k
a
trol
sp
,
ecial
t
tap
uring
e,
er
denoted
pro
!
p
,
tications
initially
A
lled
er
with
pro
randomly
k
and

uniformally
allo


hosen
e
bits.
ks
They
parallel
also
[14]
ha
reset
v
state
e
ks
additional
e
tap
er
es
e
where

they
del:

probabilit
read
time
and/or
A
write
negligible:
the
8
messages
erier
that
d
they
v

er
hange.
erier.
See

[30]
trol
for
the
a
dierence

een
denition
and
of

in
the

k
e
e
Pptm
deviate
s.

W
try
e
information

pro
the
k
follo
the
wing
w
scenario
the
for
and
iden
under
tication;
a
rstly
A
a

randomized
made
algo-
o
rithm
time
generates
hines;
public
attac
parameters
1
on
with
input
er
the
executes

n
y
of
parameter
the
k
k
.
,
Its
pro
running
tries
time
the
is
er.
p
rst
olynomial

in
to
k
but
.
is
Next
ed.
a
h

mo

not
algorithm,
to
using
t
random
the
tap
p
e

!
v
K
reset
,
he
generates
pro
pairs
a
of
2].
public
man-in-the-middle
and
b
priv
since
ate
in
k
pro
eys
those
(
erier.
pk
no
,
is
sk
tication
)
this
and
proto
sends
if
the
for

p
k
k
ey
1
to
)
the

pro
d
v
k
er
>
while
[
the
A
related
1
public
the
k

ey
all
is
es.
made
and
a
v
v

ailable
he
to
tak
an

yb
o
o
er
dy
v
,
The

b
of
w

the
the
e
pro
the
v
e
er
ks
and
that
the
activ
v

erier.
er
Finally
mak
,
the
the
erier
iden
from
tication
proto
is
in
an
to
in
to

more
e
ab
proto
the

v
b

et
ey
w
In
een
activ
the
scenario,
pro
e
v
view
er

and
er
the
the
v
erier
erier

whic
as
h
single
resp
hine.
ectiv

ely
an
use
k
random
is
tap
of
es
w
!

P
olynomial
and
T
!

V
the
.
one,
A
k
t
A
the
,
end,

the
a
v
v
erier
and

tially
or
a
not.
olynomial
W
um
e
er
no
iden
w
while
mo

dify
attac
this
er
scenario,
2
where
acts
ev
a
eryb
v
o
and
dy
to
is
ersonate
honest,
original
in
v
order
Of
to
the
add

an
er

transmit
k
information
er
the
whose
one
aim
the
is
trary
to
not
imp
w
ersonate

the

pro
a
v
y
er,
del
i.e.
es
to
tak
b
in
e



b

y
where
a

v
er
erier
erforms
with
authen
the
with
public
pro
k
er
ey
or
of

the
where
pro

v
the
er.
v
In
in
this
former
mo
[9,
del,
F
w

e



an
e

erformed
k
w
er
separate
that

do
the
es
v
not
from

with
public
v
parameters
W
and

k
w
ey
what
generation.
a
Th
iden
us,
proto
there
in
are
mo
only
a
t

w

o
the
w
y
a
an
ys

for
olynomial
him

to
er
obtain
A
information.
;
Firstly
2
,
to
the
e

is
k
8
er
2

9
passiv
0
ely
k
observ
k
e
Pr
the
V


unication
2
during
<
regular
k
authen
where

probabilit
b
is
et
o
w
er
een
the
the
tap
pro
10
v

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin