{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T13:01:14Z","timestamp":1772283674586,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642546303","type":"print"},{"value":"9783642546310","type":"electronic"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54631-0_26","type":"book-chapter","created":{"date-parts":[[2014,2,20]],"date-time":"2014-02-20T05:04:17Z","timestamp":1392872657000},"page":"446-464","source":"Crossref","is-referenced-by-count":7,"title":["Practical Cryptanalysis of a Public-Key Encryption Scheme Based on New Multivariate Quadratic Assumptions"],"prefix":"10.1007","author":[{"given":"Martin R.","family":"Albrecht","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Charles","family":"Faug\u00e9re","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Fitzpatrick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ludovic","family":"Perret","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yosuke","family":"Todo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keita","family":"Xagawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC, pp. 99\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"key":"26_CR2","unstructured":"Albrecht, M.R., Cid, C., Faug\u00e8re, J.-C., Fitzpatrick, R., Perret, L.: On the complexity of the BKW algorithm on LWE. Cryptology ePrint Archive, Report 2012\/636 (2012), \n                    \n                      http:\/\/eprint.iacr.org\/\n                    \n                    \n                  ; Des. Codes Cryptogr. (2013)"},{"key":"26_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-642-25385-0_10","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"M.R. Albrecht","year":"2011","unstructured":"Albrecht, M.R., Farshim, P., Faug\u00e8re, J.-C., Perret, L.: Polly Cracker, revisited. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol.\u00a07073, pp. 179\u2013196. Springer, Heidelberg (2011), \n                    \n                      http:\/\/eprint.iacr.org\/"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Albrecht, M.R., Fitzpatrick, R., Gopfert, F.: On the efficacy of solving lwe by reduction to unique-svp. Cryptology ePrint Archive, Report 2013\/602 (2013), \n                    \n                      http:\/\/eprint.iacr.org\/","DOI":"10.1007\/978-3-319-12160-4_18"},{"key":"26_CR5","unstructured":"Bardet, M.: \u00c9tude des syst\u00e8mes alg\u00e9briques surd\u00e9termin\u00e9s. Applications aux codes correcteurs et \u00e0 la cryptographie. PhD thesis, Universit\u00e9 Paris VI (2004)"},{"key":"26_CR6","unstructured":"Bardet, M., Faug\u00e8re, J.-C., Salvy, B.: Complexity of Gr\u00f6bner basis computation for semi-regular overdetermined sequences over F2 with solutions in F2. Technical Report 5049, INRIA (December 2003), \n                    \n                      http:\/\/www.inria.fr\/rrrt\/rr-5049.html"},{"key":"26_CR7","unstructured":"Bardet, M., Faug\u00e8re, J.-C., Salvy, B.: On the complexity of Gr\u00f6bner basis computation of semi-regular overdetermined algebraic equations. In: Proc. International Conference on Polynomial System Solving (ICPSS), pp. 71\u201375 (2004)"},{"issue":"12","key":"26_CR8","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1016\/j.jsc.2008.10.004","volume":"44","author":"C. Berbain","year":"2009","unstructured":"Berbain, C., Gilbert, H., Patarin, J.: QUAD: A multivariate stream cipher with provable security. J. Symb. Comput.\u00a044(12), 1703\u20131723 (2009)","journal-title":"J. Symb. Comput."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of Learning with Errors. To appear STOC 2013 (2013)","DOI":"10.1145\/2488608.2488680"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 97\u2013106. IEEE (2011)","DOI":"10.1109\/FOCS.2011.12"},{"key":"26_CR11","unstructured":"Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, University of Innsbruck (1965)"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/780506.780516","volume-title":"Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation","author":"J.-C. Faug\u00e8re","year":"2002","unstructured":"Faug\u00e8re, J.-C.: A new efficient algorithm for computing Gr\u00f6bner bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pp. 75\u201383. ACM, New York (2002)"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-78967-3_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"N. Gama","year":"2008","unstructured":"Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol.\u00a04965, pp. 31\u201351. Springer, Heidelberg (2008)"},{"key":"26_CR14","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"key":"26_CR15","unstructured":"G.: GMP: The GNU multiple precision arithmetic library, \n                    \n                      http:\/\/gmplib.org\/"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Goldstein, D., Mayer, A.: On the equidistribution of hecke points (2003)","DOI":"10.1515\/form.2003.009"},{"key":"26_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-642-30057-8_12","volume-title":"Public Key Cryptography \u2013 PKC 2012","author":"Y.-J. Huang","year":"2012","unstructured":"Huang, Y.-J., Liu, F.-H., Yang, B.-Y.: Public-key cryptography from new multivariate quadratic assumptions. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol.\u00a07293, pp. 190\u2013205. Springer, Heidelberg (2012)"},{"issue":"3","key":"26_CR18","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R. Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Mathematics of Operations Research\u00a012(3), 415\u2013440 (1987)","journal-title":"Mathematics of Operations Research"},{"issue":"5","key":"26_CR19","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1145\/1089023.1089027","volume":"52","author":"S. Khot","year":"2005","unstructured":"Khot, S.: Hardness of approximating the shortest vector problem in lattices. J. ACM\u00a052(5), 789\u2013808 (2005)","journal-title":"J. ACM"},{"key":"26_CR20","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"L. Lov\u00e1sz","year":"1982","unstructured":"Lov\u00e1sz, L., Lenstra Jr., H.W., Lenstra, A.K.: Factoring polynomials with rational coefficients. Mathematische Annalen\u00a0261, 515\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Lindner, R., Peikert, C.: Better key sizes (and attacks) for lwe-based encryption. IACR Cryptology ePrint Archive, 592 (2010)","DOI":"10.1007\/978-3-642-19074-2_21"},{"key":"26_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/11830924_41","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Y.-K. Liu","year":"2006","unstructured":"Liu, Y.-K., Lyubashevsky, V., Micciancio, D.: On Bounded Distance Decoding for General Lattices. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 450\u2013461. Springer, Heidelberg (2006)"},{"key":"26_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/978-3-642-03356-8_34","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"V. Lyubashevsky","year":"2009","unstructured":"Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 577\u2013594. Springer, Heidelberg (2009)"},{"key":"26_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/3-540-45961-8_39","volume-title":"Advances in Cryptology - EUROCRYPT \u201988","author":"T. Matsumoto","year":"1988","unstructured":"Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: G\u00fcnther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol.\u00a0330, pp. 419\u2013453. Springer, Heidelberg (1988)"},{"key":"26_CR25","series-title":"The Kluwer International Series in Engineering and Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of Lattice Problems: a cryptographic perspective","author":"D. Micciancio","year":"2002","unstructured":"Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: a cryptographic perspective. The Kluwer International Series in Engineering and Computer Science, vol.\u00a0671. Kluwer Academic Publishers, Boston (2002)"},{"key":"26_CR26","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-540-88702-7_5","volume-title":"Post-Quantum Cryptography","author":"D. Micciancio","year":"2009","unstructured":"Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147\u2013191. Springer, Heidelberg (2009)"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM\u00a056(6) (2009)","DOI":"10.1145\/1568318.1568324"},{"key":"26_CR28","unstructured":"Shoup, V.: NTL: A library for doing number theory, \n                    \n                      http:\/\/shoup.net\/ntl\/"},{"key":"26_CR29","unstructured":"St\u00e9hle, D., et al.: fpLLL 4.0.4. fpLLL Development Team (2013), \n                    \n                      http:\/\/perso.ens-lyon.fr\/damien.stehle\/fplll\/"},{"key":"26_CR30","unstructured":"Stein, W.A., et al.: Sage Mathematics Software (Version 5.2). The Sage Development Team (2012), \n                    \n                      http:\/\/www.sagemath.org"},{"key":"26_CR31","unstructured":"von Zur Gathen, J., Gerhard, J.: Modern computer algebra, 2nd edn. Cambridge University Press (2003)"}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography \u2013 PKC 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54631-0_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T04:47:08Z","timestamp":1558846028000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54631-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642546303","9783642546310"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54631-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}