Universal one-way hash functions and their cryptographic applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Universal one-way hash functions and their cryptographic applications

Full text

Pdf (1.15 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-first annual ACM symposium on Theory of computing table of contents

Seattle, Washington, United States

Pages: 33 - 43

Year of Publication: 1989

ISBN:0-89791-307-8

Authors

M. Naor	Computer Science Division, University of California at Berkeley, Berkeley, CA
M. Yung	IBM Research Division, T.J Watson Research Center, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 186, Citation Count: 49

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/73007.73011 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Mihir Bellare , Silvio Micali, How to sign given any trapdoor function, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.32-42, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62216]
	2	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	3	G. Brassard, C. Crepeau and M. Yung, All NP Can Be Proved in Perfect Zero-Knowledge in Constant Rounds, ICALP 1989, to appear.
	4	J. L. Carter and M. N. Wegman, Universal Classes of Hash Functions, Journal of Computer and System Sciences 18 (1979), pp. 143-154.
	5	I. B. Damgard, Collision Free Hash Functions and Public Key Signature Schemes , Eurocrypt, 1987.
	6	W. Diflie and M. Hellman, New Directions in Cryptography, IEEE Trans. on Information Theory, vol. IT-22, 6 (1976), pp. 644-654.
	7	Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
	8	O. Goldreich, Two Remarks Concerning the GMR Signature Scheme, Crypto 86.
	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.
	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.
	11	S. Goldwasser and S. Micali, Probabilistic Encryption, J. Com. Sys. Sci. 28 (1984), pp. 270- 299.
	12	S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
	13	Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
	14	Shafi Goldwasser , Silvio Micali , Andy Yao, Strong signature schemes, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.431-439, December 1983 [doi>10.1145/800061.808774]
	15	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
	16	R. Impagliazzo and M. Naor, Efficient Cryptographic Schemes Provably as Secure as Subset Sum, Manuscript.
	17	R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73012]
	18	Russell Impagliazzo , Moti Yung, Direct Minimum-Knowledge Computations, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.40-51, August 16-20, 1987
	19	L. Lamport, Constructing digital signatures from one-way functions, SRI intl. CSL-98, October 1979.
	20	L A Levin, One-way functions and pseudorandom generators, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.363-365, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22185]
	21	Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
	22	Ralph Charles Merkle, Secrecy, authentication, and public key systems., 1979
	23	R. Merkle, A Certified Digital Signature, Manuscript 1979.
	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.
	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.
	26	M. O. Rabin Fingerprinting by Random Polynomials , Harvard University, TR-15-81, 1981.
	27	M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
	28	R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
	29	Adi Shamir, On the generation of cryptographically strong pseudorandom sequences, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.38-44, Feb. 1983 [doi>10.1145/357353.357357]
	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).
	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.

CITED BY 49

	Maurizio Kliban Boyarsky, Public-key cryptography and password protocols: the multi-user case, Proceedings of the 6th ACM conference on Computer and communications security, p.63-72, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
	Ronald Cramer , Victor Shoup, Signature schemes based on the strong RSA assumption, Proceedings of the 6th ACM conference on Computer and communications security, p.46-51, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States
	Cheng-Chi Lee , Min-Shiang Hwang , Wei-Peng Yang, A flexible remote user authentication scheme using smart cards, ACM SIGOPS Operating Systems Review, v.36 n.3, p.46-52, July 2002
	Hugo Krawczyk, Distributed fingerprints and secure information dispersal, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.207-218, August 15-18, 1993, Ithaca, New York, United States
	Giovanni Di Crescenzo , Russell Impagliazzo, Security-preserving hardness-amplification for any regular one-way function, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.169-178, May 01-04, 1999, Atlanta, Georgia, United States
	Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States
	Ronald Cramer , Victor Shoup, Signature schemes based on the strong RSA assumption, ACM Transactions on Information and System Security (TISSEC), v.3 n.3, p.161-185, Aug. 2000
	Ran Canetti , Daniele Micciancio , Omer Reingold, Perfectly one-way probabilistic hash functions (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.131-140, May 24-26, 1998, Dallas, Texas, United States
	Joe Kilian , Erez Petrank, Concurrent and resettable zero-knowledge in poly-loalgorithm rounds, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.560-569, July 2001, Hersonissos, Greece
	Rosario Gennaro , Yael Gertner , Jonathan Katz, Lower bounds on the efficiency of encryption and digital signature schemes, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Moni Naor, Evaluation may be easier than generation (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.74-83, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Mihir Bellare , Silvio Micali, How to sign given any trapdoor permutation, Journal of the ACM (JACM), v.39 n.1, p.214-233, Jan. 1992
	Ramarathnam Venkatesan , Sivaramakrishnan Rajagopalan, Average case intractability of matrix and diophantine problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.632-642, May 04-06, 1992, Victoria, British Columbia, Canada
	Toshiya Itoh , Yoshinori Takei , Jun Tarui, On permutations with limited independence, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.137-146, January 09-11, 2000, San Francisco, California, United States
	Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States
	Pankaj Rohatgi, A compact and fast hybrid signature scheme for multicast packet authentication, Proceedings of the 6th ACM conference on Computer and communications security, p.93-100, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
	Christian Cachin, Efficient private bidding and auctions with an oblivious third party, Proceedings of the 6th ACM conference on Computer and communications security, p.120-127, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
	Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States
	R. Impagliazzo , S. Rudich, Limits on the provable consequences of one-way permutations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.44-61, May 14-17, 1989, Seattle, Washington, United States
	Shouhuai Xu , Ravi Sandhu, Authenticated multicast immune to denial-of-service attack, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
	Toshiya Itoh , Yoshinori Takei , Jun Tarui, On the sample size of k-restricted min-wise independent permutations and other k-wise distributions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Randal Burns , Zachary Peterson , Giuseppe Ateniese , Stephen Bono, Verifiable audit trails for a versioning file system, Proceedings of the 2005 ACM workshop on Storage security and survivability, November 11-11, 2005, Fairfax, VA, USA
	Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited, Journal of the ACM (JACM), v.51 n.4, p.557-594, July 2004
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	Rafael Pass , Alon Rosen, New and improved constructions of non-malleable cryptographic protocols, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Kirk H. M. Wong , Patrick C. L. Hui , Allan C. K. Chan, Cryptography and authentication on RFID passive tags for apparel products, Computers in Industry, v.57 n.4, p.342-349, May 2006
	Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions, Computational Complexity, v.16 n.4, p.365-411, December 2007
	Mihir Bellare , Tadayoshi Kohno , Victor Shoup, Stateful public-key cryptosystems: how to encrypt with one 160-bit exponentiation, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
	Oded Goldreich, Foundations of cryptography: a primer, Foundations and Trends® in Theoretical Computer Science, v.1 n.1, p.1-116, April 2005
	Rosario Gennaro , Yehuda Lindell, A framework for password-based authenticated key exchange¹, ACM Transactions on Information and System Security (TISSEC), v.9 n.2, p.181-234, May 2006
	Dario Catalano , Rosario Gennaro, Cramer-Damgård signatures revisited: Efficient flat-tree signatures based on factoring, Theoretical Computer Science, v.370 n.1-3, p.186-200, February, 2007
	Moni Naor , Kobbi Nissim, Certificate revocation and certificate update, Proceedings of the 7th conference on USENIX Security Symposium, 1998, p.17-17, January 26-29, 1998, San Antonio, Texas
	Iftach Haitner , Omer Reingold, Statistically-hiding commitment from any one-way function, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Ross Anderson , Francesco Bergadano , Bruno Crispo , Jong-Hyeon Lee , Charalampos Manifavas , Roger Needham, A new family of authentication protocols, ACM SIGOPS Operating Systems Review, v.32 n.4, p.9-20, Oct. 1998
	Lenore Cowen , Joan Feigenbaum , Sampath Kannan, A formal framework for evaluating heuristic programs, Annals of Mathematics and Artificial Intelligence, v.22 n.3-4, p.193-206, 1998
	J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States
	M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States
	Phillip Rogaway , Mihir Bellare, Robust computational secret sharing and a unified account of classical secret-sharing goals, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA
	Palash Sarkar, Note: Construction of universal one-way hash functions: Tree hashing revisited, Discrete Applied Mathematics, v.155 n.16, p.2174-2180, October, 2007
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Cryptography with constant computational overhead, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Ting-Yi Chang , Chou-Chen Yang , Chia-Meng Chen, Improvement on Pretty-Simple Password Authenticated Key-Exchange Protocol for Wireless Networks, Informatica, v.15 n.2, p.161-170, April 2004
	Craig Gentry , Chris Peikert , Vinod Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Moni Naor , Guy N. Rothblum, The complexity of online memory checking, Journal of the ACM (JACM), v.56 n.1, p.1-46, January 2009
	Iftach Haitner , Omer Reingold , Salil Vadhan , Hoeteck Wee, Inaccessible entropy, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Haeryong Park , Seongan Lim , Ikkwon Yie , Kitae Kim , Junghwan Song, Strong unforgeability in group signature schemes, Computer Standards & Interfaces, v.31 n.4, p.856-862, June, 2009
	Takahiro Matsuda , Nuttapong Attrapadung , Goichiro Hanaoka , Kanta Matsuura , Hideki Imai, A Strongly Unforgeable Signature under the CDH Assumption without Collision Resistant Hash Functions, IEICE - Transactions on Information and Systems, v.E91-D n.5, p.1466-1476, May 2008
	Yasumasa Hirai , Takashi Kurokawa , Shin'ichiro Matsuo , Hidema Tanaka , Akihiro Yamamura, Classification of Hash Functions Suitable for Real-Life Systems, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.1, p.64-73, January 2008
	Amir Herzberg, Folklore, practice and theory of robust combiners, Journal of Computer Security, v.17 n.2, p.159-189, April 2009