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 .
Search WWH ::




Custom Search