{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:58:34Z","timestamp":1764997114956},"publisher-location":"Cham","reference-count":43,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319566191"},{"type":"electronic","value":"9783319566207"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-56620-7_2","type":"book-chapter","created":{"date-parts":[[2017,3,31]],"date-time":"2017-03-31T02:29:18Z","timestamp":1490927358000},"page":"27-59","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Short Generators Without Quantum Computers: The Case of Multiquadratics"],"prefix":"10.1007","author":[{"given":"Jens","family":"Bauch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel J.","family":"Bernstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry","family":"de Valence","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tanja","family":"Lange","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christine","family":"van Vredendaal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,4,1]]},"reference":[{"key":"2_CR1","unstructured":"Abel, C.S.: Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reell-quadratischer Ordnungen. Ph.D. thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany (1994)"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Adleman, L.M.: Factoring numbers using singular integers. In: STOC 1991, pp. 64\u201371 (1991)","DOI":"10.1145\/103418.103432"},{"key":"2_CR3","unstructured":"Alkim, E., Ducas, L., P\u00f6ppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. USENIX Security 2016, pp. 327\u2013343 (2016)"},{"issue":"1","key":"2_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L Babai","year":"1986","unstructured":"Babai, L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1\u201313 (1986)","journal-title":"Combinatorica"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-55220-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"R Barbulescu","year":"2014","unstructured":"Barbulescu, R., Gaudry, P., Joux, A., Thom\u00e9, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 1\u201316. Springer, Heidelberg (2014). doi: 10.1007\/978-3-642-55220-5_1"},{"issue":"1","key":"2_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.5802\/jtnb.433","volume":"16","author":"K Belabas","year":"2004","unstructured":"Belabas, K.: Topics in computational algebraic number theory. J. de Th\u00e9orie des Nombres de Bordeaux 16(1), 19\u201363 (2004)","journal-title":"J. de Th\u00e9orie des Nombres de Bordeaux"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Biasse, J.-F., Fieker, C.: Improved techniques for computing the ideal class group and a system of fundamental units in number fields. In: ANTS-IX. Open Book Series, vol. 1, pp. 113\u2013133. Mathematical Sciences Publishers (2012)","DOI":"10.2140\/obs.2013.1.113"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/978-3-642-14081-5_15","volume-title":"Information Security and Privacy","author":"J-F Biasse","year":"2010","unstructured":"Biasse, J.-F., Jacobson Jr., M.J., Silvester, A.K.: Security estimates for quadratic field based cryptosystems. In: Steinfeld, R., Hawkes, P. (eds.) ACISP 2010. LNCS, vol. 6168, pp. 233\u2013247. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14081-5_15"},{"key":"2_CR9","unstructured":"Biasse, J.-F., Song, F.: On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in $$\\mathbb{Q}(\\zeta _{p^n})$$ (2015). http:\/\/cacr.uwaterloo.ca\/techreports\/2015\/cacr2015-12.pdf"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Biasse, J.-F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: SODA 2016, pp. 893\u2013902 (2016)","DOI":"10.1137\/1.9781611974331.ch64"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Biehl, I., Buchmann, J.: Algorithms for quadratic orders. In: Mathematics of Computation 1943\u20131993: A Half-century of Computational Mathematics, pp. 425\u2013451. AMS (1994)","DOI":"10.1090\/psapm\/048\/1314882"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Bos, J.W., Costello, C., Naehrig, M., Stebila, D.: Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: IEEE S&P 2015, pp. 553\u2013570 (2015)","DOI":"10.1109\/SP.2015.40"},{"issue":"2","key":"2_CR13","doi-asserted-by":"publisher","first-page":"293","DOI":"10.5802\/jtnb.281","volume":"12","author":"J Buchmann","year":"2000","unstructured":"Buchmann, J., Maurer, M., M\u00f6ller, B.: Cryptography based on number fields with large regulator. J. de Th\u00e9orie des Nombres de Bordeaux 12(2), 293\u2013307 (2000)","journal-title":"J. de Th\u00e9orie des Nombres de Bordeaux"},{"key":"2_CR14","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-46368-9_2","volume-title":"Binary Quadratic Forms: An Algorithmic Approach","author":"J Buchmann","year":"2007","unstructured":"Buchmann, J., Vollmer, U.: Binary Quadratic Forms: An Algorithmic Approach. Algorithms and Computation in Mathematics. Springer, Heidelberg (2007)"},{"key":"2_CR15","unstructured":"Buchmann, J.A.: A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. In: S\u00e9minaire de Th\u00e9orie des Nombres, Paris 1988\u20131989, pp. 27\u201341 (1990)"},{"key":"2_CR16","volume-title":"Algorithms and Computation in Mathematics","author":"JP Buhler","year":"2007","unstructured":"Buhler, J.P., Lenstra Jr., H.W., Pomerance, C.: Factoring integers with the number field sieve. In: Lenstra, A.K., Lenstra, H.W. (eds.) Algorithms and Computation in Mathematics. Springer, Heidelberg (2007)"},{"key":"2_CR17","unstructured":"Campbell, P., Groves, M., Shepherd, D.: Soliloquy: a cautionary tale (2014). http:\/\/docbox.etsi.org\/Workshop\/2014\/201410_CRYPTO\/S07_Systems_and_Attacks\/S07_Groves_Annex.pdf"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-46800-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2015","author":"JH Cheon","year":"2015","unstructured":"Cheon, J.H., Han, K., Lee, C., Ryu, H., Stehl\u00e9, D.: Cryptanalysis of the multilinear map over the integers. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 3\u201312. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-46800-5_1"},{"key":"2_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A Course in Computational Algebraic Number Theory","author":"H Cohen","year":"1993","unstructured":"Cohen, H.: A Course in Computational Algebraic Number Theory. Springer, Heidelberg (1993)"},{"key":"2_CR20","volume-title":"Advanced Topics in Computational Number Theory","author":"H Cohen","year":"1999","unstructured":"Cohen, H.: Advanced Topics in Computational Number Theory. Springer, New York (1999)"},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-662-47989-6_13","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"J-S Coron","year":"2015","unstructured":"Coron, J.-S., Lepoint, T., Tibouchi, M.: New multilinear maps over the integers. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 267\u2013286. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-47989-6_13"},{"key":"2_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-662-49896-5_20","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"R Cramer","year":"2016","unstructured":"Cramer, R., Ducas, L., Peikert, C., Regev, O.: Recovering short generators of principal ideals in cyclotomic rings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 559\u2013585. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49896-5_20"},{"key":"2_CR23","unstructured":"The Sage Developers: SageMath, the Sage Mathematics Software System (Version 7.5.1) (2017). http:\/\/www.sagemath.org"},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-319-13051-4_11","volume-title":"Selected Areas in Cryptography \u2013 SAC 2014","author":"K Eisentr\u00e4ger","year":"2014","unstructured":"Eisentr\u00e4ger, K., Hallgren, S., Lauter, K.: Weak instances of PLWE. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 183\u2013194. Springer, Cham (2014). doi: 10.1007\/978-3-319-13051-4_11"},{"key":"2_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139012843","volume-title":"Mathematics of Public Key Cryptography","author":"SD Galbraith","year":"2012","unstructured":"Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge (2012)"},{"issue":"1","key":"2_CR26","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10623-015-0146-7","volume":"78","author":"SD Galbraith","year":"2016","unstructured":"Galbraith, S.D., Gaudry, P.: Recent progress on the elliptic curve discrete logarithm problem. Des. Codes Cryptogr. 78(1), 51\u201372 (2016)","journal-title":"Des. Codes Cryptogr."},{"key":"2_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-38348-9_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"S Garg","year":"2013","unstructured":"Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1\u201317. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38348-9_1"},{"key":"2_CR28","unstructured":"Gentry, C.: A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University (2009). https:\/\/crypto.stanford.edu\/craig"},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"C. Gentry.: Fully homomorphic encryption using ideal lattices. In: STOC 2009, pp. 169\u2013178 (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"2_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/978-3-642-14623-7_7","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"C Gentry","year":"2010","unstructured":"Gentry, C.: Toward basing fully homomorphic encryption on worst-case hardness. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 116\u2013137. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14623-7_7"},{"key":"2_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-642-20465-4_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"C Gentry","year":"2011","unstructured":"Gentry, C., Halevi, S.: Implementing Gentry\u2019s fully-homomorphic encryption scheme. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 129\u2013148. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-20465-4_9"},{"key":"2_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BFb0054868","volume-title":"Algorithmic Number Theory","author":"J Hoffstein","year":"1998","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267\u2013288. Springer, Heidelberg (1998). doi: 10.1007\/BFb0054868"},{"key":"2_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/978-3-662-53018-4_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"T Kim","year":"2016","unstructured":"Kim, T., Barbulescu, R.: Extended tower number field sieve: a new complexity for the medium prime case. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 543\u2013571. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-53018-4_20"},{"key":"2_CR34","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1017\/S0027763000000088","volume":"10","author":"T Kubota","year":"1956","unstructured":"Kubota, T.: \u00dcber den bizyklischen biquadratischen Zahlk\u00f6rper. Nagoya Math. J. 10, 65\u201385 (1956)","journal-title":"Nagoya Math. J."},{"key":"2_CR35","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"2_CR36","first-page":"182","volume":"49","author":"HW Lenstra","year":"2002","unstructured":"Lenstra, H.W.: Solving the Pell equation. Notices Amer. Math. Soc. 49, 182\u2013192 (2002)","journal-title":"Notices Amer. Math. Soc."},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0747-7171(87)80061-5","volume":"4","author":"M Pohst","year":"1987","unstructured":"Pohst, M.: A modification of the LLL reduction algorithm. J. Symb. Comput. 4, 123\u2013127 (1987)","journal-title":"J. Symb. Comput."},{"key":"2_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/978-3-642-13013-7_25","volume-title":"Public Key Cryptography \u2013 PKC 2010","author":"NP Smart","year":"2010","unstructured":"Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420\u2013443. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13013-7_25"},{"key":"2_CR39","unstructured":"van der Kallen, W.: Complexity of an extended lattice reduction algorithm (1998). http:\/\/www.staff.science.uu.nl\/~kalle101\/complexity.pdf"},{"key":"2_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/10722028_39","volume-title":"Algorithmic Number Theory","author":"U Vollmer","year":"2000","unstructured":"Vollmer, U.: Asymptotically fast discrete logarithms in quadratic number fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 581\u2013594. Springer, Heidelberg (2000). doi: 10.1007\/10722028_39"},{"key":"2_CR41","unstructured":"Vollmer, U.: Rigorously analyzed algorithms for the discrete logarithm problem in quadratic number fields. Ph.D. thesis, Technische Universit\u00e4t, Darmstadt (2004)"},{"issue":"13","key":"2_CR42","first-page":"201","volume":"13","author":"H Wada","year":"1966","unstructured":"Wada, H.: On the class number and the unit group of certain algebraic number fields. J. Fac. Sci. Univ. Tokyo Sect. I 13(13), 201\u2013209 (1966)","journal-title":"J. Fac. Sci. Univ. Tokyo Sect. I"},{"key":"2_CR43","doi-asserted-by":"crossref","unstructured":"Williams, H.C.: Solving the Pell equation. In: Number theory for the millennium III, pp. 397\u2013435. A K Peters (2002)","DOI":"10.1201\/9780138747022-24"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2017"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-56620-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,22]],"date-time":"2023-08-22T23:04:27Z","timestamp":1692745467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-56620-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319566191","9783319566207"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-56620-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"1 April 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 April 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 May 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"36","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt2017.di.ens.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}