M. Naor
M. Yung
ABSTRACT
We define a Universal One-Way Hash Function family, a new primitive which enables the compression of elements in the function domain. The main property of this primitive is that given an element x. We prove constructively that universal one-way hash functions exist if any 1-1 one-way functions exist.
Among the various applications of the primitive is a One-Way based Secure Digital Signature Scheme, a system which is based on the existence of any 1-1 One-Way Functions and is secure against the most general attack known. Previously, all provably secure signature schemes were based on the stronger mathematical assumption that trapdoor one-way functions exist.
- 1.Bellare M. and S. Micali How to Sign Given any Trapdoor Function , Proc. 20th Annual Symposium on the Theory of Computing, Chicago, I1, 1988, pp. 32-42. Google Scholar
Digital Library
- 2.Blum M. and S. Micali How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits, SIAM Journal on Computing, V. 13, No. 4, Nov. 84, pp. 850-864. Google ScholarDigital Library
- 3.G. Brassard, C. Crepeau and M. Yung, All NP Can Be Proved in Perfect Zero-Knowledge in Constant Rounds, ICALP 1989, to appear.Google Scholar
- 4.J. L. Carter and M. N. Wegman, Universal Classes of Hash Functions, Journal of Computer and System Sciences 18 (1979), pp. 143-154.Google ScholarCross Ref
- 5.I. B. Damgard, Collision Free Hash Functions and Public Key Signature Schemes , Eurocrypt, 1987.Google Scholar
- 6.W. Diflie and M. Hellman, New Directions in Cryptography, IEEE Trans. on Information Theory, vol. IT-22, 6 (1976), pp. 644-654.Google Scholar
- 7.F. A. Fiat and A. Shamir, How to Prove Yourself' Practical Solutions to Identification Problems and Signature Problems Crypto 1986. Google ScholarDigital Library
- 8.O. Goldreich, Two Remarks Concerning the GMR Signature Scheme, Crypto 86.Google Scholar
- 9.O. Goldreich, H. Krawczyk and M. Luby, On the existence of Pseudorandom Generators, Proceedings of the 29th Symposium on the Foundation of Computer Science, 1988, pp. 12-24.Google ScholarDigital Library
- 10.S. Goldreich, S. Micali and A. Wigderson, Proofs that Yields Nothing But their Validity, and a Methodology of Cryptographic Protocol Design, Proceedings of the 27th Symposium on the Foundation of Computer Science, 1986, pp. 174-187.Google ScholarDigital Library
- 11.S. Goldwasser and S. Micali, Probabilistic Encryption, J. Com. Sys. Sci. 28 (1984), pp. 270- 299.Google ScholarCross Ref
- 12.S. Goldwasser, S. Micali and C. Rackoff, The Knowledge Complexity of Interactive Proof- Systems, Proc. 17th Annual Symposium on the Theory of Computing, Providence RI,, 1985, pp. 291-304. Google ScholarDigital Library
- 13.S. Goldwasser, S. Micali and R. Rivest, A secure digital signature scheme , Siam Journal on Computing, Vol. 17, 2 (1988), pp. 281-308. Google ScholarDigital Library
- 14.S. Goldwasser, S. Micali and A. C. Yao, Strong signature schemes , Proc. 15th Annual Symposium on the Theory of Computing, Boston, Ma, 1983, pp. 431-439. Google ScholarDigital Library
- 15.R. Impagliazzo, L. Levin and M. Luby, Pseudo. random Generation given from a One-way Function, These Proc. Google ScholarDigital Library
- 16.R. Impagliazzo and M. Naor, Efficient Cryptographic Schemes Provably as Secure as Subset Sum, Manuscript.Google Scholar
- 17.R. Impagliazzo and S. Rudich, Limits on the Provable Consequences of One-way Permutations, These Proc. Google ScholarDigital Library
- 18.R. Impagliazzo and M. Yung, Direct Minimum- Knowledge Computations , Proc. of Crypto 87, Springer Verlag. Google ScholarDigital Library
- 19.L. Lamport, Constructing digital signatures from one-way functions, SRI intl. CSL-98, October 1979.Google Scholar
- 20.L. Levin, One-way Functions and Pseudorandom Generators, Proc. 17th Annual Symposium on the Theory of Computing, 1985, pp. 363-365. Google ScholarDigital Library
- 21.R. Merkle, A Digital Signature based on Conventional Encryption Function, Crypto 1987, Springer Verlag. Google ScholarDigital Library
- 22.R. Merkle, Secrecy, Authentication and Public Key Systems, Ph.D. Thesis (1982), UMI Research Press, Ann Arbor, Michigan. Google ScholarDigital Library
- 23.R. Merkle, A Certified Digital Signature, Manuscript 1979.Google Scholar
- 24.R. Merkle and M. Hellman, Hiding Information and Signature in Trapdoor Knapsack, IEEE Trans. on Information Theory, vol. IT-24, 5 (1978), pp. 525-530.Google Scholar
- 25.M. O. Rabin digitalized signatures , in Foundation of Secure Computation, Academic Press, R.A. DeMillo, D. Dobkin, A. Jones and R. Lipton, eds., Academic Press, 1977.Google Scholar
- 26.M. O. Rabin Fingerprinting by Random Polynomials , Harvard University, TR-15-81, 1981.Google Scholar
- 27.M. O. Rabin Digital Signatures and Public Key Functions as Intractable as Factoring, Technical Memo TM-212, Lab. for Computer Science, MIT, 1979. Google ScholarDigital Library
- 28.R. Rivest, A. Shamir and L. Adleman, A Method for Obtaining Digital Signature and Public Key Cryptosystems, Comm. of ACM, 21 (1978), pp. 120-126. Google ScholarDigital Library
- 29.A. Shamir, On the Generation of Cryptographically Strong Pseudo-Random Number Sequences, ACM Trans. Comput. Sys., I (1983), pp. 38-44. Google ScholarDigital Library
- 30.M. N. Wegman and J. L. Carter, New Hash Functions and Their Use in Authentication and Set Equality, Journal of Computer and System Sciences 22, pp. 265-279 (1981).Google ScholarCross Ref
- 31.A. C. Yao, Theory and Applications of Trapdoor functions, Proceedings of the 23th Symposiuin on the Foundation of Computer Science, 1982, pp. 80-91.Google Scholar
Index Terms
- Universal one-way hash functions and their cryptographic applications
Recommendations
Foundations of Non-malleable Hash and One-Way Functions
ASIACRYPT '09: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security: Advances in CryptologyNon-malleability is an interesting and useful property which ensures that a cryptographic protocol preserves the independence of the underlying values: given for example an encryption ${\cal E}(m)$ of some unknown message <em>m</em> , it should be hard ...
How to construct universal one-way hash functions of order r
INDOCRYPT'05: Proceedings of the 6th international conference on Cryptology in IndiaAt ASIACRYPT 2004, Hong et al. introduced the notion of UOWHFs of order r > 0. A UOWHF has the order r if it is infeasible for any adversary to win the game for UOWHF where the adversary is allowed r adaptive queries to the hash function oracle before ...
Universal one-way hash functions via inaccessible entropy
EUROCRYPT'10: Proceedings of the 29th Annual international conference on Theory and Applications of Cryptographic TechniquesThis paper revisits the construction of Universal One-Way Hash Functions (UOWHFs) from any one-way function due to Rompel (STOC 1990). We give a simpler construction of UOWHFs, which also obtains better efficiency and security. The construction exploits ...
Comments