Mihir Bellare
Silvio Micali
Abstract
A digital signature scheme is presented, which is based on the existence of any trapdoor permutation. The scheme is secure in the strongest possible natural sense: namely, it is secure against existential forgery under adaptive chosen message attack.
- 1 BELLARE, M , AND MrC~,LI, S. How to sign given any trapdoor fllnctions. In Proceedings of the 20th Annual A CM S vmposzum on the Theoo' of Computing. ACM, New York, 1988, pp 32-42. Google Scholar
Digital Library
- 2 BLUM, L , BLUM, M., AND SHUB, M. A simple unpredactable pseudo-random number generator SIAM J. Comput. 15, 2 (May 1986), 364-383. Google ScholarDigital Library
- 3 BLUM, M., AND MICALI, S. How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13, 4 (Nov. 1984), 850-864 Google ScholarDigital Library
- 4 DIFFIE, W., AND HELLMAN, M.E. New directions in cryptography, IEEE Trans. Info. Theory IT-22 (Nov. 1976), 644-654.Google ScholarDigital Library
- 5 GOI~t)r~ETCH, O. Two remarks concerning the GMR signature scheme. Tech Rep. 715, MIT Laboratory for Computer Science, MIT, Cambridge, Mass., Sept. 1986.Google Scholar
- 6 GOLDREICH, O., GOLDWASSER, S., AND MICALI, S. HOW to construct random functions. J. ACM. 33, 4 (Oct. 1986), 792-807. Google ScholarDigital Library
- 7 GOLDWASSER, S., AND MICALI, S. Probabalistic encryption. J Comput. Syst. Sci. 28 (Apr. 1984), 270-299.Google ScholarCross Ref
- 8 GOLDWASSER, S., MICALI, S., AND RIVEST, R. A digital signature scheme secure against adaptxve chosen-message attacks. SIAM J. Comput. 17, 2 (Apr. 1988), 281-308. Google ScholarDigital Library
- 9 GOLDWASSER, S., MICALI, S., YAO, A. Strong signature schemes. In Proceedings of the 15th Annual ACM Symposium on the Theory of Computing. ACM, New York 1983, pp. 431-439. Google ScholarDigital Library
- 10 GumLou, L. A zero-knowledge evolution of the paradoxical GMR signature scheme. Manuscript, (Feb. 1988).Google Scholar
- 11 LAMPORT, L. Constructing digital signatures from a one-way funcnon. SRI Intl. CSL-98. (October 1979).Google Scholar
- 12 MERKLE, R. A digital signature based on a conventional encryption function. In Advances in Cryptology-CRYPTO "87 Lecture Notes in Computer Science, vol. 293. Springer-Verlag, New York, 1987. Google ScholarDigital Library
- 13 NAOR, M., AND YUNC, M. Universal one-way hash functions and their cryptographic apphcatIons. In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. ACM New York 1989, pp. 33-43. Google ScholarDigital Library
- 14 RIVEST, R., SHAMIa, A., AND ADLEMAN, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM (Feb. 1978), 120-t26. Google ScholarDigital Library
- 15 ROMPEL, J One-way functions are necessary and sufficient for secure signatures. In Proceedings of the 22nd Annual A CM Symposium on the Theoo' of Computing. ACM New York, 1990, pp. 387-394. Google ScholarDigital Library
- 16 WILLIAMS, H. C. A modification of the RSA public-key cryptosystem. IEEE Trans. Inf. Theory, IT-26 (1980), 726- 729.Google ScholarCross Ref
- 17 YAO, A.C. Theory and applications of trapdoor functions. In Proceedings of the 23rd Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 1982, pp. 80-91.Google ScholarDigital Library
Index Terms
- How to sign given any trapdoor permutation
Recommendations
CCA Security and Trapdoor Functions via Key-Dependent-Message Security
Advances in Cryptology – CRYPTO 2019AbstractWe study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, ...
Transitive signatures: new schemes and proofs
We present novel realizations of the transitive signature primitive introduced by Micali and Rivest, enlarging the set of assumptions on which this primitive can be based, and also providing performance improvements over existing schemes. More ...
CCA Security and Trapdoor Functions via Key-Dependent-Message Security
AbstractWe study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, ...
Reviews
Catherine Ann Meadows
A trapdoor permutation is one that is easy to compute but difficult to invert unless some further information is known. The most straightforward way to use a trapdoor permutation for digital signatures is to make the permutation public but keep its inverse secret. The owner of the secret can sign a message by computing the inverse of the function on the message, while others who do not know the secret can verify the signature by computing the public function on the signed message and verifying that the original message is obtained. No trapdoor permutation can be guaranteed to be difficult to invert on its entire domain, however. Moreover, a trapdoor permutation may have algebraic properties that make it possible to compute new signed messages from old signed messages. In this paper, the authors show how to use trapdoor permutations to construct a digital signature scheme that is secure in the very strong sense that an attacker who may obtain a signature on any message she or he chooses cannot use the information to construct signatures of her or his own. This scheme works for any trapdoor permutation. It begins by using a pair of trapdoor permutations f 0 and f 1 and a random seed a to sign a single bit; either a zero or a one is signed depending on whether the inverse of f 0 a or of f 1 a is computed. Further pairs of trapdoor permutations are used to sign a second random seed bit by bit; this seed and the first pair of functions are used to sign a second bit, and so forth. The authors show how more compact signatures can be achieved by arranging the scheme in a tree structure. The results of this paper have also been used by Naor and Yung and by Rompel to show that one-way permutations and one-way functions are sufficient for secure digital signature schemes. The authors point out that the algorithms described in this paper can be used as an introduction to the more complex schemes described in those papers.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments