Attacks on the birational permutation signature schemes

Shamir (1993) presented a family of cryptographic signature schemes based on birational permutations of the integers modulo a large integer <i>N</i> of unknown factorization. These schemes are attractive because of the low computational requirements, both for signature generation and signature verification. However, the two schemes presented in Shamir's paper are weak. We show how to break the first scheme, by first reducing it algebraically to the earlier Ong-Schnorr-Shamir signature scheme (1984), and then applying the Pollard (1987) solution to that scheme. We then show some attacks on the second scheme. These attacks give ideas which can be applied to schemes in this general family


Published in:
Advances in Cryptology - CRYPTO '93, 13th Annual International Cryptology Conference, 773, 435-43
Presented at:
Advances in Cryptology - CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993
Year:
1993
Laboratories:




 Record created 2007-01-18, last modified 2018-03-17

n/a:
Download fulltext
PS

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)