{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:16:11Z","timestamp":1764980171464,"version":"3.46.0"},"reference-count":20,"publisher":"Walter de Gruyter GmbH","issue":"3-4","license":[{"start":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T00:00:00Z","timestamp":1565740800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1839805","1846166"],"award-info":[{"award-number":["1839805","1846166"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000161","name":"National Institute of Standards and Technology","doi-asserted-by":"publisher","award":["60NANB17D184"],"award-info":[{"award-number":["60NANB17D184"]}],"id":[{"id":"10.13039\/100000161","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,9,1]]},"abstract":"Abstract<\/jats:title>\n \n A family of ring-based cryptosystems, including the multilinear maps of Garg, Gentry and Halevi\n[Candidate multilinear maps from ideal lattices, Advances in Cryptology\u2014EUROCRYPT 2013, Lecture Notes in Comput. Sci. 7881, Springer, Heidelberg 2013, 1\u201317]\nand the fully homomorphic encryption scheme of Smart and Vercauteren\n[Fully homomorphic encryption with relatively small key and ciphertext sizes, Public Key Cryptography\u2014PKC 2010, Lecture Notes in Comput. Sci. 6056, Springer, Berlin 2010, 420\u2013443],\nare based on the hardness of finding a short generator of a principal ideal (short-PIP) in a number field typically in\n \n \n \n \n \u211a<\/m:mi>\n \u2062<\/m:mo>\n \n (<\/m:mo>\n \n \u03b6<\/m:mi>\n \n 2<\/m:mn>\n s<\/m:mi>\n <\/m:msup>\n <\/m:msub>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n \n {\\mathbb{Q}(\\zeta_{2^{s}})}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\nIn this paper, we present a polynomial-time quantum algorithm for recovering a generator of a principal ideal in\n \n \n \n \n \u211a<\/m:mi>\n \u2062<\/m:mo>\n \n (<\/m:mo>\n \n \u03b6<\/m:mi>\n \n 2<\/m:mn>\n s<\/m:mi>\n <\/m:msup>\n <\/m:msub>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n \n {\\mathbb{Q}(\\zeta_{2^{s}})}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and we recall how this can be used to attack the schemes relying on the short-PIP in\n \n \n \n \n \u211a<\/m:mi>\n \u2062<\/m:mo>\n \n (<\/m:mo>\n \n \u03b6<\/m:mi>\n \n 2<\/m:mn>\n s<\/m:mi>\n <\/m:msup>\n <\/m:msub>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n \n {\\mathbb{Q}(\\zeta_{2^{s}})}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n by using the work of Cramer et al.\n[R. Cramer, L. Ducas, C. Peikert and O. Regev,\nRecovering short generators of principal ideals in cyclotomic rings,\nIACR Cryptology ePrint Archive 2015,\n https:\/\/eprint.iacr.org\/2015\/313<\/jats:ext-link>\n ],\nwhich is derived from observations of Campbell, Groves and Shepherd\n[SOLILOQUY, a cautionary tale].\nWe put this attack into perspective by reviewing earlier attempts at providing an efficient quantum algorithm for solving the PIP in\n \n \n \n \n \u211a<\/m:mi>\n \u2062<\/m:mo>\n \n (<\/m:mo>\n \n \u03b6<\/m:mi>\n \n 2<\/m:mn>\n s<\/m:mi>\n <\/m:msup>\n <\/m:msub>\n )<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n \n {\\mathbb{Q}(\\zeta_{2^{s}})}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\nThe assumption that short-PIP is hard was challenged by Campbell, Groves and Shepherd.\nThey proposed an approach for solving short-PIP that proceeds in two steps: first they sketched a quantum algorithm for finding\n an<\/jats:italic>\n arbitrary generator (not necessarily short) of the input principal ideal.\nThen they suggested that it is feasible to compute a\n short<\/jats:italic>\n generator efficiently from the generator in step 1.\nCramer et al.\nvalidated step 2 of the approach by giving a detailed analysis.\nIn this paper, we focus on step 1, and we show that step 1 can run in quantum polynomial time if we use an algorithm for the continuous hidden subgroup problem (HSP) due to Eisentr\u00e4ger et al.\n[K. Eisentr\u00e4ger, S. Hallgren, A. Kitaev and F. Song, A quantum algorithm for computing the unit group of an arbitrary degree number field, Proceedings of the 2014 ACM Symposium on Theory of Computing\u2014STOC\u201914, ACM, New York 2014, 293\u2013302].\n <\/jats:p>","DOI":"10.1515\/jmc-2015-0046","type":"journal-article","created":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T05:39:53Z","timestamp":1565761193000},"page":"151-168","source":"Crossref","is-referenced-by-count":1,"title":["On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in \u211a(\ud835\udf01\n \n 2\n \ud835\udc60<\/sup>\n <\/sub>\n )"],"prefix":"10.1515","volume":"13","author":[{"given":"Jean-Fran\u00e7ois","family":"Biasse","sequence":"first","affiliation":[{"name":"Department of Mathematics & Statistics , University of South Florida , 4202 East Fowler Ave, CMC342 , Tampa , FL 33620-5700 , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fang","family":"Song","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering , Texas A&M University , Harvey R Bright Building, 3112 TAMU , College Station , TX 77843-3112 , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2019,8,14]]},"reference":[{"key":"2025120600115312596_j_jmc-2015-0046_ref_001_w2aab3b7b1b1b6b1ab1b8b1Aa","doi-asserted-by":"crossref","unstructured":"J.-F. Biasse,\nSubexponential time relations in the class group of large degree number fields,\nAdv. Math. Commun. 8 (2014), no. 4, 407\u2013425.\n10.3934\/amc.2014.8.407","DOI":"10.3934\/amc.2014.8.407"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_002_w2aab3b7b1b1b6b1ab1b8b2Aa","doi-asserted-by":"crossref","unstructured":"J.-F. Biasse and C. Fieker,\nSubexponential class group and unit group computation in large degree number fields,\nLMS J. Comput. Math. 17 (2014), 385\u2013403.\n10.1112\/S1461157014000345","DOI":"10.1112\/S1461157014000345"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_003_w2aab3b7b1b1b6b1ab1b8b3Aa","doi-asserted-by":"crossref","unstructured":"J.-F. Biasse and F. Song,\nEfficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields,\nProceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms,\nACM, New York (2016), 893\u2013902.","DOI":"10.1137\/1.9781611974331.ch64"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_004_w2aab3b7b1b1b6b1ab1b8b4Aa","unstructured":"P. Campbell, M. Groves and D. Shepherd,\nSOLILOQUY, a cautionary tale."},{"key":"2025120600115312596_j_jmc-2015-0046_ref_005_w2aab3b7b1b1b6b1ab1b8b5Aa","doi-asserted-by":"crossref","unstructured":"H. Cohen,\nAdvanced Topics in Computational Number Theory,\nGrad. Texts in Math. 193,\nSpringer, New York, 2000.","DOI":"10.1007\/978-1-4419-8489-0"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_006_w2aab3b7b1b1b6b1ab1b8b6Aa","doi-asserted-by":"crossref","unstructured":"R. Cramer, L. Ducas, C. Peikert and O. Regev,\nRecovering short generators of principal ideals in cyclotomic rings,\nIACR Cryptology ePrint Archive (2015), https:\/\/eprint.iacr.org\/2015\/313.","DOI":"10.1007\/978-3-662-49896-5_20"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_007_w2aab3b7b1b1b6b1ab1b8b7Aa","doi-asserted-by":"crossref","unstructured":"K. Eisentr\u00e4ger, S. Hallgren, A. Kitaev and F. Song,\nA quantum algorithm for computing the unit group of an arbitrary degree number field,\nProceedings of the 2014 ACM Symposium on Theory of Computing\u2014STOC\u201914,\nACM, New York (2014), 293\u2013302.","DOI":"10.1145\/2591796.2591860"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_008_w2aab3b7b1b1b6b1ab1b8b8Aa","doi-asserted-by":"crossref","unstructured":"S. Garg, C. Gentry and S. Halevi,\nCandidate multilinear maps from ideal lattices,\nAdvances in Cryptology\u2014EUROCRYPT 2013,\nLecture Notes in Comput. Sci. 7881,\nSpringer, Heidelberg (2013), 1\u201317.","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_009_w2aab3b7b1b1b6b1ab1b8b9Aa","doi-asserted-by":"crossref","unstructured":"C. Gentry and M. Szydlo,\nCryptanalysis of the revised NTRU signature scheme,\nAdvances in Cryptology\u2014EUROCRYPT 2002,\nLecture Notes in Comput. Sci. 2332,\nSpringer, Berlin (2002), 299\u2013320.","DOI":"10.1007\/3-540-46035-7_20"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_010_w2aab3b7b1b1b6b1ab1b8c10Aa","unstructured":"L. Hales,\nThe quantum fourier transform and extensions of the abelian hidden subgroup problem,\nPhD thesis, University of California Berkeley, 2002."},{"key":"2025120600115312596_j_jmc-2015-0046_ref_011_w2aab3b7b1b1b6b1ab1b8c11Aa","doi-asserted-by":"crossref","unstructured":"S. Hallgren,\nFast quantum algorithms for computing the unit group and class group of a number field,\nProceedings of the 37th Annual ACM Symposium on Theory of Computing\u2014STOC\u201905,\nACM, New York (2005), 468\u2013474.","DOI":"10.1145\/1060590.1060660"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_012_w2aab3b7b1b1b6b1ab1b8c12Aa","doi-asserted-by":"crossref","unstructured":"S. Hallgren,\nPolynomial-time quantum algorithms for Pell\u2019s equation and the principal ideal problem,\nJ. ACM 54 (2007), no. 1, Article ID 4.","DOI":"10.1145\/1206035.1206039"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_013_w2aab3b7b1b1b6b1ab1b8c13Aa","doi-asserted-by":"crossref","unstructured":"N. Howgrave-Graham and M. Szydlo,\nA method to solve cyclotomic norm equations f\u2217f\u00af{f\\ast\\overline{f}},\nAlgorithmic Number Theory,\nLecture Notes in Comput. Sci. 3076,\nSpringer, Berlin (2004), 272\u2013279.","DOI":"10.1007\/978-3-540-24847-7_20"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_014_w2aab3b7b1b1b6b1ab1b8c14Aa","doi-asserted-by":"crossref","unstructured":"M.-H. Kim and S.-G. Lim,\nSquare classes of totally positive units,\nJ. Number Theory 125 (2007), no. 1, 1\u20136.\n10.1016\/j.jnt.2006.04.010","DOI":"10.1016\/j.jnt.2006.04.010"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_015_w2aab3b7b1b1b6b1ab1b8c15Aa","doi-asserted-by":"crossref","unstructured":"D. Micciancio and S. Goldwasser,\nComplexity of Lattice Problems. A Cryptographic Perspective,\nKluwer Int. Ser. Eng. Comp. Sci. 671,\nKluwer Academic, Boston, 2002.","DOI":"10.1007\/978-1-4615-0897-7"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_016_w2aab3b7b1b1b6b1ab1b8c16Aa","unstructured":"O. Regev,\nPrivate communication, 2015."},{"key":"2025120600115312596_j_jmc-2015-0046_ref_017_w2aab3b7b1b1b6b1ab1b8c17Aa","doi-asserted-by":"crossref","unstructured":"P. W. Shor,\nPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,\nSIAM J. Comput. 26 (1997), no. 5, 1484\u20131509.\n10.1137\/S0097539795293172","DOI":"10.1137\/S0097539795293172"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_018_w2aab3b7b1b1b6b1ab1b8c18Aa","doi-asserted-by":"crossref","unstructured":"N. P. Smart and F. Vercauteren,\nFully homomorphic encryption with relatively small key and ciphertext sizes,\nPublic Key Cryptography\u2014PKC 2010,\nLecture Notes in Comput. Sci. 6056,\nSpringer, Berlin (2010), 420\u2013443.","DOI":"10.1007\/978-3-642-13013-7_25"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_019_w2aab3b7b1b1b6b1ab1b8c19Aa","doi-asserted-by":"crossref","unstructured":"L. C. Washington,\nIntroduction to Cyclotomic Fields,\nGrad. Texts in Math. 83,\nSpringer, New York, 1982.","DOI":"10.1007\/978-1-4684-0133-2"},{"key":"2025120600115312596_j_jmc-2015-0046_ref_020_w2aab3b7b1b1b6b1ab1b8c20Aa","unstructured":"H. Weber,\nLehrbuch der Algebra. Vol. II,\nVieweg, Braunschweig, 1899."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/jmc.2019.13.issue-3-4\/jmc-2015-0046\/jmc-2015-0046.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0046\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0046\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:12:01Z","timestamp":1764979921000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2015-0046\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,14]]},"references-count":20,"journal-issue":{"issue":"3-4","published-online":{"date-parts":[[2019,8,14]]},"published-print":{"date-parts":[[2019,9,1]]}},"alternative-id":["10.1515\/jmc-2015-0046"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2015-0046","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2019,8,14]]}}}