{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:00:14Z","timestamp":1777964414858,"version":"3.51.4"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,4,26]],"date-time":"2016-04-26T00:00:00Z","timestamp":1461628800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00145-016-9229-5","type":"journal-article","created":{"date-parts":[[2016,4,26]],"date-time":"2016-04-26T19:56:12Z","timestamp":1461700572000},"page":"519-549","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Efficient Cryptosystems From \n                \n                  \n                \n                $$\\mathbf{2}^{{\\varvec{k}}}$$\n                \n                  \n                    \n                      \n                        2\n                      \n                      \n                        k\n                      \n                    \n                  \n                \n              -th Power Residue Symbols"],"prefix":"10.1007","volume":"30","author":[{"given":"Fabrice","family":"Benhamouda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javier","family":"Herranz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Joye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Beno\u00eet","family":"Libert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,26]]},"reference":[{"key":"9229_CR1","doi-asserted-by":"crossref","unstructured":"M.\u00a0Abdalla, F.\u00a0Ben Hamouda, and D.\u00a0Pointcheval. Tighter reductions for forward-secure signature schemes. In PKC\u00a02013, LNCS 7778, pp. 292\u2013311. Springer, February\/March 2013.","DOI":"10.1007\/978-3-642-36362-7_19"},{"key":"9229_CR2","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, Z.\u00a0Brakerski, M.\u00a0Naor, T.\u00a0Ristenpart, G.\u00a0Segev, H.\u00a0Shacham, and S.\u00a0Yilek. Hedged public-key encryption: How to protect against bad randomness. In ASIACRYPT\u00a02009, LNCS 5912, pp. 232\u2013249. Springer, December 2009.","DOI":"10.1007\/978-3-642-10366-7_14"},{"key":"9229_CR3","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, A.\u00a0Boldyreva, and A.\u00a0O\u2019Neill. Deterministic and efficiently searchable encryption. In CRYPTO\u00a02007, LNCS 4622, pp. 535\u2013552. Springer, August 2007.","DOI":"10.1007\/978-3-540-74143-5_30"},{"key":"9229_CR4","doi-asserted-by":"crossref","unstructured":"L.\u00a0Blum, M.\u00a0Blum, and M.\u00a0Shub. Comparison of two pseudo-random number generators. In CRYPTO\u201982, pp. 61\u201378. Plenum Press, New York, USA, 1982.","DOI":"10.1007\/978-1-4757-0602-4_6"},{"key":"9229_CR5","doi-asserted-by":"crossref","unstructured":"L.\u00a0Blum, M.\u00a0Blum, and M.\u00a0Shub. A simple unpredictable pseudo-random number generator. SIAM J.\u00a0Comput., 15(2):363\u2013383, 1986.","DOI":"10.1137\/0215025"},{"key":"9229_CR6","unstructured":"J.\u00a0D.\u00a0C. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale University, New Haven, CT, USA, 1987."},{"key":"9229_CR7","doi-asserted-by":"crossref","unstructured":"A.\u00a0Boldyreva, S.\u00a0Fehr, and A.\u00a0O\u2019Neill. On notions of security for deterministic encryption, and efficient constructions without random oracles. In CRYPTO\u00a02008, LNCS 5157, pp. 335\u2013359. Springer, August 2008.","DOI":"10.1007\/978-3-540-85174-5_19"},{"key":"9229_CR8","doi-asserted-by":"crossref","unstructured":"M.\u00a0Blum and S.\u00a0Goldwasser. An efficient probabilistic public-key encryption scheme which hides all partial information. In CRYPTO\u201984, LNCS 196, pp. 289\u2013302. Springer, August 1984.","DOI":"10.1007\/3-540-39568-7_23"},{"key":"9229_CR9","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, D.\u00a0Hofheinz, and S.\u00a0Yilek. Possibility and impossibility results for encryption and commitment secure under selective opening. In EUROCRYPT\u00a02009, LNCS 5479, pp. 1\u201335. Springer, April 2009.","DOI":"10.1007\/978-3-642-01001-9_1"},{"key":"9229_CR10","doi-asserted-by":"crossref","unstructured":"Z.\u00a0Brakerski and G.\u00a0Segev. Better security for deterministic public-key encryption: The auxiliary-input setting. In CRYPTO\u00a02011, LNCS 6841, pp. 543\u2013560. Springer, August 2011.","DOI":"10.1007\/978-3-642-22792-9_31"},{"key":"9229_CR11","doi-asserted-by":"crossref","unstructured":"J.\u00a0D. Cohen and M.\u00a0J. Fischer. A robust and verifiable cryptographically secure election scheme (extended abstract). In 26th FOCS, pp. 372\u2013382. IEEE Computer Society Press, October 1985.","DOI":"10.1109\/SFCS.1985.2"},{"key":"9229_CR12","doi-asserted-by":"crossref","unstructured":"D.\u00a0Catalano, R.\u00a0Gennaro, N.\u00a0Howgrave-Graham, and P.\u00a0Q. Nguyen. Paillier\u2019s cryptosystem revisited. In ACM CCS 01, pp. 206\u2013214. ACM Press, November 2001.","DOI":"10.1145\/501983.502012"},{"key":"9229_CR13","doi-asserted-by":"crossref","unstructured":"D.\u00a0Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J.\u00a0Cryptology, 10(4):233\u2013260, 1997.","DOI":"10.1007\/s001459900030"},{"key":"9229_CR14","doi-asserted-by":"crossref","unstructured":"I.\u00a0Damg\u00e5rd, M.\u00a0Jurik, and J.\u00a0B. Nielsen. A generalization of Paillier\u2019s public-key system with applications to electronic voting. Int. J. Inf. Sec., 9(6):371\u2013385, 2010.","DOI":"10.1007\/s10207-010-0119-9"},{"key":"9229_CR15","doi-asserted-by":"crossref","unstructured":"C.\u00a0Dwork, M.\u00a0Naor, O.\u00a0Reingold, and L.\u00a0Stockmeyer. Magic functions. J.\u00a0ACM, 50(6):852\u2013921, 2003.","DOI":"10.1145\/950620.950623"},{"key":"9229_CR16","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Dodis, L.\u00a0Reyzin, and A.\u00a0Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In EUROCRYPT\u00a02004, LNCS 3027, pp. 523\u2013540. Springer, May 2004.","DOI":"10.1007\/978-3-540-24676-3_31"},{"key":"9229_CR17","unstructured":"ECRYPT II. Yearly report on algorithms and keysizes, 2012."},{"key":"9229_CR18","doi-asserted-by":"crossref","unstructured":"D.\u00a0M. Freeman, O.\u00a0Goldreich, E.\u00a0Kiltz, A.\u00a0Rosen, and G.\u00a0Segev. More constructions of lossy and correlation-secure trapdoor functions. In PKC\u00a02010, LNCS 6056, pp. 279\u2013295. Springer, May 2010.","DOI":"10.1007\/978-3-642-13013-7_17"},{"key":"9229_CR19","doi-asserted-by":"crossref","unstructured":"D.\u00a0M. Freeman, O.\u00a0Goldreich, E.\u00a0Kiltz, A.\u00a0Rosen, and G.\u00a0Segev. More constructions of lossy and correlation-secure trapdoor functions. J.\u00a0Cryptology, 26(1):39\u201374, January 2013.","DOI":"10.1007\/s00145-011-9112-3"},{"key":"9229_CR20","doi-asserted-by":"crossref","unstructured":"S.\u00a0Goldwasser and S.\u00a0Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270\u2013299, 1984.","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"9229_CR21","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich. Foundations of Cryptography. Cambridge University Press, 2004.","DOI":"10.1017\/CBO9780511721656"},{"key":"9229_CR22","doi-asserted-by":"crossref","unstructured":"J.\u00a0Groth. Cryptography in subgroups of \n                    \n                      \n                    \n                    $${\\mathbb{Z}}_n$$\n                    \n                      \n                        \n                          Z\n                          n\n                        \n                      \n                    \n                  . In TCC\u00a02005, LNCS 3378, pp. 50\u201365. Springer, February 2005.","DOI":"10.1007\/978-3-540-30576-7_4"},{"key":"9229_CR23","unstructured":"J.\u00a0A. Horwitz. Applications of Cayley Graphs, Bilinearity, and Higher-Order Residues to Cryptology. PhD thesis, Stanford University, Stanford, CA, USA, 2004."},{"key":"9229_CR24","doi-asserted-by":"crossref","unstructured":"D.\u00a0Hofheinz, E.\u00a0Kiltz, and V.\u00a0Shoup. Practical chosen ciphertext secure encryption from factoring. J.\u00a0Cryptology, 26(1):102\u2013118, January 2013.","DOI":"10.1007\/s00145-011-9115-0"},{"key":"9229_CR25","doi-asserted-by":"crossref","unstructured":"B.\u00a0Hemenway and R.\u00a0Ostrovsky. Extended-DDH and lossy trapdoor functions. In PKC\u00a02012, LNCS 7293, pp. 627\u2013643. Springer, May 2012.","DOI":"10.1007\/978-3-642-30057-8_37"},{"key":"9229_CR26","doi-asserted-by":"crossref","unstructured":"K.\u00a0Ireland and M.\u00a0Rosen. A Classical Introduction to Modern Number Theory, Graduate Texts in Mathematics 84. Springer, 2nd edition, 1990.","DOI":"10.1007\/978-1-4757-2103-4"},{"key":"9229_CR27","unstructured":"ISO\/IEC 18033-2. Information technology \u2013 Security techniques \u2013 Encryption algorithms \u2013 Part 2: Asymmetric ciphers. International Organization for Standardization, May 2006."},{"key":"9229_CR28","doi-asserted-by":"crossref","unstructured":"M.\u00a0Joye and P.\u00a0Paillier. Fast generation of prime numbers on portable devices: An update. In CHES\u00a02006, LNCS 4249, pp. 160\u2013173. Springer, October 2006.","DOI":"10.1007\/11894063_13"},{"key":"9229_CR29","doi-asserted-by":"crossref","unstructured":"M.\u00a0Joye, P.\u00a0Paillier, and S.\u00a0Vaudenay. Efficient generation of prime numbers. In CHES\u00a02000, LNCS 1965, pp. 340\u2013354. Springer, August 2000.","DOI":"10.1007\/3-540-44499-8_27"},{"key":"9229_CR30","doi-asserted-by":"crossref","unstructured":"K.\u00a0Kurosawa, Y.\u00a0Katayama, W.\u00a0Ogata, and S.\u00a0Tsujii. General public key residue cryptosystems and mental poker protocols. In EUROCRYPT\u201990, LNCS 473, pp. 374\u2013388. Springer, May 1990.","DOI":"10.1007\/3-540-46877-3_34"},{"key":"9229_CR31","doi-asserted-by":"crossref","unstructured":"J.\u00a0Katz and Y.\u00a0Lindell. Introduction to Modern Cryptography. CRC Press, 2007.","DOI":"10.1201\/9781420010756"},{"key":"9229_CR32","doi-asserted-by":"crossref","unstructured":"E.\u00a0Kiltz, A.\u00a0O\u2019Neill, and A.\u00a0Smith. Instantiability of RSA-OAEP under chosen-plaintext attack. In CRYPTO\u00a02010, LNCS 6223, pp. 295\u2013313. Springer, August 2010.","DOI":"10.1007\/978-3-642-14623-7_16"},{"key":"9229_CR33","doi-asserted-by":"crossref","unstructured":"E.\u00a0Kiltz, K.\u00a0Pietrzak, M.\u00a0Stam, and M.\u00a0Yung. A new randomness extraction paradigm for hybrid encryption. In EUROCRYPT\u00a02009, LNCS 5479, pp. 590\u2013609. Springer, April 2009.","DOI":"10.1007\/978-3-642-01001-9_34"},{"key":"9229_CR34","doi-asserted-by":"crossref","unstructured":"F.\u00a0Lemmermeyer. Reciprocity Laws. Springer Monographs in Mathematics. Springer, 2000.","DOI":"10.1007\/978-3-662-12893-0"},{"key":"9229_CR35","doi-asserted-by":"crossref","unstructured":"J.\u00a0Monnerat and S.\u00a0Vaudenay. Generic homomorphic undeniable signatures. In ASIACRYPT\u00a02004, LNCS 3329, pp. 354\u2013371. Springer, December 2004.","DOI":"10.1007\/978-3-540-30539-2_25"},{"key":"9229_CR36","doi-asserted-by":"crossref","unstructured":"J.\u00a0Monnerat and S.\u00a0Vaudenay. Undeniable signatures based on characters: How to sign with one bit. In PKC\u00a02004, LNCS 2947, pp. 69\u201385. Springer, March 2004.","DOI":"10.1007\/978-3-540-24632-9_6"},{"key":"9229_CR37","doi-asserted-by":"crossref","unstructured":"P.\u00a0Mol and S.\u00a0Yilek. Chosen-ciphertext security from slightly lossy trapdoor functions. In PKC\u00a02010, LNCS 6056, pp. 296\u2013311. Springer, May 2010.","DOI":"10.1007\/978-3-642-13013-7_18"},{"key":"9229_CR38","doi-asserted-by":"crossref","unstructured":"P.\u00a0Q. Nguyen. Public-key cryptanalysis. In Recent Trends in Cryptography, Contemporary Mathematics. AMS\u2013RSME, 2009.","DOI":"10.1090\/conm\/477\/09304"},{"key":"9229_CR39","doi-asserted-by":"crossref","unstructured":"D.\u00a0Naccache and J.\u00a0Stern. A new public key cryptosystem based on higher residues. In ACM CCS 98, pp. 59\u201366. ACM Press, November 1998.","DOI":"10.1145\/288090.288106"},{"key":"9229_CR40","doi-asserted-by":"crossref","unstructured":"T.\u00a0Okamoto and D.\u00a0Pointcheval. The gap-problems: A new class of problems for the security of cryptographic schemes. In PKC\u00a02001, LNCS 1992, pp. 104\u2013118. Springer, February 2001.","DOI":"10.1007\/3-540-44586-2_8"},{"key":"9229_CR41","doi-asserted-by":"crossref","unstructured":"T.\u00a0Okamoto and S.\u00a0Uchiyama. A new public-key cryptosystem as secure as factoring. In EUROCRYPT\u201998, LNCS 1403, pp. 308\u2013318. Springer, May\/June 1998.","DOI":"10.1007\/BFb0054135"},{"key":"9229_CR42","doi-asserted-by":"crossref","unstructured":"P.\u00a0Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT\u201999, LNCS 1592, pp. 223\u2013238. Springer, May 1999.","DOI":"10.1007\/3-540-48910-X_16"},{"key":"9229_CR43","doi-asserted-by":"crossref","unstructured":"S.\u00a0H. Pohlig and M.\u00a0E. Hellman. An improved algorithm for computing logarithms over \n                    \n                      \n                    \n                    $${\\rm GF}(p)$$\n                    \n                      \n                        \n                          GF\n                          (\n                          p\n                          )\n                        \n                      \n                    \n                   and its cryptographic significance. IEEE Tran. Inf. Theory, 24(1):106\u2013110, 1978.","DOI":"10.1109\/TIT.1978.1055817"},{"key":"9229_CR44","unstructured":"S.\u00a0J. Park, B.\u00a0Y. Lee, and D.\u00a0H. Won. A probabilistic encryption using very high residuosity and its applications. In Global Telecommunications Conference (GLOBECOM\u00a0\u201995), pp. 1179\u20131182. IEEE Press, 1995."},{"key":"9229_CR45","doi-asserted-by":"crossref","unstructured":"C.\u00a0Peikert and B.\u00a0Waters. Lossy trapdoor functions and their applications. In 40th ACM STOC, pp. 187\u2013196. ACM Press, May 2008.","DOI":"10.1145\/1374376.1374406"},{"key":"9229_CR46","doi-asserted-by":"crossref","unstructured":"O.\u00a0Regev. On lattices, learning with errors, random linear codes, and cryptography. J.\u00a0ACM, 56(6), 2009. Earlier version in STOC\u00a02005.","DOI":"10.1145\/1568318.1568324"},{"key":"9229_CR47","doi-asserted-by":"crossref","unstructured":"R.\u00a0Scheidler. A public-key cryptosystem using purely cubic fields. J.\u00a0Cryptology, 11(2):109\u2013124, 1998.","DOI":"10.1007\/s001459900038"},{"key":"9229_CR48","unstructured":"V.\u00a0Shoup. A Computational Introduction to Number Theory and Algebra. Cambridge University Press, 2nd edition, 2010."},{"key":"9229_CR49","doi-asserted-by":"crossref","unstructured":"R.\u00a0Scheidler and H.\u00a0C. Williams. A public-key cryptosystem utilizing cyclotomic fields. Des. Codes Cryptography, 6(2):117\u2013131, 1995.","DOI":"10.1007\/BF01398010"},{"key":"9229_CR50","doi-asserted-by":"crossref","unstructured":"H.\u00a0Wee. Dual projective hashing and its applications - lossy trapdoor functions and more. In EUROCRYPT\u00a02012, LNCS 7237, pp. 246\u2013262. Springer, April 2012.","DOI":"10.1007\/978-3-642-29011-4_16"},{"key":"9229_CR51","doi-asserted-by":"crossref","unstructured":"S.\u00a0Y. Yan. Number Theory for Computing. Springer, 2nd edition, 2002.","DOI":"10.1007\/978-3-662-04773-6"},{"key":"9229_CR52","unstructured":"Y.\u00a0Zheng, T.\u00a0Matsumoto, and H.\u00a0Imai. Residuosity problem and its applications to cryptography. Trans. IEICE, E-71(8):759\u2013767, 1988."}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9229-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-016-9229-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9229-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9229-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:15:05Z","timestamp":1586333705000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-016-9229-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,26]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["9229"],"URL":"https:\/\/doi.org\/10.1007\/s00145-016-9229-5","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,26]]},"assertion":[{"value":"29 April 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2015","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}