{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T09:59:44Z","timestamp":1771667984184,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,11,28]],"date-time":"2017-11-28T00:00:00Z","timestamp":1511827200000},"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":[[2018,7]]},"DOI":"10.1007\/s00145-017-9272-x","type":"journal-article","created":{"date-parts":[[2017,11,28]],"date-time":"2017-11-28T15:29:36Z","timestamp":1511882976000},"page":"845-884","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Key-Recovery Attacks on ASASA"],"prefix":"10.1007","volume":"31","author":[{"given":"Brice","family":"Minaud","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Derbez","sequence":"additional","affiliation":[]},{"given":"Pierre-Alain","family":"Fouque","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"Karpman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,28]]},"reference":[{"key":"9272_CR1","doi-asserted-by":"crossref","unstructured":"M. R. Albrecht, J. C. Faug\u00e8re, R. Fitzpatrick, L. Perret, Y. Todo, and K. Xagawa, Practical cryptanalysis of a public-key encryption scheme based on new multivariate quadratic assumptions, in Hugo Krawczyk, editor, Public-Key Cryptography\u2013PKC 2014, Lecture Notes in Computer Science, vol. 8383 (Springer, Berlin, 2014) pp. 446\u2013464","DOI":"10.1007\/978-3-642-54631-0_26"},{"key":"9272_CR2","unstructured":"A. Biryukov, C. Bouillaguet, and D. Khovratovich, Cryptographic schemes based on the ASASA structure: black-box, white-box, and public-key, in Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology\u2013ASIACRYPT 2014, Lecture Notes in Computer Science, vol. 8873 (Springer, Berlin, 2014) pp. 63\u201384. Full version: http:\/\/eprint.iacr.org\/2014\/474 ."},{"issue":"1","key":"9272_CR3","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1109\/TIT.2012.2214203","volume":"59","author":"C Boura","year":"2013","unstructured":"C. Boura, A. Canteaut, On the influence of the algebraic degree of $$ F^{-1} $$ F - 1 on the algebraic degree of $$ G\\circ F$$ G \u2218 F , in IEEE Transactions on Information Theory, 59(1):691\u2013702, 2013.","journal-title":"IEEE Transactions on Information Theory"},{"key":"9272_CR4","doi-asserted-by":"crossref","unstructured":"A. Biryukov, C. De\u00a0Canniere, A. Braeken, and B. Preneel, A toolbox for cryptanalysis: Linear and affine equivalence algorithms, in International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), (Springer, Berlin, 2003) pp. 33\u201350","DOI":"10.1007\/3-540-39200-9_3"},{"key":"9272_CR5","doi-asserted-by":"crossref","unstructured":"L. Bettale, J. -C. Faug\u00e8re, and L.\u00a0Perret, Cryptanalysis of multivariate and odd-characteristic HFE variants, in Public Key Cryptography\u2014PKC 2011, vol. 6571 (Springer, Berlin, 2011) pp. 441\u2013458","DOI":"10.1007\/978-3-642-19379-8_27"},{"key":"9272_CR6","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya, Polynomial decompositions in polynomial time, in Andreas\u00a0S. Schulz and Dorothea Wagner, editors, Proceedings Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8\u201310, 2014., of Lecture Notes in Computer Science vol. 8737 (Springer, Berlin, 2014), pp. 125\u2013136","DOI":"10.1007\/978-3-662-44777-2_11"},{"key":"9272_CR7","unstructured":"G. Blom, L. Holst, and D. Sandell, Problems and snapshots from the world of probability. (Springer, Berlin, 2012)"},{"key":"9272_CR8","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya, P. Hatami, and M. Tulsiani, Algorithmic regularity for polynomials and applications, in Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, SIAM, 2015 pp. 1870\u20131889","DOI":"10.1137\/1.9781611973730.125"},{"key":"9272_CR9","doi-asserted-by":"crossref","unstructured":"E. Biham, Cryptanalysis of patarin\u2019s 2-round public key system with s-boxes (2R), in Bart Preneel, editor, Advances in Cryptology \u2013 EUROCRYPT 2000, Lecture Notes in Computer Science, vol. 1807 (Springer, Berlin, 2000) pp. 408\u2013416","DOI":"10.1007\/3-540-45539-6_28"},{"key":"9272_CR10","unstructured":"A. Biryukov and D. Khovratovich, Decomposition attack on SASASASAS, in Cryptology ePrint Archive, Report 2015\/646, 2015. http:\/\/eprint.iacr.org\/ ."},{"issue":"4","key":"9272_CR11","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A Blum","year":"2003","unstructured":"A. Blum, A. Kalai, and H. Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, in Journal of the ACM (JACM), 50(4):506\u2013519, 2003.","journal-title":"J. ACM (JACM)"},{"key":"9272_CR12","doi-asserted-by":"crossref","unstructured":"A. Biryukov and A. Shamir, Structural cryptanalysis of SASAS, in Birgit Pfitzmann, editor, Advances in Cryptology\u2013EUROCRYPT 2001, Lecture Notes in Computer Science, vol. 2045 (Springer, Berlin, 2001) pp. 395\u2013405","DOI":"10.1007\/3-540-44987-6_24"},{"issue":"3","key":"9272_CR13","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s12095-015-0149-2","volume":"8","author":"S Bogos","year":"2016","unstructured":"S. Bogos, F. Tramer, and S. Vaudenay, On solving LPN using BKW and variants. Cryptography and Communications, 8(3):331\u2013369, 2016.","journal-title":"Cryptogr. Commun."},{"key":"9272_CR14","unstructured":"J. Daemen, Cipher and hash function design strategies based on linear and differential cryptanalysis. PhD thesis, Katholieke Universiteit Leuven, Leuven, Belgium, 1995."},{"key":"9272_CR15","unstructured":"I. Dinur, O. Dunkelman, T. Kranz, G. Leander, Decomposing the asasa block cipher construction, in Cryptology ePrint Archive, Report 2015\/507, 2015. http:\/\/eprint.iacr.org\/2015\/507\/ ."},{"key":"9272_CR16","doi-asserted-by":"crossref","unstructured":"Y. Ding-Feng, K. Y. Lam, and D. Zong-Duo, Cryptanalysis of \u201c2R\u201d schemes, in Michael Wiener, editor, Advances in Cryptology \u2013 CRYPTO\u2019 99, Lecture Notes in Computer Science, vol. 1666 (Springer, Berlin, 1999) pp. 315\u2013325","DOI":"10.1007\/3-540-48405-1_20"},{"key":"9272_CR17","doi-asserted-by":"crossref","unstructured":"V. Dubois, P. Alain Fouque, A. Shamir, and J. Stern, Practical cryptanalysis of SFLASH, in Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007, Lecture Notes in Computer Science, vol. 4622 (Springer, Berlin, 2007) pp. 1\u201312","DOI":"10.1007\/978-3-540-74143-5_1"},{"key":"9272_CR18","doi-asserted-by":"crossref","unstructured":"V. Dubois, L. Granboulan, J. Stern, Cryptanalysis of HFE with internal perturbation, in Tatsuaki Okamoto and Xiaoyun Wang, editors, Public Key Cryptography \u2013 PKC 2007, Lecture Notes in Computer Science, vol. 4450 (Springer, Berlin, 2007) pp. 249\u2013265","DOI":"10.1007\/978-3-540-71677-8_17"},{"key":"9272_CR19","doi-asserted-by":"crossref","unstructured":"W.\u00a0Diffie and M.\u00a0E. Hellman, Multiuser cryptographic techniques, in AFIPS 1976 National Computer Conference, (ACM, 1976) pp. 109\u2013112","DOI":"10.1145\/1499799.1499815"},{"key":"9272_CR20","doi-asserted-by":"crossref","unstructured":"J. Ding, A new variant of the matsumoto-imai cryptosystem through perturbation, in Feng Bao, Robert Deng, and Jianying Zhou, editors, Public Key Cryptography \u2013 PKC 2004, Lecture Notes in Computer Science, vol. 2947 (Springer, Berlin, 2004) pp. 305\u2013318","DOI":"10.1007\/978-3-540-24632-9_22"},{"key":"9272_CR21","doi-asserted-by":"crossref","unstructured":"I. Dinur and A. Shamir, Cube attacks on tweakable black box polynomials, in Antoine Joux, editor, Advances in Cryptology \u2013 EUROCRYPT 2009, Lecture Notes in Computer Science, vol. 5479 (Springer, Berlin, 2009) pp. 278\u2013299","DOI":"10.1007\/978-3-642-01001-9_16"},{"key":"9272_CR22","doi-asserted-by":"crossref","unstructured":"H. Fell and W. Diffie, Analysis of a public key approach based on polynomial substitution, in Hugh C. Williams, editor, Advances in Cryptology \u2013 CRYPTO \u201985 proceedings, Lecture Notes in Computer Science, vol. 218 (Springer, Berlin, 1986) pp. 340\u2013349","DOI":"10.1007\/3-540-39799-X_24"},{"key":"9272_CR23","doi-asserted-by":"crossref","unstructured":"J. -C. Faug\u00e8re and A. Joux, Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gr\u00f6bner bases, in Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, Lecture Notes in Computer Science, vol. 2729 (Springer, Berlin, 2003) pp. 44\u201360","DOI":"10.1007\/978-3-540-45146-4_3"},{"key":"9272_CR24","doi-asserted-by":"crossref","unstructured":"J. -C. Faug\u00e8re and L. Perret, Cryptanalysis of 2R- schemes, in Cynthia Dwork, editor, Advances in Cryptology - CRYPTO 2006, Lecture Notes in Computer Science, vol. 4117 (Springer, Berlin, 2006) pp. 357\u2013372","DOI":"10.1007\/11818175_21"},{"issue":"12","key":"9272_CR25","doi-asserted-by":"publisher","first-page":"1676","DOI":"10.1016\/j.jsc.2008.02.005","volume":"44","author":"J-C Faug\u00e8re","year":"2009","unstructured":"J.-C. Faug\u00e8re and L.\u00a0Perret. An Efficient Algorithm for Decomposing Multivariate Polynomials and its Applications to Cryptography. J. Symb. Comput., 44(12):1676\u20131689, 2009.","journal-title":"J. Symb. Comput."},{"key":"9272_CR26","doi-asserted-by":"crossref","unstructured":"J.-C. Faug\u00e8re and L.\u00a0Perret, High order derivatives and decomposition of multivariate polynomials, in ISSAC \u201909: Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, (ACM, 2009) pp. 207\u2013214","DOI":"10.1145\/1576702.1576732"},{"key":"9272_CR27","doi-asserted-by":"crossref","unstructured":"J.-C. Faug\u00e8re, J.\u00a0von\u00a0zur Gathen, and L.\u00a0Perret, Decomposition of generic multivariate polynomials, in ISSAC \u201910: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, (ACM, 2010) pp. 131\u2013137. isbn: 0747-7171 (updated version).","DOI":"10.1145\/1837934.1837963"},{"key":"9272_CR28","doi-asserted-by":"crossref","unstructured":"H. Gilbert, J\u00e9r\u00f4me Pl\u00fbt, and J. Treger, Key-recovery attack on the ASASA cryptosystem with expanding S-boxes, in CRYPTO 2015. (Springer, Berlin, 2015)","DOI":"10.1007\/978-3-662-47989-6_23"},{"key":"9272_CR29","doi-asserted-by":"crossref","unstructured":"Y. -J. Huang, F. -H. Liu, and B. -Y. Yang, Public-key cryptography from new multivariate quadratic assumptions, in Marc Fischlin, Johannes\u00a0A. Buchmann, and Mark Manulis, editors, Proceedings Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012., volume 7293 of Lecture Notes in Computer Science, (Springer, Berlin, 2012) pp. 190\u2013205","DOI":"10.1007\/978-3-642-30057-8_12"},{"key":"9272_CR30","doi-asserted-by":"crossref","unstructured":"\u00c9. Levieil and P. -A. Fouque, An improved LPN algorithm, in Roberto De\u00a0Prisco and Moti Yung, editors, Security and Cryptography for Networks, Lecture Notes in Computer Science, vol. 4116 (Springer, Berlin, 2006) pp. 348\u2013359","DOI":"10.1007\/11832072_24"},{"key":"9272_CR31","doi-asserted-by":"crossref","unstructured":"M. Matsui, Linear cryptanalysis method for DES cipher, in Tor Helleseth, editor, Advances in Cryptology \u2013 EUROCRYPT \u201993, Lecture Notes in Computer Science, vol. 765 (Springer, Berlin, 1994) pp. 386\u2013397","DOI":"10.1007\/3-540-48285-7_33"},{"key":"9272_CR32","unstructured":"T. Matsumoto and H. Imai, Public quadratic polynomial-tuples for efficient signature-verification and message-encryption, in D.\u00a0Barstow, W.\u00a0Brauer, P.\u00a0Brinch\u00a0Hansen, D.\u00a0Gries, D.\u00a0Luckham, C.\u00a0Moler, A.\u00a0Pnueli, G.\u00a0Seegm\u00fcller, J.\u00a0Stoer, N.\u00a0Wirth, and Christoph\u00a0G. G\u00fcnther, editors, Advances in Cryptology \u2013 EUROCRYPT \u201988, Lecture Notes in Computer Science, vol. 330 (Springer, Berlin, 1988) pp. 419\u2013453"},{"key":"9272_CR33","doi-asserted-by":"crossref","unstructured":"J. Patarin, Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt\u201988, in Don Coppersmith, editor, Advances in Cryptology \u2013 CRYPTO\u2019 95, Lecture Notes in Computer Science, vol. 963 (Springer, Berlin, 1995) pp. 248\u2013261","DOI":"10.1007\/3-540-44750-4_20"},{"key":"9272_CR34","doi-asserted-by":"crossref","unstructured":"J. Patarin, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms, in Ueli Maurer, editor, Advances in Cryptology \u2013 EUROCRYPT \u201996, Lecture Notes in Computer Science, vol. 1070 (Springer, Berlin, 1996) pp. 33\u201348","DOI":"10.1007\/3-540-68339-9_4"},{"key":"9272_CR35","doi-asserted-by":"crossref","unstructured":"J. Patarin and L. Goubin, Asymmetric cryptography with S-boxes, in ICICS\u201997, Lecture Notes in Computer Science, vol. 1334 (Springer, Berlin, 1997) pp. 369\u2013380","DOI":"10.1007\/BFb0028492"},{"key":"9272_CR36","doi-asserted-by":"crossref","unstructured":"J. Patarin, L. Goubin, N. Courtois, Quartz, 128-bit long digital signatures, in CT-RSA Conference. (2001)","DOI":"10.1007\/3-540-45353-9_21"},{"key":"9272_CR37","doi-asserted-by":"crossref","unstructured":"O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in STOC\u201905. (ACM Press, 2005), pp. 84\u201393","DOI":"10.1145\/1060590.1060603"},{"key":"9272_CR38","doi-asserted-by":"crossref","unstructured":"V. Rijmen, B. Preneel, A family of trapdoor ciphers, in Eli Biham, editor, Fast Software Encryption, Lecture Notes in Computer Science, vol. 1267 (Springer, Berlin, 1997), pp. 139\u2013148","DOI":"10.1007\/BFb0052342"},{"key":"9272_CR39","unstructured":"The Sage\u00a0Development Team. Sage Mathematics Software. http:\/\/www.sagemath.org"},{"key":"9272_CR40","doi-asserted-by":"crossref","unstructured":"H. Wu, F. Bao, R. Deng, Q.-Z. Ye, Cryptanalysis of Rijmen\u2013Preneel Trapdoor Ciphers, in Kazuo Ohta, Dingyi Pei, editors, Advances in Cryptology\u2014ASIACRYPT\u201998, Lecture Notes in Computer Science, vol. 1514 (Springer, Berlin, 1998), pp. 126\u2013132","DOI":"10.1007\/3-540-49649-1_11"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-017-9272-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-017-9272-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-017-9272-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T16:00:18Z","timestamp":1751040018000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-017-9272-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,28]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9272"],"URL":"https:\/\/doi.org\/10.1007\/s00145-017-9272-x","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,28]]},"assertion":[{"value":"2 November 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2017","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"}]}}