The random oracle methodology, revisited (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The random oracle methodology, revisited (preliminary version)

Full text

Pdf (1.44 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 209 - 218

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Ran Canetti	IBM Watson, P.O. Box 704, Yorktown Heights, NY
Oded Goldreich	Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
Shai Halevi	IBM Watson, P.O. Box 704, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 31, Citation Count: 48

Additional Information:

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/276698.276741 What is a DOI?

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 , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
	2	M. Bellare and P. Rogaway. The Exact Security of Digital Signatures: How to Sign vAth RSA and Rabin. In EuroCrypt96, Springer LNCS (Vol. 1070), pages 399-416.
	3	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]
	4	Ran Canetti, Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.455-469, August 17-21, 1997
	5	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 [doi>10.1145/276698.276721]
	6	I.B. Damg~.rd. Collision free hash functions and public key signature schemes. In EuroOrypt87, LNCS (Vol. 304), Springer-Verlag, 1988. Pages 203-216.
	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	Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
	9	S. Goldwasser and S. Micali. Probabilistic Encryplion. JOSS, Vol. 28, No. 2, pages 270-299, 1984. Preliminary version in ldth STOC, 1982.
	10	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]
	11	L. C. Guillou , J.-J. Quisquater, A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory, Lecture Notes in Computer Science on Advances in Cryptology-EUROCRYPT'88, p.123-128, April 1988, Davos, Switzerland
	12	Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
	13	Joe Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.723-732, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129782]
	14	$. Micali. CS Proofs. in 85th IEEE Symposium on Foundations of Computer Science, pages 436--453, 1994.
	15	M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
	16	Tatsuaki Okamoto, Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.31-53, August 16-20, 1992
	17	D. Pointcheval and J. Stern. Security Proofs for Signature Schemes. In Eurocrypt96, Springer- Vefiag LNCS (Vol. 1070), pages 387-398.
	18	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 [doi>10.1145/100216.100269]
	19	C.P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptolo~y, Vol. 4, No. 3, pages 161-174 (1991).
	20	A.C. Yao. Theory and Application of Trapdoor Functions. In ~3rd IEI~E Symposium on Founda. tions of Computer Science, pages 80-91, 1982.

CITED BY 48

	Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
	H. Wang , Y. Zhang, Untraceable off-line electronic cash flow in e-commerce, Australian Computer Science Communications, v.23 n.1, p.191-198, January-February 2001
	Guillaume Poupard , Jacques Stern, On the fly signatures based on factoring, Proceedings of the 6th ACM conference on Computer and communications security, p.37-45, November 01-04, 1999, Kent Ridge Digital Labs, Singapore
	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
	Oded Goldreich, Cryptography and cryptographic protocols, Distributed Computing, v.16 n.2-3, p.177-199, September 2003
	Hua Wang , Jinli Cao , Yanchun Zhang, A flexible payment scheme and its permission-role assignment, Proceedings of the twenty-sixth Australasian conference on Computer science: research and practice in information technology, p.189-198, February 01, 2003, Adelaide, Australia
	Eric Cronin , Sugih Jamin , Tal Malkin , Patrick McDaniel, On the performance, feasibility, and use of forward-secure signatures, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA
	Cynthia Dwork , Moni Naor , Omer Reingold , Larry Stockmeyer, Magic Functions: In Memoriam: Bernard M. Dwork 1923--1998, Journal of the ACM (JACM), v.50 n.6, p.852-921, November 2003
	Wen-Guey Tzeng, Efficient 1-Out-of-n Oblivious Transfer Schemes with Universally Usable Parameters, IEEE Transactions on Computers, v.53 n.2, p.232-240, February 2004
	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
	Dahlia Malkhi , Michael Merritt , Ohad Rodeh, Secure reliable multicast protocols in a WAN, Distributed Computing, v.13 n.1, p.19-28, January 2000
	Daniel R. Brown, Generic Groups, Collision Resistance, and ECDSA, Designs, Codes and Cryptography, v.35 n.1, p.119-152, April 2005
	Hua Wang , Jinli Cao , Yanchun Zhang, A Flexible Payment Scheme and Its Role-Based Access Control, IEEE Transactions on Knowledge and Data Engineering, v.17 n.3, p.425-436, March 2005
	Hoeteck Wee, On obfuscating point functions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Eli Ben-Sasson , Madhu Sudan, Simple PCPs with poly-log rate and query complexity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Maurizio Adriano Strangio, Efficient Diffie-Hellmann two-party key agreement protocols based on elliptic curves, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Luis von Ahn , Nicholas Hopper , John Langford, Covert two-party computation, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Chik How Tan, A secure signature scheme, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
	Javier Herranz , Germán Sáez, Distributed Ring Signatures from General Dual Access Structures, Designs, Codes and Cryptography, v.40 n.1, p.103-120, July 2006
	Jonathan Katz , Nan Wang, Efficiency improvements for signature schemes with tight security reductions, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA
	Christian Cachin , Klaus Kursawe , Anna Lysyanskaya , Reto Strobl, Asynchronous verifiable secret sharing and proactive cryptosystems, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA
	Phillip G. Bradford , Olga V. Gavrylyako, Hash chains with diminishing ranges for sensors, International Journal of High Performance Computing and Networking, v.4 n.1/2, p.31-38, July 2006
	Markus Jakobsson , Steven Myers, Delayed password disclosure, International Journal of Applied Cryptography, v.1 n.1, p.47-59, February 2008
	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
	Matthew Pirretti , Patrick Traynor , Patrick McDaniel , Brent Waters, Secure attribute-based systems, 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
	Jan Camenisch , Maciej Koprowski, Fine-grained forward-secure signature schemes without random oracles, Discrete Applied Mathematics, v.154 n.2, p.175-188, 1 February 2006
	Sherman S. M. Chow , Victor K. Wei , Joseph K. Liu , Tsz Hon Yuen, Ring signatures without random oracles, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan
	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
	Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Provably secure authenticated group Diffie-Hellman key exchange, ACM Transactions on Information and System Security (TISSEC), v.10 n.3, p.10-es, July 2007
	Zuhua Shao, A provably secure short signature scheme based on discrete logarithms, Information Sciences: an International Journal, v.177 n.23, p.5432-5440, December, 2007
	Oleg Izmerly , Tal Mor, Chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment, Theoretical Computer Science, v.367 n.3, p.308-323, December, 2006
	Caroline Fontaine , Fabien Galand, A survey of homomorphic encryption for nonspecialists, European Journal of Information Systems, v.2007 n.1, p.1-15, January 2007
	Craig Gentry , Zulfikar Ramzan, Provable Cryptographic Security and its Applications to Mobile Wireless Computing, Wireless Personal Communications: An International Journal, v.29 n.3-4, p.191-203, June 2004
	Markus Jakobsson , Steven Myers, Delayed password disclosure, Proceedings of the 2007 ACM workshop on Digital identity management, November 02-02, 2007, Fairfax, Virginia, USA
	Markus Jakobsson , Steven Myers, Delayed password disclosure, ACM SIGACT News, v.38 n.3, September 2007
	Chik How Tan, A new signature scheme without random oracles, International Journal of Security and Networks, v.1 n.3/4, p.237-242, December 2006
	Jean-Sébastien Coron, A variant of Boneh-Franklin IBE with a tight reduction in the random oracle model, Designs, Codes and Cryptography, v.50 n.1, p.115-133, January 2009
	Zheng Gong , Xuejia Lai , Kefei Chen, A synthetic indifferentiability analysis of some block-cipher-based hash functions, Designs, Codes and Cryptography, v.48 n.3, p.293-305, September 2008
	Colin Boyd , Yvonne Cliff , Juan M. Gonzalez Nieto , Kenneth G. Paterson, One-round key exchange in the standard model, International Journal of Applied Cryptography, v.1 n.3, p.181-199, February 2009
	SeongHan Shin , Kazukuni Kobara , Hideki Imai, A Secure Authenticated Key Exchange Protocol for Credential Services, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.1, p.139-149, January 2008
	Mototsugu Nishioka, Identity-Based Encryptions with Tight Security Reductions to the BDH Problem, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.5, p.1241-1252, May 2008
	Yanli Ren , Dawu Gu, Fully CCA2 secure identity based broadcast encryption without random oracles, Information Processing Letters, v.109 n.11, p.527-533, May, 2009
	Mototsugu Nishioka , Naohisa Komatsu, A Note on the Random Oracle Methodology, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.2, p.650-663, February 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
	Feng Cao , Zhenfu Cao, An identity based universal designated verifier signature scheme secure in the standard model, Journal of Systems and Software, v.82 n.4, p.643-649, April, 2009
	Haifeng Qian , Yuan Zhou , Zhibin Li , Zecheng Wang , Bing Zhang, Efficient public key encryption with smallest ciphertext expansion from factoring, Designs, Codes and Cryptography, v.49 n.1-3, p.233-249, December 2008
	Yanjiang Yang , Feng Bao , Xuhua Ding , Robert H. Deng, Multiuser private queries over encrypted databases, International Journal of Applied Cryptography, v.1 n.4, p.309-319, August 2009