From Wikipedia, the free encyclopedia
In the
mathematical
and
computer science
field of
cryptography
, a group of three numbers (
x
,
y
,
z
) is said to be a
claw
of two permutations
f
0
and
f
1
if
- f
0
(
x
) =
f
1
(
y
) =
z
.
A pair of permutations
f
0
and
f
1
are said to be
claw-free
if there is no efficient algorithm for computing a claw.
The terminology
claw free
was introduced by
Goldwasser
,
Micali
, and
Rivest
in their 1984 paper, "A Paradoxical Solution to the Signature Problem" (and later in a more complete journal paper), where they showed that the existence of
claw-free pairs of trapdoor permutations
implies the existence of digital signature schemes secure against
adaptive chosen-message attack
.
[1]
[2]
This construction was later superseded by the construction of digital signatures from any one-way trapdoor permutation.
[3]
The existence of
trapdoor permutations
does not by itself imply claw-free permutations exist;
[4]
however, it has been shown that claw-free permutations do exist if factoring is hard.
[5]
The general notion of claw-free permutation (not necessarily trapdoor) was further studied by
Ivan Damgard
in his PhD thesis
The Application of Claw Free Functions in Cryptography
(Aarhus University, 1988), where he showed how to construct
Collision Resistant Hash Functions
from claw-free permutations.
[5]
The notion of claw-freeness is closely related to that of collision resistance in hash functions. The distinction is that claw-free permutations are
pairs
of functions in which it is hard to create a collision between them, while a collision-resistant hash function is a single function in which it's hard to find a collision, i.e. a function
H
is collision resistant if it's hard to find a pair of distinct values
x
,
y
such that
- H
(
x
) =
H
(
y
).
In the hash function literature, this is commonly termed a
hash collision
. A hash function where collisions are difficult to find is said to have
collision resistance
.
Bit commitment
[
edit
]
Given a pair of claw-free permutations
f
0
and
f
1
it is straightforward to create a
commitment scheme
. To commit to a bit
b
the sender chooses a random
x
, and calculates
f
b
(
x
). Since both
f
0
and
f
1
share the same domain (and range), the bit
b
is statistically hidden from the receiver. To open the commitment, the sender simply sends the randomness
x
to the receiver. The sender is bound to his bit because opening a commitment to 1 −
b
is exactly equivalent to finding a claw. Notice that like the construction of Collision Resistant Hash functions, this construction does not require that the claw-free functions have a trapdoor.
References
[
edit
]
- ^
Goldwasser, Shafi
;
Micali, Silvio
;
Rivest, Ronald L.
(1984). "A Paradoxical Solution to the Signature Problem".
Proceedings of FOCS
(PDF)
. pp. 441?448.
- ^
Goldwasser, Shafi
;
Micali, Silvio
;
Rivest, Ronald L.
(April 1988). "A digital signature scheme secure against adaptive chosen-message attacks".
SIAM J. Comput
.
17
(2): 281?308.
CiteSeerX
10.1.1.20.8353
.
doi
:
10.1137/0217017
.
- ^
Bellare, Mihir
;
Micali, Silvio
(1992).
"How to sign given any trapdoor permutation"
.
Journal of the ACM
.
39
: 214?233.
doi
:
10.1145/147508.147537
.
S2CID
628275
.
- ^
Dodis, Yevgeniy; Reyzin, Leonid (2002). "On the Power of Claw-Free Permutations": 55?73.
CiteSeerX
10.1.1.19.6331
.
- ^
a
b
Damgard, Ivan Bjerre
(1988). "Collision free hash functions and public key signature schemes".
Advances in Cryptology ? EUROCRYPT' 87
. Lecture Notes in Computer Science. Vol. 304. Springer. pp. 203?216.
doi
:
10.1007/3-540-39118-5_19
.
Further reading
[
edit
]