{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:36:01Z","timestamp":1771702561928,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540648925","type":"print"},{"value":"9783540684626","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055735","type":"book-chapter","created":{"date-parts":[[2006,7,27]],"date-time":"2006-07-27T17:12:36Z","timestamp":1154020356000},"page":"283-298","source":"Crossref","is-referenced-by-count":36,"title":["Many-to-one trapdoor functions and their relation to public-key cryptosystems"],"prefix":"10.1007","author":[{"given":"Mihir","family":"Bellare","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shai","family":"Halevi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai and C. Dwork. A public-key cryptoSystem with worst-case\/average-case equivalence. Proceedings of the 29th Annual Symposium on the Theory of Computing, ACM, 1997.","DOI":"10.1145\/258533.258604"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Adleman, Manders and Miller. On taking roots in finite fields. Proceedings of the 18th Symposium on Foundations of Computer Science, IEEE, 1977.","DOI":"10.1109\/SFCS.1977.18"},{"key":"20_CR3","unstructured":"M. Bellare, S. Halevi, A. Sahai, and S. Vadhan. Many-to-one trapdoor functions and their relation to public-key cryptosystems. Pull version of this paper, available via http:\/\/www-cse.ucsd.edu\/users\/mihir."},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"M. Bellare and P. Rogaway. Random oracles are practical: a paradigm for designing efficient protocols. Proceedings of the First Annual Conference on Computer and Communications Security, ACM, 1993.","DOI":"10.1145\/168588.168596"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"713","DOI":"10.2307\/2004849","volume":"24","author":"E. Berlekamp","year":"1970","unstructured":"E. Berlekamp. Factoring polynomials over large finite fields. Mathematics of Computation, Vol. 24, 1970, pp. 713\u2013735.","journal-title":"Mathematics of Computation"},{"issue":"No.4","key":"20_CR6","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, Vol. 13, No. 4, 850\u2013864, November 1984.","journal-title":"SIAM Journal on Computing"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"R. Canetti. Towards realizing random oracles: Hash functions that hide all partial information. Advances in Cryptology \u2014 Crypto 97 Proceedings, Lecture Notes in Computer Science Vol. 1294, B. Kaliski ed., Springer-Verlag, 1997.","DOI":"10.1007\/BFb0052255"},{"key":"20_CR8","unstructured":"R. Canetti, O. Goldreich and S. Halevi. The random oracle model, revisited. Proceedings of the 30th Annual Symposium on the Theory of Computing, ACM, 1998."},{"issue":"No.6","key":"20_CR9","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"IT-22","author":"W. Diffie","year":"1976","unstructured":"W. Diffie and M. Hellman. New directions in cryptography. IEEE Trans. Info. Theory, Vol. IT-22, No. 6, November 1976, pp. 644\u2013654.","journal-title":"IEEE Trans. Info. Theory"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"D. Dolev, C. Dwork, and M. Naor. Non-Malleable Cryptography. Proceedings of the 23rd Annual Symposium on the Theory of Computing, ACM, 1991.","DOI":"10.1145\/103418.103474"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T. Gamal El","year":"1985","unstructured":"T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory, Vol. 31, 1985, pp. 469\u2013472.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. Levin. A hard predicate for all one-way functions. Proceedings of the 21st Annual Symposium on the Theory of Computing, ACM, 1989.","DOI":"10.1145\/73007.73010"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, Vol. 28, April 1984, pp. 270\u2013299.","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR14","unstructured":"O. Goldreich, N. Nisan, and A. Wigderson. On Yao's XOR Lemma. Electronic Colloquium on Computational Complexity, TR95-050. March 1995. http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"20_CR15","unstructured":"J. H\u00e5stad, R. Impagliazzo, L. Levin and M. Luby. Construction of a pseudo-random generator from any one-way function. Manuscript. Earlier versions in STOC 89 and STOC 90."},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and M. Luby. One-way Functions are Essential for Complexity-Based Cryptography. Proceedings of the 30th Symposium on Foundations of Computer Science, IEEE, 1989.","DOI":"10.1109\/SFCS.1989.63483"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. Proceedings of the 21st Annual Symposium on the Theory of Computing, ACM, 1989.","DOI":"10.1145\/73007.73012"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung. Public-Key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. Proceedings of the 22nd Annual Symposium on the Theory of Computing, ACM, 1990.","DOI":"10.1145\/100216.100273"},{"key":"20_CR19","unstructured":"M. Rabin. Digitalized Signatures and Public Key Functions as Intractable as Factoring. MIT\/LCS\/TR-212, 1979."},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"A. Yao. Theory and applications of trapdoor functions. Proceedings of the 23rd Symposium on Foundations of Computer Science, IEEE, 1982.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 CRYPTO '98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T05:08:45Z","timestamp":1555736925000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648925","9783540684626"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0055735","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}