Cryptography Reference
In-Depth Information
Alice
Bob
generate c , s 1 , s 2 , r 1 ,..., r N
n i =
g
(
s 1 ,
n i )
y i = C r i ( n i , k i , c )
i
)
, k i =
g
(
s 2 ,
c , y 1 ,..., y N
−−−−−−−−−−−−−−−−−−−→
pick i , solve
( y i , c )
, get n i , k i
n i
←−−−−−−−−−−−−−−−−−−−
k i = g ( s 2 , n i )
keep k i
keep k i
Figure 5.6. Merkle Key exchange protocol using puzzles.
One of the first signature schemes was invented by Ralph Merkle in 1979 (but it
was published 10 years later; see Ref. [131]). Basic principles are twofold:
Each bit x i of the message is signed by using a one-time secret key k i : a 1-bit
x i =
1 is signed by disclosing the secret key k i , and the corresponding public
key is the image
h ( k i ) of the secret key through a one-way function;
A large set of public keys
v i =
v i is authenticated by using a hash tree: each
v i is
attached to a leaf of an oriented binary tree, and if a
and a r are attached to the
two subtrees of a node, we attach h ( a ,
a r ) to the node where h is a collision-
resistant hash function.
The property of the hash tree is that we can authenticate all public keys by authenticating
the value attached to the root of the tree only. Therefore, assuming that the root value
is authenticated, we sign the message x by disclosing all k i keys for which x i =
1 and
reminding all
v i for other i . Signature verification simply consists in checking that all
h ( k i ) and reminded
v i lead to the correct root value when attached to the tree 6
(see
Fig. 5.7).
One problem with this basic signature scheme is that only 1-bits are signed: the
signature verifier is ensured that all 1-bits are authentic, but he is not sure for 0-bits
since they could have been substituted to 1-bits. This problem is fixed by preencoding
the message. A message m is first encoded into a binary string x in such a way that
replacing one or several 1-bit of x by 0-bits leads to an invalid codeword. As an
example, Merkle proposed to simply append to m the binary representation c of the
number of 0-bits in m : x
c . We notice that if c is the binary representation
of a number which is greater than c , then there must be at least one position i for
which we have c i =
=
m
||
0 and c i =
1. Since the adversary cannot replace a 0-bit by a
1-bit in x , he cannot increase the number of 0-bit in m by replacing a 1-bit by a
0-bit.
+
+
=
If m has a length of n , then x has a length of n
log 2 n . Hence we need n
log 2 n
O ( n ) keys to sign m , and O ( n ) h -operation in order to sign or verify the signature.
6
As one can see, the main difference between computer science and botanic is that trees are rooted on the
top in the former.
Search WWH ::




Custom Search