{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T10:55:26Z","timestamp":1776941726447,"version":"3.51.4"},"publisher-location":"Singapore","reference-count":29,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819551125","type":"print"},{"value":"9789819551132","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T00:00:00Z","timestamp":1765152000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T00:00:00Z","timestamp":1765152000000},"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":[[2026]]},"DOI":"10.1007\/978-981-95-5113-2_14","type":"book-chapter","created":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T15:43:42Z","timestamp":1765122222000},"page":"436-465","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Practical Cryptanalysis of\u00a0Pseudorandom Correlation Generators Based on\u00a0Quasi-abelian Syndrome Decoding"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9416-6244","authenticated-orcid":false,"given":"Charles","family":"Bouillaguet","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5314-1806","authenticated-orcid":false,"given":"Claire","family":"Delaplace","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0597-6221","authenticated-orcid":false,"given":"Micka\u00ebl","family":"Hamdad","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2113-3967","authenticated-orcid":false,"given":"Damien","family":"Vergnaud","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,8]]},"reference":[{"issue":"2","key":"14_CR1","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10107-002-0349-3","volume":"95","author":"ED Andersen","year":"2003","unstructured":"Andersen, E.D., Roos, C., Terlaky, T.: On implementing a primal-dual interior-point method for conic quadratic optimization. Math. Program. 95(2), 249\u2013277 (2003)","journal-title":"Math. Program."},{"key":"14_CR2","unstructured":"MOSEK ApS. The MOSEK Optimizer API for Python 11.0.20 (2025)"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Arnold, A., Roche, D.S.: Multivariate sparse interpolation using randomized kronecker substitutions. In: Nabeshima, K., Nagasaka, K., Winkler, F., Sz\u00e1nt\u00f3, \u00c1. (eds.) International Symposium on Symbolic and Algebraic Computation, ISSAC \u201914, Kobe, Japan, July 23-25, 2014, pp. 35\u201342. ACM (2014)","DOI":"10.1145\/2608628.2608674"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th ACM STOC, pp. 1\u201310. ACM Press (1988)","DOI":"10.1145\/62212.62213"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynominal interpolation (extended abstract). In: Simon, J. (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pp. 301\u2013309. ACM (1988)","DOI":"10.1145\/62212.62241"},{"key":"14_CR6","series-title":"Part VI, volume 15489 of LNCS","first-page":"69","volume-title":"ASIACRYPT 2024","author":"M Bombar","year":"2024","unstructured":"Bombar, M., et al.: FOLEAGE: $$\\mathbb{{F}}_{4}$$OLE-based multi-party computation for Boolean circuits. In: Chung, K.-M., Sasaki, Yu. (eds.) ASIACRYPT 2024. Part VI, volume 15489 of LNCS, pp. 69\u2013101. Springer, Singapore (2024)"},{"key":"14_CR7","series-title":"Part IV, volume 14084 of LNCS","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/978-3-031-38551-3_18","volume-title":"CRYPTO 2023","author":"M Bombar","year":"2023","unstructured":"Bombar, M., Couteau, G., Couvreur, A., Ducros, C.: Correlated pseudorandomness from the hardness of quasi-abelian decoding. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. Part IV, volume 14084 of LNCS, pp. 567\u2013601. Springer, Cham (2023)"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Bonetti, M., Cirillo, P., Ogay, A.: Computing the exact distributions of some functions of the ordered multinomial counts: maximum, minimum, range and sums of order statistics. R. Soc. Open Sci. 6(10), 190198 (2019)","DOI":"10.1098\/rsos.190198"},{"key":"14_CR9","unstructured":"Bouillaguet, C., Delaplace, C., Hamdad, M., Vergnaud, D.: Practical cryptanalysis of pseudorandom correlation generators based on quasi-abelian syndrome decoding. IACR Cryptol. ePrint Arch., p. 892 (2025)"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press (2004)","DOI":"10.1017\/CBO9780511804441"},{"key":"14_CR11","series-title":"Part III, volume 11694 of LNCS","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-030-26954-8_16","volume-title":"CRYPTO 2019","author":"E Boyle","year":"2019","unstructured":"Boyle, E., et al.: Efficient pseudorandom correlation generators: Silent OT extension and more. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. Part III, volume 11694 of LNCS, pp. 489\u2013518. Springer, Cham (2019)"},{"issue":"2","key":"14_CR12","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Romberg, J.K., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489\u2013509 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"14_CR13","doi-asserted-by":"publisher","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","volume":"52","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Tao, T.: Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406\u20135425 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006). A Journal Issued by the Courant Institute of Mathematical Sciences","DOI":"10.1002\/cpa.20124"},{"issue":"3","key":"14_CR15","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s11222-010-9174-3","volume":"21","author":"CJ Corrado","year":"2011","unstructured":"Corrado, C.J.: The exact distribution of the maximum, minimum and the range of multinomial\/dirichlet and multivariate hypergeometric frequencies. Stat. Comput. 21(3), 349\u2013359 (2011)","journal-title":"Stat. Comput."},{"issue":"4","key":"14_CR16","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E de Klerk","year":"2002","unstructured":"de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"14_CR17","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Giesbrecht, M., Roche, D.S.: Diversification improves interpolation. In: Schost, \u00c9., Emiris, I.Z., (eds.) Symbolic and Algebraic Computation, International Symposium, ISSAC 2011 (co-located with FCRC 2011), San Jose, CA, USA, June 7-11, 2011, Proceedings, pp. 123\u2013130. ACM (2011)","DOI":"10.1145\/1993886.1993909"},{"key":"14_CR19","unstructured":"Huang, M.-D.A., Rao, A.J.: Interpolation of sparse multivariate polynomials over large finite fields with applications. In: Tardos, \u00c9. (ed.) Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 28-30 January 1996, Atlanta, Georgia, USA, pp. 508\u2013517. ACM\/SIAM (1996)"},{"key":"14_CR20","doi-asserted-by":"publisher","unstructured":"Huang, Q.-L., Gao, X.-S.: Sparse polynomial interpolation with finitely many values for the coefficients. In: Gerdt, V.P., Koepf, W., Seiler, W.M., Vorozhtsov, E.V. (eds.) CASC 2017. LNCS, vol. 10490, pp. 196\u2013209. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-66320-3_15","DOI":"10.1007\/978-3-319-66320-3_15"},{"key":"14_CR21","doi-asserted-by":"publisher","unstructured":"A Classical Introduction to Modern Number Theory. GTM, vol. 84. Springer, New York (1990). https:\/\/doi.org\/10.1007\/978-1-4757-2103-4","DOI":"10.1007\/978-1-4757-2103-4"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Kaltofen, E.L., Lakshman, Y.N., Wiley, J.-M.: Modular rational sparse multivariate polynomial interpolation. In: Watanabe, S., Nagata, M. (eds.) Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC \u201990, Tokyo, Japan, August 20-24, 1990, pp. 135\u2013139. ACM (1990)","DOI":"10.1145\/96877.96912"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Li, Z., Xing, C., Yao, Y., Yuan, C.: Efficient pseudorandom correlation generators for any finite field. In: Fehr, S., Fouque, P.-A. (eds.) Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part V, volume 15605 of Lecture Notes in Computer Science, pp. 145\u2013175. Springer (2025)","DOI":"10.1007\/978-3-031-91092-0_6"},{"key":"14_CR24","doi-asserted-by":"crossref","unstructured":"Lidl, R., Niederreiter, H.: Finite fields. volume\u00a020 of Encycl. Math. Appl. Cambridge: Cambridge Univ. Press, 2nd ed. edition (1996)","DOI":"10.1017\/CBO9780511525926"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Nesterov, Y.E., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming, volume\u00a013 of Siam studies in applied mathematics. SIAM (1994)","DOI":"10.1137\/1.9781611970791"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Sudan, M.: Maximum likelihood decoding of reed Solomon codes. In: 37th Annual Symposium on Foundations of Computer Science, FOCS \u201996, Burlington, Vermont, USA, 14-16 October, 1996, pp. 164\u2013172. IEEE Computer Society (1996)","DOI":"10.1109\/SFCS.1996.548475"},{"key":"14_CR27","volume-title":"Sparse polynomial interpolation: faster strategies over finite fields","author":"J van der Hoeven","year":"2024","unstructured":"van der Hoeven, J., Lecerf, G.: Sparse polynomial interpolation: faster strategies over finite fields. Applicable Algebra in Engineering, Communication and Computing (2024)"},{"key":"14_CR28","unstructured":"Wasserman, H.: Reconstructing randomly sampled multivariate polynomials from highly noisy data. In: Karloff, H.J. (ed.) Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California, USA, pp. 59\u201367. ACM\/SIAM (1998)"},{"key":"14_CR29","doi-asserted-by":"publisher","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation. LNCS, vol. 72, pp. 216\u2013226. Springer, Heidelberg (1979). https:\/\/doi.org\/10.1007\/3-540-09519-5_73","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 ASIACRYPT 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-5113-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T15:43:44Z","timestamp":1765122224000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-5113-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,8]]},"ISBN":["9789819551125","9789819551132"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-5113-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,8]]},"assertion":[{"value":"8 December 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ASIACRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Theory and Application of Cryptology and Information Security","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Melbourne, VIC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 December 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"asiacrypt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/asiacrypt.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}