Algorithm Schnorr signature
1 algorithm
1.1 choosing parameters
1.2 notation
1.3 key generation
1.4 signing
1.5 verifying
1.6 proof of correctness
1.7 security argument
algorithm
choosing parameters
all users of signature scheme agree on group,
g
{\displaystyle g}
, of prime order,
q
{\displaystyle q}
, generator,
g
{\displaystyle g}
, in discrete log problem assumed hard. typically schnorr group used.
all users agree on cryptographic hash function
h
:
{
0
,
1
}
∗
→
z
q
{\displaystyle h:\{0,1\}^{*}\rightarrow \mathbb {z} _{q}}
.
notation
in following,
exponentiation stands repeated application of group operation
juxtaposition stands multiplication on set of congruence classes or application of group operation (as applicable)
subtraction stands subtraction on set of equivalence groups
m
∈
{
0
,
1
}
∗
{\displaystyle m\in \{0,1\}^{*}}
, set of finite bit strings
s
,
e
,
e
v
∈
z
q
{\displaystyle s,e,e_{v}\in \mathbb {z} _{q}}
, set of congruence classes modulo
q
{\displaystyle q}
x
,
k
∈
z
q
×
{\displaystyle x,k\in \mathbb {z} _{q}^{\times }}
, multiplicative group of integers modulo
q
{\displaystyle q}
(for prime
q
{\displaystyle q}
,
z
q
×
=
z
q
∖
0
¯
q
{\displaystyle \mathbb {z} _{q}^{\times }=\mathbb {z} _{q}\setminus {\overline {0}}_{q}}
)
y
,
r
,
r
v
∈
g
{\displaystyle y,r,r_{v}\in g}
.
key generation
choose private signing key,
x
{\displaystyle x}
, allowed set.
the public verification key
y
=
g
x
{\displaystyle y=g^{x}}
.
signing
to sign message,
m
{\displaystyle m}
:
choose random
k
{\displaystyle k}
allowed set.
let
r
=
g
k
{\displaystyle r=g^{k}}
.
let
e
=
h
(
r
∥
m
)
{\displaystyle e=h(r\parallel m)}
,
∥
{\displaystyle \parallel }
denotes concatenation ,
r
{\displaystyle r}
represented bit string.
let
s
=
k
−
x
e
{\displaystyle s=k-xe}
.
the signature pair,
(
s
,
e
)
{\displaystyle (s,e)}
.
note
s
,
e
∈
z
q
{\displaystyle s,e\in \mathbb {z} _{q}}
; if
q
<
2
160
{\displaystyle q<2^{160}}
, signature representation can fit 40 bytes.
verifying
let
r
v
=
g
s
y
e
{\displaystyle r_{v}=g^{s}y^{e}}
let
e
v
=
h
(
r
v
∥
m
)
{\displaystyle e_{v}=h(r_{v}\parallel m)}
if
e
v
=
e
{\displaystyle e_{v}=e}
signature verified.
proof of correctness
it relatively easy see
e
v
=
e
{\displaystyle e_{v}=e}
if signed message equals verified message:
r
v
=
g
s
y
e
=
g
k
−
x
e
g
x
e
=
g
k
=
r
{\displaystyle r_{v}=g^{s}y^{e}=g^{k-xe}g^{xe}=g^{k}=r}
, , hence
e
v
=
h
(
r
v
∥
m
)
=
h
(
r
∥
m
)
=
e
{\displaystyle e_{v}=h(r_{v}\parallel m)=h(r\parallel m)=e}
.
public elements:
g
{\displaystyle g}
,
g
{\displaystyle g}
,
q
{\displaystyle q}
,
y
{\displaystyle y}
,
s
{\displaystyle s}
,
e
{\displaystyle e}
,
r
{\displaystyle r}
. private elements:
k
{\displaystyle k}
,
x
{\displaystyle x}
.
this shows correctly signed message verify correctly; many other properties required secure signature algorithm.
security argument
the signature scheme constructed applying fiat–shamir transformation schnorr s identification protocol. therefore, (as per fiat , shamir s arguments), secure if
h
{\displaystyle h}
modeled random oracle.
its security can argued in generic group model, under assumption
h
{\displaystyle h}
random-prefix preimage resistant , random-prefix second-preimage resistant . in particular,
h
{\displaystyle h}
not need collision resistant.
in 2012, seurin provided exact proof of schnorr signature scheme. in particular, seurin shows security proof using forking lemma best possible result signature schemes based on one-way group homomorphisms including schnorr-type signatures , guillou-quisquater signature schemes. namely, under romdl assumption, algebraic reduction must lose factor
f
(
ϵ
f
)
q
h
{\displaystyle f({\epsilon }_{f})q_{h}}
in time-to-success ratio,
f
≤
1
{\displaystyle f\leq 1}
function remains close 1 long
ϵ
f
{\displaystyle {\epsilon }_{f}}
noticeably smaller 1 ,
ϵ
f
{\displaystyle {\epsilon }_{f}}
probability of forging error making @
q
h
{\displaystyle q_{h}}
queries random oracle.
Comments
Post a Comment