{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:07:02Z","timestamp":1750694822892,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031683879"},{"type":"electronic","value":"9783031683886"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-68388-6_1","type":"book-chapter","created":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T08:02:51Z","timestamp":1723795371000},"page":"3-13","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The One-Wayness of\u00a0Jacobi Signatures"],"prefix":"10.1007","author":[{"given":"Henry","family":"Corrigan-Gibbs","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David J.","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,17]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58691-1_70","volume-title":"Open Problems in Number Theoretic Complexity","author":"LM Adleman","year":"1994","unstructured":"Adleman, L.M., McCurley, K.S.: Open Problems in Number Theoretic Complexity. Algorithmic Number Theory, II. In (1994)"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"65","DOI":"10.2307\/1969420","volume":"55","author":"NC Ankeny","year":"1952","unstructured":"Ankeny, N.C.: The least quadratic non residue. Ann. Math. 55, 65\u201372 (1952)","journal-title":"Ann. Math."},{"issue":"191","key":"1_CR3","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1090\/S0025-5718-1990-1023756-8","volume":"55","author":"E Bach","year":"1990","unstructured":"Bach, E.: Explicit bounds for primality testing and related problems. Math. Comput. 55(191), 355\u2013380 (1990)","journal-title":"Math. Comput."},{"key":"1_CR4","unstructured":"Ball, M., Holmgren, J., Ishai, Y., Liu, T., Malkin, T.: On the complexity of decomposable randomized encodings, or: how friendly can a garbling-friendly PRF be? In: ITCS (2020)"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"313","DOI":"10.46586\/tosc.v2020.i1.313-330","volume":"2020","author":"W Beullens","year":"2020","unstructured":"Beullens, W., Beyne, T., Udovenko, A., Vitto, G.: Cryptanalysis of the Legendre PRF and generalizations. IACR Trans. Symmetric Cryptology 2020, 313\u2013330 (2020)","journal-title":"IACR Trans. Symmetric Cryptology"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00208-015-1353-2","volume":"366","author":"JW Bober","year":"2016","unstructured":"Bober, J.W., Goldmakher, L.: P\u00f3lya-Vinogradov and the least quadratic nonresidue. Mathematische Annalen 366, 853\u2013863 (2016)","journal-title":"Mathematische Annalen"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Boneh, D., Lipton, R.J.: Algorithms for black-box fields and their application to cryptography (extended abstract). In: CRYPTO (1996)","DOI":"10.1007\/3-540-68697-5_22"},{"key":"1_CR8","unstructured":"Damg\u00e5rd, I.: On the randomness of Legendre and Jacobi sequences. In: CRYPTO (1988)"},{"key":"1_CR9","unstructured":"Feist, D.: Legendre pseudo-random function (2019). https:\/\/legendreprf.org\/"},{"key":"1_CR10","first-page":"52","volume":"1","author":"P Frixons","year":"2021","unstructured":"Frixons, P., Schrottenloher, A.: Quantum security of the legendre PRF. Math. Cryptol. 1, 52\u201369 (2021)","journal-title":"Math. Cryptol."},{"key":"1_CR11","unstructured":"Fujioka, A., Okamoto, T., Miyaguchi, S.: ESIGN: an efficient digital signature implementation for smart cards. In: EUROCRYPT (1991)"},{"key":"1_CR12","doi-asserted-by":"publisher","unstructured":"Graham, S.W., Ringrose, C.: Lower bounds for least quadratic non-residues. In: Berndt, B.C., Diamond, H.G., Halberstam, H., Hildebrand, A. (eds.) Analytic Number Theory. Progress in Mathematics, vol. 85. Birkh\u00e4user Boston (1990). https:\/\/doi.org\/10.1007\/978-1-4612-3464-7_18","DOI":"10.1007\/978-1-4612-3464-7_18"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Grassi, L., Rechberger, C., Rotaru, D., Scholl, P., Smart, N.P.: MPC-friendly symmetric key primitives. In: ACM CCS (2016)","DOI":"10.1145\/2976749.2978332"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Kalujerovi\u0107, N., Kleinjung, T., Kosti\u0107, D.: Cryptanalysis of the generalised legendre pseudorandom function. In: Algorithmic Number Theory Symposium (2020)","DOI":"10.2140\/obs.2020.4.267"},{"key":"1_CR15","unstructured":"Khovratovich, D.: Key recovery attacks on the legendre PRFs within the birthday bound. IACR Cryptol. ePrint Arch. (2019)"},{"issue":"295","key":"1_CR16","doi-asserted-by":"publisher","first-page":"2391","DOI":"10.1090\/S0025-5718-2015-02925-1","volume":"84","author":"Y Lamzouri","year":"2015","unstructured":"Lamzouri, Y., Li, X., Soundararajan, K.: Conditional bounds for the least quadratic non-residue and related problems. Math. Comput. 84(295), 2391\u20132412 (2015)","journal-title":"Math. Comput."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Okamoto, T., Uchiyama, S.: A new public-key cryptosystem as secure as factoring. In: EUROCRYPT (1998)","DOI":"10.1007\/BFb0054135"},{"issue":"4","key":"1_CR18","first-page":"489","volume":"79","author":"R Peralta","year":"1996","unstructured":"Peralta, R., Okamoto, E.: Faster factoring of integers of a special form. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 79(4), 489\u2013493 (1996)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"1_CR19","doi-asserted-by":"publisher","unstructured":"Seres, I.A., Horv\u00e1th, M., Burcsi, P.: The legendre pseudorandom function as a multivariate quadratic cryptosystem: security and applications. Appl. Algebra Eng. Commun. Comput. 1\u201331 (2023). https:\/\/doi.org\/10.1007\/s00200-023-00599-2","DOI":"10.1007\/s00200-023-00599-2"},{"issue":"5","key":"1_CR20","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"PW Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Shoup, V.: A Computational Introduction to Number Theory and Algebra. Cambridge University Press (2006)","DOI":"10.1017\/CBO9781139165464"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-68388-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T08:03:27Z","timestamp":1723795407000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-68388-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031683879","9783031683886"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-68388-6_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"17 August 2024","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, CA","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":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}