{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T16:10:30Z","timestamp":1768925430118,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662530078","type":"print"},{"value":"9783662530085","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53008-5_1","type":"book-chapter","created":{"date-parts":[[2016,7,20]],"date-time":"2016-07-20T10:10:14Z","timestamp":1469009414000},"page":"3-32","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Adversary-Dependent Lossy Trapdoor Function from Hardness of Factoring Semi-smooth RSA Subgroup Moduli"],"prefix":"10.1007","author":[{"given":"Takashi","family":"Yamakawa","sequence":"first","affiliation":[]},{"given":"Shota","family":"Yamada","sequence":"additional","affiliation":[]},{"given":"Goichiro","family":"Hanaoka","sequence":"additional","affiliation":[]},{"given":"Noboru","family":"Kunihiro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,7,21]]},"reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/978-3-540-74143-5_30","volume-title":"Advances in Cryptology \u2013 CRYPTO 2007","author":"M Bellare","year":"2007","unstructured":"Bellare, M., Boldyreva, A., O\u2019Neill, A.: Deterministic and efficiently searchable encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 535\u2013552. Springer, Heidelberg (2007)"},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-540-85174-5_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"M Bellare","year":"2008","unstructured":"Bellare, M., Fischlin, M., O\u2019Neill, A., Ristenpart, T.: Deterministic encryption: definitional equivalences and constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 360\u2013378. Springer, Heidelberg (2008)"},{"key":"1_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-01001-9_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2009","author":"M Bellare","year":"2009","unstructured":"Bellare, M., Hofheinz, D., Yilek, S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 1\u201335. Springer, Heidelberg (2009)"},{"issue":"2","key":"1_CR4","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0215025","volume":"15","author":"L Blum","year":"1986","unstructured":"Blum, L., Blum, M., Shub, M.: A simple unpredictable pseudo-random number generator. SIAM J. Comput. 15(2), 364\u2013383 (1986)","journal-title":"SIAM J. Comput."},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-540-85174-5_19","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"A Boldyreva","year":"2008","unstructured":"Boldyreva, A., Fehr, S., O\u2019Neill, A.: On notions of security for deterministic encryption, and efficient constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 335\u2013359. Springer, Heidelberg (2008)"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1007\/3-540-68339-9_16","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 1996","author":"D Coppersmith","year":"1996","unstructured":"Coppersmith, D.: Finding a small root of a bivariate integer equation; factoring with high bits known. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 178\u2013189. Springer, Heidelberg (1996)"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-642-19379-8_9","volume-title":"Public Key Cryptography \u2013 PKC 2011","author":"J-S Coron","year":"2011","unstructured":"Coron, J.-S., Joux, A., Mandal, A., Naccache, D., Tibouchi, M.: Cryptanalysis of the RSA subgroup assumption from TCC 2005. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 147\u2013155. Springer, Heidelberg (2011)"},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/3-540-46035-7_4","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2002","author":"R Cramer","year":"2002","unstructured":"Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45\u201364. Springer, Heidelberg (2002)"},{"key":"1_CR9","volume-title":"Prime Numbers: A Computational Perspective","author":"R Crandall","year":"2005","unstructured":"Crandall, R., Pomerance, C.: Prime Numbers: A Computational Perspective, 2nd edn. Springer, New York (2005)","edition":"2"},{"issue":"1","key":"1_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1137\/060651380","volume":"38","author":"Y Dodis","year":"2008","unstructured":"Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97\u2013139 (2008)","journal-title":"SIAM J. Comput."},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-13013-7_17","volume-title":"Public Key Cryptography \u2013 PKC 2010","author":"DM Freeman","year":"2010","unstructured":"Freeman, D.M., Goldreich, O., Kiltz, E., Rosen, A., Segev, G.: More constructions of lossy and correlation-secure trapdoor functions. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 279\u2013295. Springer, Heidelberg (2010)"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: STOC, pp. 25\u201332 (1989)","DOI":"10.1145\/73007.73010"},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-30576-7_4","volume-title":"Theory of Cryptography","author":"J Groth","year":"2005","unstructured":"Groth, J.: Cryptography in subgroups of $$Z_n^*$$. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 50\u201365. Springer, Heidelberg (2005)"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1007\/978-3-642-32009-5_47","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"G Hanaoka","year":"2012","unstructured":"Hanaoka, G., Matsuda, T., Schuldt, J.C.N.: On the impossibility of constructing efficient key encapsulation and programmable hash functions in prime order groups. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 812\u2013831. Springer, Heidelberg (2012)"},{"issue":"301","key":"1_CR15","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/978-3-540-74143-5_31","volume-title":"Advances in Cryptology \u2013 CRYPTO 2007","author":"D Hofheinz","year":"2007","unstructured":"Hofheinz, D., Kiltz, E.: Secure hybrid encryption from weakened key encapsulation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 553\u2013571. Springer, Heidelberg (2007)"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/978-3-642-03356-8_37","volume-title":"Advances in Cryptology \u2013 CRYPTO 2009","author":"D Hofheinz","year":"2009","unstructured":"Hofheinz, D., Kiltz, E.: The group of signed quadratic residues and applications. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 637\u2013653. Springer, Heidelberg (2009)"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-642-01001-9_18","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2009","author":"D Hofheinz","year":"2009","unstructured":"Hofheinz, D., Kiltz, E.: Practical chosen ciphertext secure encryption from factoring. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 313\u2013332. Springer, Heidelberg (2009)"},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/978-3-642-13190-5_34","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"E Kiltz","year":"2010","unstructured":"Kiltz, E., Mohassel, P., O\u2019Neill, A.: Adaptive trapdoor functions and chosen-ciphertext security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 673\u2013692. Springer, Heidelberg (2010)"},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-14623-7_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"E Kiltz","year":"2010","unstructured":"Kiltz, E., O\u2019Neill, A., Smith, A.: Instantiability of RSA-OAEP under chosen-plaintext attack. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 295\u2013313. Springer, Heidelberg (2010)"},{"key":"1_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1007\/978-3-642-01001-9_34","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2009","author":"E Kiltz","year":"2009","unstructured":"Kiltz, E., Pietrzak, K., Stam, M., Yung, M.: A new randomness extraction paradigm for hybrid encryption. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 590\u2013609. Springer, Heidelberg (2009)"},{"issue":"3","key":"1_CR22","doi-asserted-by":"publisher","first-page":"649","DOI":"10.2307\/1971363","volume":"126","author":"HW Lenstra Jr","year":"1987","unstructured":"Lenstra Jr., H.W.: Factoring integers with elliptic curves. Ann. Math. 126(3), 649\u2013673 (1987)","journal-title":"Ann. Math."},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-41227-1_14","volume-title":"Provable Security","author":"X Lu","year":"2013","unstructured":"Lu, X., Li, B., Liu, Y.: How to remove the exponent GCD in HK09. In: Susilo, W., Reyhanitabar, R. (eds.) ProvSec 2013. LNCS, vol. 8209, pp. 239\u2013248. Springer, Heidelberg (2013)"},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-29101-2_3","volume-title":"Information Security Practice and Experience","author":"X Lu","year":"2012","unstructured":"Lu, X., Li, B., Mei, Q., Liu, Y.: Improved efficiency of chosen ciphertext secure encryption from factoring. In: Ryan, M.D., Smyth, B., Wang, G. (eds.) ISPEC 2012. LNCS, vol. 7232, pp. 34\u201345. Springer, Heidelberg (2012)"},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-642-19379-8_13","volume-title":"Public Key Cryptography \u2013 PKC 2011","author":"Q Mei","year":"2011","unstructured":"Mei, Q., Li, B., Lu, X., Jia, D.: Chosen ciphertext secure encryption under factoring assumption revisited. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 210\u2013227. Springer, Heidelberg (2011)"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Naccache, D., Stern, J.: A new public key cryptosystem based on higher residues. In: ACM Conference on Computer and Communications Security, pp. 59\u201366 (1998)","DOI":"10.1145\/288090.288106"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: STOC, pp. 187\u2013196 (2008)","DOI":"10.1145\/1374376.1374406"},{"issue":"1","key":"1_CR28","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/TIT.1978.1055817","volume":"24","author":"SC Pohlig","year":"1978","unstructured":"Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over gf(p) and its cryptographic significance (corresp.). IEEE Trans. Inf. Theor. 24(1), 106\u2013110 (1978)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"3","key":"1_CR29","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1017\/S0305004100049252","volume":"76","author":"J. M. Pollard","year":"1974","unstructured":"Pollard, J.M.: Theorems of factorization and primality testing. In: Proceedings of the cambridge philosophical society, vol. 76, pp. 521\u2013528 (1974)","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01933667","volume":"15","author":"JM Pollard","year":"1975","unstructured":"Pollard, J.M.: A monte carlo method for factorization. BIT 15, 331\u2013334 (1975)","journal-title":"BIT"},{"key":"1_CR31","first-page":"918","volume":"32","author":"JM Pollard","year":"1978","unstructured":"Pollard, J.M.: Monte Carlo methods for index computation (mod p). Math. Comput. 32, 918\u2013924 (1978)","journal-title":"Math. Comput."},{"key":"1_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-642-38348-9_6","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"A Raghunathan","year":"2013","unstructured":"Raghunathan, A., Segev, G., Vadhan, S.: Deterministic public-key encryption for adaptively chosen plaintext distributions. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 93\u2013110. Springer, Heidelberg (2013)"},{"key":"1_CR33","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005, pp. 84\u201393 (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Shanks, D.: Class number, a theory of factorization, and genera. In: 1969 Number Theory Institute (Proceedings of the Symposium Pure Mathematics, vol. XX, State University New York, Stony Brook, N.Y., 1969), pp. 415\u2013440, Providence, R.I (1971)","DOI":"10.1090\/pspum\/020\/0316385"},{"key":"1_CR35","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Vadhan, S.P.: Extracting randomness from samplable distributions. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12\u201314 November 2000, Redondo Beach, California, USA, pp. 32\u201342 (2000)","DOI":"10.1109\/SFCS.2000.892063"},{"key":"1_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-319-02937-5_13","volume-title":"Cryptology and Network Security","author":"H Xue","year":"2013","unstructured":"Xue, H., Li, B., Lu, X., Jia, D., Liu, Y.: Efficient lossy trapdoor functions based on subgroup membership assumptions. In: Abdalla, M., Nita-Rotaru, C., Dahab, R. (eds.) CANS 2013. LNCS, vol. 8257, pp. 235\u2013250. Springer, Heidelberg (2013)"},{"key":"1_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1007\/978-3-319-10879-7_32","volume-title":"Security and Cryptography for Networks","author":"T Yamakawa","year":"2014","unstructured":"Yamakawa, T., Yamada, S., Nuida, K., Hanaoka, G., Kunihiro, N.: Chosen ciphertext security on hard membership decision groups: the case of semi-smooth subgroups of quadratic residues. In: Abdalla, M., De Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 558\u2013577. Springer, Heidelberg (2014)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2016"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53008-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T02:59:31Z","timestamp":1749005971000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53008-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662530078","9783662530085"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53008-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"21 July 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 August 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"36","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}