{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,15]],"date-time":"2026-08-15T20:34:40Z","timestamp":1786826080694,"version":"build-2736575974"},"reference-count":80,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,3,1]],"date-time":"2023-03-01T00:00:00Z","timestamp":1677628800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,1]],"date-time":"2023-03-01T00:00:00Z","timestamp":1677628800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009934","name":"E\u00f6tv\u00f6s Lor\u00e1nd University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009934","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Sequences of consecutive Legendre and Jacobi symbols as pseudorandom bit generators were proposed for cryptographic use in 1988. Major interest has been shown towards pseudorandom functions (PRF) recently, based on the Legendre and power residue symbols, due to their efficiency in the multi-party setting. The security of these PRFs is not known to be reducible to standard cryptographic assumptions. In this work, we show that key-recovery attacks against the Legendre PRF are equivalent to solving a specific family of multivariate quadratic (MQ) equation system over a finite prime field. This new perspective sheds some light on the complexity of key-recovery attacks against the Legendre PRF. We conduct algebraic cryptanalysis on the resulting MQ instance. We show that the currently known techniques and attacks fall short in solving these sparse quadratic equation systems. Furthermore, we build novel cryptographic applications of the Legendre PRF, e.g., verifiable random function and (verifiable) oblivious (programmable) PRFs.<\/jats:p>","DOI":"10.1007\/s00200-023-00599-2","type":"journal-article","created":{"date-parts":[[2023,3,1]],"date-time":"2023-03-01T03:02:40Z","timestamp":1677639760000},"page":"223-253","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["The Legendre pseudorandom function as a multivariate quadratic cryptosystem: security and applications"],"prefix":"10.1007","volume":"36","author":[{"given":"Istv\u00e1n Andr\u00e1s","family":"Seres","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M\u00e1t\u00e9","family":"Horv\u00e1th","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"P\u00e9ter","family":"Burcsi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,3,1]]},"reference":[{"key":"599_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.46586\/tosc.v2020.i3.1-45","volume":"2020","author":"A Aly","year":"2020","unstructured":"Aly, A., Ashur, T., Ben-Sasson, E., Dhooghe, S., Szepieniec, A.: Design of symmetric-key primitives for advanced cryptographic protocols. IACR Trans. Symmetric Cryptol. 2020, 1\u201345 (2020). https:\/\/www.iacr.org\/cryptodb\/data\/paper.php?pubkey=30562","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"599_CR2","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Cid, C., Grassi, L., Khovratovich, D., L\u00fcftenegger, R., Rechberger, C., Schofnegger, M.: Algebraic cryptanalysis of stark-friendly designs: application to marvellous and MIMC. In: ASIACRYPT (3), vol. 11923 of Lecture Notes in Computer Science, pp. 371\u2013397. Springer (2019)","DOI":"10.1007\/978-3-030-34618-8_13"},{"key":"599_CR3","unstructured":"Ashur, T., Dhooghe, S.: Marvellous: a stark-friendly family of cryptographic primitives. IACR Cryptol. ePrint Arch. 2018, 1098 (2018)"},{"key":"599_CR4","unstructured":"Albrecht, M.R., Davidson, A., Deo, A., Smart, N.P.: Round-optimal verifiable oblivious pseudorandom functions from ideal lattices. IACR Cryptol. ePrint Arch. 2019, 1271 (2019)"},{"key":"599_CR5","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Davidson, A., Deo, A., Smart, N.P.: Round-optimal verifiable oblivious pseudorandom functions from ideal lattices. In: Public Key Cryptography (2), vol. 12711, Lecture Notes in Computer Science, pp. 261\u2013289. Springer (2021)","DOI":"10.1007\/978-3-030-75248-4_10"},{"key":"599_CR6","doi-asserted-by":"crossref","unstructured":"Albrecht, M., Grassi, L., Rechberger, C., Roy, A., Tiessen, T.: MIMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 191\u2013219. Springer (2016)","DOI":"10.1007\/978-3-662-53887-6_7"},{"key":"599_CR7","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: EUROCRYPT (1), vol. 9056, Lecture Notes in Computer Science, pp. 430\u2013454. Springer (2015)","DOI":"10.1007\/978-3-662-46800-5_17"},{"key":"599_CR8","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 Cryptol. 2020, 313\u2013330 (2020)","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"599_CR9","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., D\u00f6ttling, N.: Two-message statistically sender-private OT from LWE. In: TCC (2), vol. 11240, Lecture Notes in Computer Science, pp. 370\u2013390. Springer (2018)","DOI":"10.1007\/978-3-030-03810-6_14"},{"key":"599_CR10","doi-asserted-by":"crossref","unstructured":"Buser, M., Dowsley, R., Esgin, M.F., Kermanshahi, S.K., Kuchta, V., Liu, J.K., Phan, R., Zhang, Z.: Post-quantum verifiable random function from symmetric primitives in pos blockchain. IACR Cryptol. ePrint Arch. 302 (2021)","DOI":"10.1007\/978-3-031-17140-6_2"},{"key":"599_CR11","doi-asserted-by":"crossref","unstructured":"Beullens, W., de\u00a0Saint Guilhem C.D.: Legroast: Efficient post-quantum signatures from the Legendre PRF. In: International Conference on Post-Quantum Cryptography, pp. 130\u2013150. Springer (2020)","DOI":"10.1007\/978-3-030-44223-1_8"},{"key":"599_CR12","unstructured":"Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: Providing sound foundations for cryptography: on the work of Shafi Goldwasser and Silvio Micali, pp. 329\u2013349. (2019)"},{"key":"599_CR13","unstructured":"Bardet, M., Faugere, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: Proceedings of MEGA, vol. 5 (2005)"},{"key":"599_CR14","doi-asserted-by":"crossref","unstructured":"Badrinarayanan, S., Garg, S., Ishai, Y., Sahai, A., Wadia, A.: Two-message witness indistinguishability and secure computation in the plain model from new assumptions. In: ASIACRYPT (3), vol. 10626, Lecture Notes in Computer Science, pp. 275\u2013303. Springer (2017)","DOI":"10.1007\/978-3-319-70700-6_10"},{"key":"599_CR15","doi-asserted-by":"crossref","unstructured":"Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 416\u2013432. Springer (2003)","DOI":"10.1007\/3-540-39200-9_26"},{"key":"599_CR16","unstructured":"Ben-Sasson, E, Bentov, I, Horesh, Y, Riabzev, M: Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptol. ePrint Arch. 2018, 46 (2018)"},{"key":"599_CR17","unstructured":"Buchberger, B.: Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal. PhD thesis, Universitat Insbruck (1965)"},{"key":"599_CR18","doi-asserted-by":"crossref","unstructured":"Chandran, N., Gupta, D., Shah, A.: Circuit-PSI with linear complexity via relaxed batch opprf. In: 22nd Privacy Enhancing Technologies Symposium (PETS 2022), June (2022)","DOI":"10.2478\/popets-2022-0018"},{"key":"599_CR19","doi-asserted-by":"crossref","unstructured":"Canetti, R., Jain, A., Scafuro, A.: Practical UC security with a global random oracle. In: CCS, pp. 597\u2013608. ACM (2014)","DOI":"10.1145\/2660267.2660374"},{"key":"599_CR20","doi-asserted-by":"crossref","unstructured":"Chase, M., Lysyanskaya, A.: Simulatable VRFS with applications to multi-theorem NIZK. In: CRYPTO, vol. 4622, Lecture Notes in Computer Science, pp. 303\u2013322. Springer (2007)","DOI":"10.1007\/978-3-540-74143-5_17"},{"key":"599_CR21","unstructured":"Cox, D., Little, J., OShea, D.: Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media (2013)"},{"key":"599_CR22","doi-asserted-by":"crossref","unstructured":"Chase, M., Meiklejohn, S., Zaverucha, G.: Algebraic MACs and keyed-verification anonymous credentials. In: CCS, pp. 1205\u20131216. ACM (2014)","DOI":"10.1145\/2660267.2660328"},{"key":"599_CR23","unstructured":"Cascudo, I, Schnyder, R: A note on secure multiparty computation via higher residue symbol techniques. IACR Cryptol. ePrint Arch. 2020, 183 (2020)"},{"key":"599_CR24","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I.: On the randomness of Legendre and Jacobi sequences. In: CRYPTO, vol. 403, Lecture Notes in Computer Science, pp. 163\u2013172. Springer (1988)","DOI":"10.1007\/0-387-34799-2_13"},{"issue":"1","key":"599_CR25","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1112\/jlms\/s1-6.1.49","volume":"1","author":"Harold Davenport","year":"1931","unstructured":"Davenport, Harold: On the distribution of quadratic residues (mod p). J. Lond. Math. Soc. 1(1), 49\u201354 (1931)","journal-title":"J. Lond. Math. Soc."},{"key":"599_CR26","unstructured":"D\u00e9chene, I.: Generalized Jacobians in cryptography. ProQuest (2007)"},{"key":"599_CR27","unstructured":"Davidson, A., Faz-Hern\u00e1ndez, A., Sullivan, N., Wood, C.: Oblivious pseudorandom functions (OPRFs) using prime-order groups (2021). https:\/\/datatracker.ietf.org\/doc\/draft-irtf-cfrg-voprf\/"},{"issue":"3","key":"599_CR28","first-page":"164","volume":"2018","author":"Alex Davidson","year":"2018","unstructured":"Davidson, Alex, Goldberg, Ian, Sullivan, Nick, Tankersley, George, Valsorda, Filippo: Privacy pass: bypassing internet challenges anonymously. Proc. Priv. Enhanc. Technol. 2018(3), 164\u2013180 (2018)","journal-title":"Proc. Priv. Enhanc. Technol."},{"issue":"3","key":"599_CR29","doi-asserted-by":"publisher","first-page":"1276","DOI":"10.1109\/18.669398","volume":"44","author":"Cunsheng Ding","year":"1998","unstructured":"Ding, Cunsheng, Helleseth, Tor, Shan, Weijuan: On the linear complexity of Legendre sequences. IEEE Trans. Inf. Theory 44(3), 1276\u20131278 (1998)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"599_CR30","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Kiltz, E., Pietrzak, K., Wichs, D.: Message authentication, revisited. In: EUROCRYPT, vol. 7237, Lecture Notes in Computer Science, pp. 355\u2013374. Springer (2012)","DOI":"10.1007\/978-3-642-29011-4_22"},{"key":"599_CR31","doi-asserted-by":"crossref","unstructured":"Demmler, D, Schneider, T, Zohner, M: ABY\u2014 a framework for efficient mixed-protocol secure two-party computation. The Internet Society, In NDSS (2015)","DOI":"10.14722\/ndss.2015.23113"},{"key":"599_CR32","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Yampolskiy, A.: A verifiable random function with short proofs and keys. In: Public Key Cryptography, vol. 3386 of Lecture Notes in Computer Science, pp. 416\u2013431. Springer (2005)","DOI":"10.1007\/978-3-540-30580-4_28"},{"key":"599_CR33","doi-asserted-by":"crossref","unstructured":"Esgin, M.F., Kuchta, V., Sakzad, A., Steinfeld, R., Zhang, Z., Sun, S., Chu, S.: Practical post-quantum few-time verifiable random function with applications to Algorand. IACR Cryptol. ePrint Arch. 2020, 1222 (2020)","DOI":"10.1007\/978-3-662-64331-0_29"},{"key":"599_CR34","doi-asserted-by":"crossref","unstructured":"Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: TCC, vol. 3378, Lecture Notes in Computer Science, pp. 303\u2013324. Springer (2005)","DOI":"10.1007\/978-3-540-30576-7_17"},{"key":"599_CR35","unstructured":"Frixons, P., Schrottenloher, A.: Quantum security of the Legendre PRF. IACR Cryptol. ePrint Arch. 149 (2021)"},{"key":"599_CR36","doi-asserted-by":"crossref","unstructured":"Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: SOSP, pp. 51\u201368. ACM (2017)","DOI":"10.1145\/3132747.3132757"},{"key":"599_CR37","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, San Francisco. W.H. Freeman, CA (1979)"},{"key":"599_CR38","unstructured":"Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: a new hash function for zero-knowledge proof systems. In: USENIX Security Symposium, pp. 519\u2013535. USENIX Association (2021)"},{"key":"599_CR39","doi-asserted-by":"crossref","unstructured":"Gyarmati, Katalin, Mauduit, Christian, S\u00e1rk\u00f6zy, Andr\u00e1s: The cross-correlation measure for families of binary sequences. Applied Algebra and Number Theory, pp. 126\u2013143. Cambridge University Press (2014)","DOI":"10.1017\/CBO9781139696456.009"},{"key":"599_CR40","doi-asserted-by":"crossref","unstructured":"Goldberg, S., Naor, M., Papadopoulos, D., Reyzin, L., Vasant, S., Ziv, A.: Nsec5: provably preventing DNSSEC zone enumeration. In: The Network and Distributed System Security (NDSS) Symposium, CA, San Diego (2015)","DOI":"10.14722\/ndss.2015.23211"},{"key":"599_CR41","doi-asserted-by":"crossref","unstructured":"Goldberg, S., Naor, M., Papadopoulos, D., Reyzin, L.: NSEC5 from elliptic curves: provably preventing dnssec zone enumeration with shorter responses. Cryptol. ePrint Arch. Report 2016\/083 (2016). https:\/\/ia.cr\/2016\/083","DOI":"10.14722\/ndss.2015.23211"},{"key":"599_CR42","doi-asserted-by":"crossref","unstructured":"Groth, J.: On the size of pairing-based non-interactive arguments. In: EUROCRYPT (2), vol. 9666, Lecture Notes in Computer Science, pp. 305\u2013326. Springer (2016)","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"599_CR43","doi-asserted-by":"crossref","unstructured":"Grassi, L., Rechberger, C., Rotaru, D., Scholl, P., Smart, N.P.: MPC-friendly symmetric key primitives. In: CCS, pp. 430\u2013443. ACM (2016)","DOI":"10.1145\/2976749.2978332"},{"key":"599_CR44","unstructured":"Hartshorne, R.: Algebraic Geometry, vol.\u00a052. Springer Science & Business Media (2013)"},{"issue":"3","key":"599_CR45","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/s00145-008-9034-x","volume":"23","author":"Carmit Hazay","year":"2010","unstructured":"Hazay, Carmit, Lindell, Yehuda: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. J. Cryptol. 23(3), 422\u2013456 (2010)","journal-title":"J. Cryptol."},{"key":"599_CR46","doi-asserted-by":"crossref","unstructured":"Huang, Y.-J., Liu, F.-H., Yang, B.-Y.: Public-key cryptography from new multivariate quadratic assumptions. In: International Workshop on Public Key Cryptography, pp. 190\u2013205. Springer (2012)","DOI":"10.1007\/978-3-642-30057-8_12"},{"key":"599_CR47","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A.: Efficient non-interactive secure computation. In: EUROCRYPT, vol. 6632, Lecture Notes in Computer Science, pp. 406\u2013425. Springer (2011)","DOI":"10.1007\/978-3-642-20465-4_23"},{"key":"599_CR48","doi-asserted-by":"crossref","unstructured":"Jakobsen, T., Knudsen, L.: The interpolation attack on block ciphers. In: International Workshop on Fast Software Encryption, pp. 28\u201340. Springer (1997)","DOI":"10.1007\/BFb0052332"},{"key":"599_CR49","doi-asserted-by":"crossref","unstructured":"Jarecki, S., Kiayias, A., Krawczyk, H.: Round-optimal password-protected secret sharing and T-PAKE in the password-only model. In: ASIACRYPT (2), vol. 8874, Lecture Notes in Computer Science, pp. 233\u2013253. Springer (2014)","DOI":"10.1007\/978-3-662-45608-8_13"},{"key":"599_CR50","doi-asserted-by":"crossref","unstructured":"Jarecki, S., Kiayias, A., Krawczyk, H., Xu, J.: Highly-efficient and composable password-protected secret sharing (or: how to protect your bitcoin wallet online). In: 2016 IEEE European Symposium on Security and Privacy (EuroS &P), pp. 276\u2013291. IEEE (2016)","DOI":"10.1109\/EuroSP.2016.30"},{"key":"599_CR51","doi-asserted-by":"crossref","unstructured":"Jarecki, S., Krawczyk, H., Xu, J.: Opaque: an asymmetric PAKE protocol secure against pre-computation attacks. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 456\u2013486. Springer (2018)","DOI":"10.1007\/978-3-319-78372-7_15"},{"key":"599_CR52","doi-asserted-by":"crossref","unstructured":"Jarecki, S., Liu, X.: Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection. In: TCC, vol. 5444, Lecture Notes in Computer Science, pp. 577\u2013594. Springer (2009)","DOI":"10.1007\/978-3-642-00457-5_34"},{"key":"599_CR53","unstructured":"Keelveedhi, S., Bellare, M., Ristenpart, T.: Dupless: server-aided encryption for deduplicated storage. In: 22nd $$\\{$$USENIX$$\\}$$ Security Symposium ($$\\{$$USENIX$$\\}$$ Security 13), pp. 179\u2013194. (2013)"},{"key":"599_CR54","unstructured":"Khovratovich, D.: Key recovery attacks on the Legendre PRFS within the birthday bound. Cryptol. ePrint Arch. Report 2019\/862 (2019)"},{"key":"599_CR55","doi-asserted-by":"crossref","unstructured":"Karako\u00e7, F., K\u00fcp\u00e7\u00fc, A.: Linear complexity private set intersection for secure two-party protocols. In: CANS, vol. 12579, Lecture Notes in Computer Science, pp. 409\u2013429. Springer (2020)","DOI":"10.1007\/978-3-030-65411-5_20"},{"key":"599_CR56","unstructured":"Kaluderovic, N, Kleinjung, T, Kostic, D: Improved key recovery on the Legendre PRF. IACR Cryptol. ePrint Arch. 2020, 98 (2020)"},{"key":"599_CR57","doi-asserted-by":"crossref","unstructured":"Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: CCS, pp. 818\u2013829. ACM (2016)","DOI":"10.1145\/2976749.2978381"},{"key":"599_CR58","first-page":"177","volume":"4","author":"\u00c1 Kiss","year":"2017","unstructured":"Kiss, \u00c1., Liu, J., Schneider, T., Asokan, N., Pinkas, B.: Private set intersection for unequal set sizes with mobile applications. Proc. Priv. Enhanc. Technol. 4, 177\u2013197 (2017)","journal-title":"Proc. Priv. Enhanc. Technol."},{"key":"599_CR59","doi-asserted-by":"crossref","unstructured":"Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., Trieu, N.: Practical multi-party private set intersection from symmetric-key techniques. In: CCS, pp. 1257\u20131272. ACM (2017)","DOI":"10.1145\/3133956.3134065"},{"key":"599_CR60","doi-asserted-by":"crossref","unstructured":"Katz, J., Ostrovsky, R.: Round-optimal secure two-party computation. In: CRYPTO, vol. 3152 Lecture Notes in Computer Science, pp. 335\u2013354. Springer (2004)","DOI":"10.1007\/978-3-540-28628-8_21"},{"key":"599_CR61","doi-asserted-by":"crossref","unstructured":"Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Annual International Cryptology Conference, pp. 19\u201330. Springer (1999)","DOI":"10.1007\/3-540-48405-1_2"},{"issue":"4","key":"599_CR62","doi-asserted-by":"publisher","first-page":"37","DOI":"10.3390\/cryptography4040037","volume":"4","author":"B Liang","year":"2020","unstructured":"Liang, B., Banegas, G., Mitrokotsa, A.: Statically aggregate verifiable random functions and application to e-lottery. Cryptography 4(4), 37 (2020)","journal-title":"Cryptography"},{"key":"599_CR63","unstructured":"Lemmermeyer, F.: Conics-a poor man\u2019s elliptic curves. arXiv:math\/0311306. (2003)"},{"key":"599_CR64","doi-asserted-by":"crossref","unstructured":"Li, C., Preneel, B.: Improved interpolation attacks on cryptographic primitives of low algebraic degree. In: International Conference on Selected Areas in Cryptography, pp. 171\u2013193. Springer (2019)","DOI":"10.1007\/978-3-030-38471-5_8"},{"key":"599_CR65","doi-asserted-by":"crossref","unstructured":"Mohassel, P., Rosulek, M.: Non-interactive secure 2pc in the offline\/online and batch settings. In: EUROCRYPT (3), vol. 10212, Lecture Notes in Computer Science, pp. 425\u2013455. (2017)","DOI":"10.1007\/978-3-319-56617-7_15"},{"key":"599_CR66","doi-asserted-by":"crossref","unstructured":"Micali, S., Rabin, M., Vadhan, S.: Verifiable random functions. In: 40th Annual Symposium on Foundations of Computer Science (cat. No. 99CB37039), pp. 120\u2013130. IEEE (1999)","DOI":"10.1109\/SFFCS.1999.814584"},{"issue":"4","key":"599_CR67","doi-asserted-by":"publisher","first-page":"365","DOI":"10.4064\/aa-82-4-365-377","volume":"82","author":"Christian Mauduit","year":"1997","unstructured":"Mauduit, Christian, S\u00e1rk\u00f6zy, Andr\u00e1s: On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol. Acta Arith. 82(4), 365\u2013377 (1997)","journal-title":"Acta Arith."},{"key":"599_CR68","doi-asserted-by":"crossref","unstructured":"Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: FOCS, pp. 458\u2013467. IEEE Computer Society (1997)","DOI":"10.1109\/SFCS.1997.646134"},{"key":"599_CR69","unstructured":"Ospina, D.E.E.: Groebner bases and applications to the security of multivariate public key cryptosystems. Ph.D. thesis, Ph.D. dissertation, Escuela de Matem\u00e1ticas, Univ. Nacional de Colombia (2016)"},{"issue":"197","key":"599_CR70","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1090\/S0025-5718-1992-1106978-9","volume":"58","author":"Rene Peralta","year":"1992","unstructured":"Peralta, Rene: On the distribution of quadratic residues and nonresidues modulo a prime number. Math. Comput. 58(197), 433\u2013440 (1992)","journal-title":"Math. Comput."},{"key":"599_CR71","doi-asserted-by":"crossref","unstructured":"Perlner, R., Petzoldt, A., Smith-Tone, D.: Total break of the SRP encryption scheme. In: International Conference on Selected Areas in Cryptography, pp. 355\u2013373. Springer (2017)","DOI":"10.1007\/978-3-319-72565-9_18"},{"key":"599_CR72","doi-asserted-by":"crossref","unstructured":"Pinkas, B., Schneider, T., Tkachenko, O., Yanai, A.: Efficient circuit-based PSI with linear communication. In: EUROCRYPT (3), vol. 11478, Lecture Notes in Computer Science, pp. 122\u2013153. Springer (2019)","DOI":"10.1007\/978-3-030-17659-4_5"},{"key":"599_CR73","unstructured":"Papadopoulos, D., Wessels, D., Huque, S., Naor, M., \u010del\u00e1k, J.V., Reyzin, L., Goldberg, S.: Making NSEC5 practical for DNSSEC. Cryptol. ePrint Arch. Report 2017\/099 (2017)"},{"issue":"2\u2014-3","key":"599_CR74","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1016\/j.jco.2003.08.019","volume":"20","author":"A Russell","year":"2004","unstructured":"Russell, A., Shparlinski, I.E.: Classical and quantum function reconstruction via character evaluation. J. Complex. 20(2\u2014-3), 404\u2013422 (2004)","journal-title":"J. Complex."},{"key":"599_CR75","unstructured":"Sugita, M., Kawazoe, M., Imai, H.: Relation between XL algorithm and Gr\u00f6bner bases algorithms. IACR eprint Server (2004)"},{"issue":"2","key":"599_CR76","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s10998-007-4185-1","volume":"55","author":"Vikt\u00f3ria T\u00f3th","year":"2007","unstructured":"T\u00f3th, Vikt\u00f3ria: Collision and avalanche effect in families of pseudorandom binary sequences. Period. Math. Hung. 55(2), 185\u2013196 (2007)","journal-title":"Period. Math. Hung."},{"key":"599_CR77","unstructured":"Ullah, E.: New techniques for polynomial system solving (Doctoral dissertation Universit\u00e4t Passau) (2012)"},{"issue":"3","key":"599_CR78","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S009753970343141X","volume":"36","author":"W van Dam","year":"2006","unstructured":"van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36(3), 763\u2013778 (2006)","journal-title":"SIAM J. Comput."},{"key":"599_CR79","unstructured":"Vinogradov, I.M..: Elements of Number Theory. Courier Dover Publications (2016)"},{"key":"599_CR80","unstructured":"Ching-Hua, Y.: Sign modules in secure arithmetic circuits. IACR Cryptol. ePrint Arch. 2011, 539 (2011)"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-023-00599-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00200-023-00599-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-023-00599-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T14:31:51Z","timestamp":1738679511000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00200-023-00599-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,1]]},"references-count":80,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["599"],"URL":"https:\/\/doi.org\/10.1007\/s00200-023-00599-2","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,1]]},"assertion":[{"value":"15 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}