Cryptography Reference
In-Depth Information
Exercise 22.1.7
In the Schnorr identification scheme as presented above, the challenge is
a randomly chosen integer 1
s
1
<r
. Instead, for efficiency
1
≤
reasons, one could choose
κ
(where
κ
is the security parameter, but where 2
l
is significantly smaller than
r
). Show that the proof of Theorem
22.1.5
still holds in this
setting.
s
1
<
2
l
for some
l
such that
l
1
≤
≥
Exercise 22.1.8
Explain why the Schnorr identification scheme cannot be implemented in
an algebraic group quotient.
22.1.2 Schnorr signatures
We now present the
Schnorr signature scheme
[
469
,
470
], which has very attractive
security and efficiency. The main idea is to make the identification protocol of the previous
section non-interactive by replacing the challenge
s
1
by a random integer that depends
on the message being signed. This idea is known as the
Fiat-Shamir transform
.By
Exercise
22.1.6
it is important that
s
1
cannot be predicted and so it is also necessary to
make it depend on
s
0
.
More precisely, one sets
s
1
=
H
(
m
s
0
) where
H
is a cryptographic hash function from
}
∗
to
l
for some parameter
l
and where
m
and
s
0
are interpreted as binary strings
{
0
,
1
{
0
,
1
}
(and where
denotes concatenation of binary strings as usual).
One would therefore obtain the following signature scheme, which we call
naive
Schnorr signatures
: To sign a message
m
choose a random 0
≤
k<r
, compute
s
0
=
g
k
,
s
1
=
a
s
1
(mod
r
) and send the signature (
s
0
,
s
2
) together with
m
.
A verifier, given
m
,
(
s
0
,
s
2
) and the public key
h
, would compute
s
1
=
H
(
m
s
0
) and
s
2
=
k
+
H
(
m
s
0
) and accept
the signature if
g
s
2
s
0
h
s
1
.
=
(22.2)
Schnorr makes the further observation that instead of sending (
s
0
,
s
2
) one could send
(
s
1
,
s
2
). This has major implications for the size of signatures. For example,
g
may be
an element of order
r
in
F
p
(for example, with
r
2
256
2
3072
). In this case,
≈
and
p
≈
g
k
requires 3072 bits,
s
2
requires 256 bits and
s
1
may require as little as 128 bits. In
other words, signatures would have 3072
s
0
=
+
256
=
3328 bits in the naive scheme, whereas
Schnorr signatures only require 128
384 bits.
We present the precise Schnorr signature scheme in Box
22.1
.
+
256
=
Example 22.1.9
Let
p
=
311 and
r
=
31
|
(
p
−
1). Let
g
=
169 which has order
r
.Let
g
a
a
=
47 (mod
p
).
To sign a message
m
(a binary string) let
k
11 and
h
=
≡
g
k
=
20 and
s
0
=
≡
225 (mod
p
). The binary
expansion of
s
0
is (11100001)
2
. We must now compute
s
1
=
(11100001)). Since we
do not want to go into the details of
H
, let us just suppose that the output length of
H
is
4 and that
s
1
is the binary string 1001. Then
s
1
corresponds to the integer 9. Finally, we
H
(
m
1
One could speed up signature verification using similar methods to Exercise
22.1.13
.