{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T15:44:05Z","timestamp":1765122245522,"version":"3.46.0"},"publisher-location":"Singapore","reference-count":43,"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_15","type":"book-chapter","created":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T15:43:40Z","timestamp":1765122220000},"page":"466-497","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Hybrid Algorithm for\u00a0the\u00a0Regular Syndrome Decoding Problem"],"prefix":"10.1007","author":[{"given":"Tianrui","family":"Wang","sequence":"first","affiliation":[]},{"given":"Anyu","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Kang","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Hanlin","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Yu","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Jun","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Xiaoyun","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,8]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Abram, D., Scholl, P.: Low-communication multiparty triple generation for SPDZ from Ring-LPN. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) Public-Key Cryptography \u2013 PKC 2022, pp. 221\u2013251. Springer International Publishing (2022)","DOI":"10.1007\/978-3-030-97121-2_9"},{"key":"15_CR2","unstructured":"Al Jabri, A.: A statistical decoding algorithm for general linear block codes. In: Honary, B. (ed.) 8th IMA International Conference on Cryptography and Coding. Lecture Notes in Computer Science, vol.\u00a02260, pp.\u00a01\u20138. Springer, Heidelberg, Germany, Cirencester, UK (Dec\u00a017\u201319, 2001)"},{"issue":"4","key":"15_CR3","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1016\/j.aam.2006.08.008","volume":"39","author":"D Andr\u00e9n","year":"2007","unstructured":"Andr\u00e9n, D., Hellstr\u00f6m, L., Markstr\u00f6m, K.: On the complexity of matrix reduction over finite fields. Adv. Appl. Math. 39(4), 428\u2013452 (2007)","journal-title":"Adv. Appl. Math."},{"key":"15_CR4","unstructured":"Ant Group: SecretFlow: a unified trusted privacy-preserving computing framework. https:\/\/github.com\/secretflow (2022)"},{"key":"15_CR5","doi-asserted-by":"publisher","unstructured":"Augot, D., Finiasz, M., Sendrier, N.: A family of fast syndrome based cryptographic hash functions. In: Dawson, E., Vaudenay, S. (eds.) Progress in Cryptology - Mycrypt 2005, First International Conference on Cryptology in Malaysia, Kuala Lumpur, Malaysia, September 28-30, 2005, Proceedings. Lecture Notes in Computer Science, vol.\u00a03715, pp. 64\u201383. Springer (2005). https:\/\/doi.org\/10.1007\/11554868_6","DOI":"10.1007\/11554868_6"},{"key":"15_CR6","doi-asserted-by":"publisher","unstructured":"Baum, C., Malozemoff, A.J., Rosen, M.B., Scholl, P.: Mac\u2019n\u2019cheese: zero-knowledge proofs for Boolean and arithmetic circuits with nested disjunctions. In: Malkin, T., Peikert, C. (eds.) Advances in Cryptology \u2013 CRYPTO\u00a02021, Part\u00a0IV. Lecture Notes in Computer Science, vol. 12828, pp. 92\u2013122. Springer, Heidelberg, Germany, Virtual Event (Aug\u00a016\u201320, 2021). https:\/\/doi.org\/10.1007\/978-3-030-84259-8_4","DOI":"10.1007\/978-3-030-84259-8_4"},{"key":"15_CR7","doi-asserted-by":"publisher","unstructured":"Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in $$2^{n\/20}$$: how 1 + 1 = 0 improves information set decoding. In: Pointcheval, D., Johansson, T. (eds.) Advances in Cryptology \u2013 EUROCRYPT\u00a02012. Lecture Notes in Computer Science, vol.\u00a07237, pp. 520\u2013536. Springer, Heidelberg, Germany, Cambridge, UK (Apr\u00a015\u201319, 2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_31","DOI":"10.1007\/978-3-642-29011-4_31"},{"key":"15_CR8","doi-asserted-by":"publisher","unstructured":"Berlekamp, E.R., McEliece, R.J., van Tilborg, H.C.A.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theory 24(3), 384\u2013386 (1978). https:\/\/doi.org\/10.1109\/TIT.1978.1055873","DOI":"10.1109\/TIT.1978.1055873"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Bombar, M., Bui, D., Couteau, G., Couvreur, A., Ducros, C., Servan-Schreiber, S.: FOLEAGE: $$\\mathbb{F}_4$$OLE-based multi-party computation for Boolean circuits. Cryptology ePrint Archive, Paper 2024\/429 (2024). https:\/\/eprint.iacr.org\/2024\/429","DOI":"10.1007\/978-981-96-0938-3_3"},{"key":"15_CR10","doi-asserted-by":"publisher","unstructured":"Bombar, M., Couteau, G., Couvreur, A., Ducros, C.: Correlated pseudorandomness from the hardness of quasi-abelian decoding. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part IV. Lecture Notes in Computer Science, vol. 14084, pp. 567\u2013601. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-38551-3_18","DOI":"10.1007\/978-3-031-38551-3_18"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Bouillaguet, C., et al.: Fast exhaustive search for polynomial systems in. In: International Workshop on Cryptographic Hardware and Embedded Systems, pp. 203\u2013218. Springer (2010)","DOI":"10.1007\/978-3-642-15031-9_14"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Bouillaguet, C., Delaplace, C., Trimoska, M.: A simple deterministic algorithm for systems of quadratic polynomials over $$\\mathbb{F}_4$$. In: Symposium on Simplicity in Algorithms (SOSA), pp. 285\u2013296. SIAM (2022)","DOI":"10.1137\/1.9781611977066.22"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Boyle, E., Couteau, G., Gilboa, N., Ishai, Y.: Compressing vector OLE. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 896\u2013912 (2018)","DOI":"10.1145\/3243734.3243868"},{"key":"15_CR14","doi-asserted-by":"publisher","unstructured":"Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Resch, N., Scholl, P.: Correlated pseudorandomness from expand-accumulate codes. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology \u2013 CRYPTO\u00a02022, Part\u00a0II. Lecture Notes in Computer Science, vol. 13508, pp. 603\u2013633. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug\u00a015\u201318, 2022). https:\/\/doi.org\/10.1007\/978-3-031-15979-4_21","DOI":"10.1007\/978-3-031-15979-4_21"},{"key":"15_CR15","doi-asserted-by":"publisher","unstructured":"Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Efficient pseudorandom correlation generators: Silent OT extension and more. In: Boldyreva, A., Micciancio, D. (eds.) Advances in Cryptology \u2013 CRYPTO\u00a02019, Part\u00a0III. Lecture Notes in Computer Science, vol. 11694, pp. 489\u2013518. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug\u00a018\u201322, 2019). https:\/\/doi.org\/10.1007\/978-3-030-26954-8_16","DOI":"10.1007\/978-3-030-26954-8_16"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Efficient pseudorandom correlation generators from ring-LPN. In: Advances in Cryptology\u2013CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17\u201321, 2020, Proceedings, Part II 40. pp. 387\u2013416. Springer (2020)","DOI":"10.1007\/978-3-030-56880-1_14"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Briaud, P., \u00d8ygarden, M.: A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 391\u2013422. Springer (2023)","DOI":"10.1007\/978-3-031-30589-4_14"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Bui, D., Carozza, E., Couteau, G., Goudarzi, D., Joux, A.: Faster signatures from MPC-in-the-head. Cryptology ePrint Archive, Paper 2024\/252 (2024). https:\/\/eprint.iacr.org\/2024\/252","DOI":"10.1007\/978-981-96-0875-1_13"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Carozza, E., Couteau, G., Joux, A.: Short signatures from regular syndrome decoding in the head. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 532\u2013563. Springer (2023)","DOI":"10.1007\/978-3-031-30589-4_19"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 392\u2013407. Springer (2000)","DOI":"10.1007\/3-540-45539-6_27"},{"key":"15_CR21","doi-asserted-by":"publisher","unstructured":"Couteau, G., Rindal, P., Raghuraman, S.: Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In: Malkin, T., Peikert, C. (eds.) Advances in Cryptology \u2013 CRYPTO\u00a02021, Part\u00a0III. Lecture Notes in Computer Science, vol. 12827, pp. 502\u2013534. Springer, Heidelberg, Germany, Virtual Event (Aug\u00a016\u201320, 2021). https:\/\/doi.org\/10.1007\/978-3-030-84252-9_17","DOI":"10.1007\/978-3-030-84252-9_17"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Cui, H., Liu, H., Yan, D., Yang, K., Yu, Y., Zhang, K.: Resolved: shorter signatures from regular syndrome decoding and VOLE-in-the-head. Cryptology ePrint Archive (2024)","DOI":"10.1007\/978-3-031-57718-5_8"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Dinur, I.: Cryptanalytic applications of the polynomial method for solving multivariate equation systems over GF(2). In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 374\u2013403. Springer (2021)","DOI":"10.1007\/978-3-030-77870-5_14"},{"key":"15_CR24","unstructured":"Dumer, I.: On minimum distance decoding of linear codes. In: Proceedings of the 5th Joint Soviet-Swedish International Workshop on Information Theory, pp. 50\u201352 (1991)"},{"key":"15_CR25","doi-asserted-by":"publisher","unstructured":"Esser, A., K\u00fcbler, R., May, A.: LPN decoded. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology \u2013 CRYPTO\u00a02017, Part\u00a0II. Lecture Notes in Computer Science, vol. 10402, pp. 486\u2013514. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug\u00a020\u201324, 2017). https:\/\/doi.org\/10.1007\/978-3-319-63715-0_17","DOI":"10.1007\/978-3-319-63715-0_17"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"Esser, A., Santini, P.: Not just regular decoding: asymptotics and improvements of regular syndrome decoding attacks. Cryptology ePrint Archive (2023)","DOI":"10.1007\/978-3-031-68391-6_6"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Hazay, C., Orsini, E., Scholl, P., Soria-Vazquez, E.: Tinykeys: a new approach to efficient multi-party computation. In: Annual International Cryptology Conference, pp. 3\u201333. Springer (2018)","DOI":"10.1007\/978-3-319-96878-0_1"},{"key":"15_CR28","doi-asserted-by":"publisher","unstructured":"Joux, A., Vitse, V.: A crossbred algorithm for solving Boolean polynomial systems. In: Kaczorowski, J., Pieprzyk, J., Pomykala, J. (eds.) Number-Theoretic Methods in Cryptology - First International Conference, NuTMiC 2017, Warsaw, Poland, September 11-13, 2017, Revised Selected Papers. Lecture Notes in Computer Science, vol. 10737, pp. 3\u201321. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-76620-1_1","DOI":"10.1007\/978-3-319-76620-1_1"},{"key":"15_CR29","unstructured":"Kim, J., Lee, C.: Reduce and Prange: Revisiting Prange\u2019s information set decoding for LPN and RSD. Cryptology ePrint Archive (2024)"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"Lee, P.J., Brickell, E.F.: An observation on the security of McEliece\u2019s public-key cryptosystem. In: Workshop on the Theory and Application of of Cryptographic Techniques, pp. 275\u2013280. Springer (1988)","DOI":"10.1007\/3-540-45961-8_25"},{"key":"15_CR31","unstructured":"Liu, H., Wang, X., Yang, K., Yu, Y.: The hardness of LPN over any integer ring and field for PCG applications. Cryptology ePrint Archive (2022)"},{"key":"15_CR32","doi-asserted-by":"publisher","unstructured":"May, A., Meurer, A., Thomae, E.: Decoding random linear codes in $$\\tilde{\\cal{O}}(2^{0.054n})$$. In: Lee, D.H., Wang, X. (eds.) Advances in Cryptology \u2013 ASIACRYPT\u00a02011. Lecture Notes in Computer Science, vol.\u00a07073, pp. 107\u2013124. Springer, Heidelberg, Germany, Seoul, South Korea (Dec\u00a04\u20138, 2011). https:\/\/doi.org\/10.1007\/978-3-642-25385-0_6","DOI":"10.1007\/978-3-642-25385-0_6"},{"key":"15_CR33","unstructured":"Meta: Private Computation Framework 2.0. https:\/\/github.com\/facebookresearch\/fbpcf (2022)"},{"issue":"5","key":"15_CR34","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1109\/TIT.1962.1057777","volume":"8","author":"E Prange","year":"1962","unstructured":"Prange, E.: The use of information sets in decoding cyclic codes. IRE Trans. Inf. Theory 8(5), 5\u20139 (1962)","journal-title":"IRE Trans. Inf. Theory"},{"key":"15_CR35","doi-asserted-by":"publisher","unstructured":"Rachuri, R., Scholl, P.: Le Mans: dynamic and fluid MPC for dishonest majority. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology \u2013 CRYPTO\u00a02022, Part\u00a0I. Lecture Notes in Computer Science, vol. 13507, pp. 719\u2013749. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug\u00a015\u201318, 2022). https:\/\/doi.org\/10.1007\/978-3-031-15802-5_25","DOI":"10.1007\/978-3-031-15802-5_25"},{"key":"15_CR36","doi-asserted-by":"crossref","unstructured":"Raghuraman, S., Rindal, P., Tanguy, T.: Expand-convolute codes for pseudorandom correlation generators from LPN. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology \u2013 CRYPTO 2023, pp. 602\u2013632. Springer Nature Switzerland (2023)","DOI":"10.1007\/978-3-031-38551-3_19"},{"key":"15_CR37","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.jalgebra.2020.08.035","volume":"565","author":"I Semaev","year":"2021","unstructured":"Semaev, I., Tenti, A.: Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gr\u00f6bner bases. J. Algebra 565, 651\u2013674 (2021)","journal-title":"J. Algebra"},{"key":"15_CR38","doi-asserted-by":"crossref","unstructured":"Stern, J.: A method for finding codewords of small weight. In: Coding Theory and Applications: 3rd International Colloquium Toulon, France, November 2\u20134, 1988 Proceedings 3, pp. 106\u2013113. Springer (1989)","DOI":"10.1007\/BFb0019850"},{"key":"15_CR39","unstructured":"Wang, X., Malozemoff, A.J., Katz, J.: EMP-toolkit: efficient multiparty computation toolkit. https:\/\/github.com\/emp-toolkit (2016)"},{"key":"15_CR40","unstructured":"Weger, V., Gassner, N., Rosenthal, J.: A survey on code-based cryptography. CoRR abs\/2201.07119 (2022). https:\/\/arxiv.org\/abs\/2201.07119"},{"key":"15_CR41","doi-asserted-by":"publisher","unstructured":"Weng, C., Yang, K., Katz, J., Wang, X.: Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for Boolean and arithmetic circuits. In: 2021 IEEE Symposium on Security and Privacy, pp. 1074\u20131091. IEEE Computer Society Press, San Francisco, CA, USA (May\u00a024\u201327, 2021). https:\/\/doi.org\/10.1109\/SP40001.2021.00056","DOI":"10.1109\/SP40001.2021.00056"},{"key":"15_CR42","unstructured":"Williams, R.R.: The polynomial method in circuit complexity applied to algorithm design (invited talk). In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2014)"},{"key":"15_CR43","doi-asserted-by":"crossref","unstructured":"Yang, K., Weng, C., Lan, X., Zhang, J., Wang, X.: Ferret: fast extension for correlated OT with small communication. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1607\u20131626 (2020)","DOI":"10.1145\/3372297.3417276"}],"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_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T15:43:43Z","timestamp":1765122223000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-5113-2_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,8]]},"ISBN":["9789819551125","9789819551132"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-5113-2_15","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"}}]}}