{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:54:51Z","timestamp":1743026091079,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031400025"},{"type":"electronic","value":"9783031400032"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-40003-2_19","type":"book-chapter","created":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T13:03:04Z","timestamp":1691586184000},"page":"505-532","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Time and Query Complexity Tradeoffs for the Dihedral Coset Problem"],"prefix":"10.1007","author":[{"given":"Maxime","family":"Remaud","sequence":"first","affiliation":[]},{"given":"Andr\u00e9","family":"Schrottenloher","sequence":"additional","affiliation":[]},{"given":"Jean-Pierre","family":"Tillich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,10]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case\/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, 4\u20136 May 1997, pp. 284\u2013293 (1997). http:\/\/doi.acm.org\/10.1145\/258533.258604","DOI":"10.1145\/258533.258604"},{"key":"19_CR2","unstructured":"Alagic, G., et al.: Status report on the third round of the nist post-quantum cryptography standardization process (2022\u201307-05 04:07:00 2022). https:\/\/tsapps.nist.gov\/publication\/get_pdf.cfm?pub_id=934458"},{"key":"19_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-030-64834-3_14","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2020","author":"N Alamati","year":"2020","unstructured":"Alamati, N., De Feo, L., Montgomery, H., Patranabis, S.: Cryptographic group actions and applications. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 411\u2013439. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64834-3_14"},{"key":"19_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-20465-4_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"A Becker","year":"2011","unstructured":"Becker, A., Coron, J.-S., Joux, A.: Improved generic algorithms for hard knapsacks. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 364\u2013385. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20465-4_21"},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-38616-9_2","volume-title":"Post-Quantum Cryptography","author":"DJ Bernstein","year":"2013","unstructured":"Bernstein, D.J., Jeffery, S., Lange, T., Meurer, A.: Quantum algorithms for the subset-sum problem. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 16\u201333. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38616-9_2"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-030-34578-5_9","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2019","author":"W Beullens","year":"2019","unstructured":"Beullens, W., Kleinjung, T., Vercauteren, F.: CSI-FiSh: efficient isogeny based signatures through class group computations. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 227\u2013247. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-34578-5_9"},{"key":"19_CR7","unstructured":"Bonnetain, X.: Improved low-qubit hidden shift algorithms (2019). arXiv:1901.11428"},{"key":"19_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/978-3-030-64834-3_22","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2020","author":"X Bonnetain","year":"2020","unstructured":"Bonnetain, X., Bricout, R., Schrottenloher, A., Shen, Y.: Improved classical and quantum algorithms for subset-sum. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 633\u2013666. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64834-3_22"},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/978-3-030-45724-2_17","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"X Bonnetain","year":"2020","unstructured":"Bonnetain, X., Schrottenloher, A.: Quantum security analysis of CSIDH. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 493\u2013522. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45724-2_17"},{"key":"19_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BFb0054319","volume-title":"LATIN\u201998: Theoretical Informatics","author":"G Brassard","year":"1998","unstructured":"Brassard, G., H\u00d8yer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 163\u2013169. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0054319"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-030-03332-3_15","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2018","author":"W Castryck","year":"2018","unstructured":"Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 395\u2013427. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-03332-3_15"},{"issue":"3","key":"19_CR12","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s13389-021-00271-w","volume":"12","author":"J Ch\u00e1vez-Saab","year":"2022","unstructured":"Ch\u00e1vez-Saab, J., Chi-Dom\u00ednguez, J., Jaques, S., Rodr\u00edguez-Henr\u00edquez, F.: The SQALE of CSIDH: sublinear v\u00e9lu quantum-resistant isogeny action with low exponents. J. Cryptogr. Eng. 12(3), 349\u2013368 (2022)","journal-title":"J. Cryptogr. Eng."},{"issue":"1","key":"19_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/jmc-2012-0016","volume":"8","author":"A Childs","year":"2014","unstructured":"Childs, A., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time. J. Math. Cryptol. 8(1), 1\u201329 (2014)","journal-title":"J. Math. Cryptol."},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1007\/978-3-030-17659-4_26","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"L De Feo","year":"2019","unstructured":"De Feo, L., Galbraith, S.D.: SeaSign: compact isogeny signatures from class group actions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 759\u2013789. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17659-4_26"},{"key":"19_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-030-25510-7_15","volume-title":"Post-Quantum Cryptography","author":"T Decru","year":"2019","unstructured":"Decru, T., Panny, L., Vercauteren, F.: Faster SeaSign signatures through improved rejection sampling. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 271\u2013285. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-25510-7_15"},{"issue":"6","key":"19_CR16","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W Diffie","year":"1976","unstructured":"Diffie, W., Hellman, M.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644\u2013654 (1976)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"19_CR17","unstructured":"Esser, A., Ramos-Calderer, S., Bellini, E., Latorre, J.I., Manzano, M.: An optimized quantum implementation of ISD on scalable quantum resources. IACR Cryptology ePrint Archive, p. 1608 (2021)"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/3-540-49116-3_45","volume-title":"STACS 99","author":"M Ettinger","year":"1999","unstructured":"Ettinger, M., H\u00f8yer, P.: On quantum algorithms for noncommutative hidden subgroups. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 478\u2013487. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-49116-3_45"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Ettinger, M., H\u00f8yer, P., Knill, E.: The quantum query complexity of the hidden subgroup problem is polynomial (2004). arXiv:quant-ph\/0401083","DOI":"10.1016\/j.ipl.2004.01.024"},{"key":"19_CR20","unstructured":"Helm, A., May, A.: Subset sum quantumly in $$1.17^n$$. In: Jeffery, S. (ed.) TQC 2018. Leibniz International Proceedings in Informatics (LIPIcs), vol. 111, pp. 5:1\u20135:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018)"},{"key":"19_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/978-3-030-44223-1_24","volume-title":"Post-Quantum Cryptography","author":"A Helm","year":"2020","unstructured":"Helm, A., May, A.: The power of few qubits and collisions \u2013 subset sum below Grover\u2019s bound. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 445\u2013460. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-44223-1_24"},{"key":"19_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-13190-5_12","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"N Howgrave-Graham","year":"2010","unstructured":"Howgrave-Graham, N., Joux, A.: New generic algorithms for hard knapsacks. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 235\u2013256. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_12"},{"issue":"1","key":"19_CR23","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/S0097539703436345","volume":"35","author":"G Kuperberg","year":"2005","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170\u2013188 (2005). https:\/\/doi.org\/10.1137\/S0097539703436345","journal-title":"SIAM J. Comput."},{"key":"19_CR24","unstructured":"Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: TQC. LIPIcs, vol. 22, pp. 20\u201334. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2013)"},{"key":"19_CR25","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. 5677, pp. 577\u2013594. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_34"},{"key":"19_CR26","unstructured":"NIST: Submission requirements and evaluation criteria for the post-quantum cryptography standardization process (2016). https:\/\/csrc.nist.gov\/CSRC\/media\/Projects\/Post-Quantum-Cryptography\/documents\/call-for-proposals-final-dec-2016.pdf"},{"key":"19_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/978-3-030-45724-2_16","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"C Peikert","year":"2020","unstructured":"Peikert, C.: He gives C-sieves on the CSIDH. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 463\u2013492. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45724-2_16"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Regev, O.: Quantum computation and lattice problems. In: FOCS, pp. 520\u2013529. IEEE Computer Society (2002)","DOI":"10.1109\/SFCS.2002.1181976"},{"issue":"6","key":"19_CR29","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1145\/1039488.1039490","volume":"51","author":"O Regev","year":"2004","unstructured":"Regev, O.: New lattice-based cryptographic constructions. J. ACM 51(6), 899\u2013942 (2004)","journal-title":"J. ACM"},{"key":"19_CR30","unstructured":"Regev, O.: A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space (2004). arXiv:quant-ph\/0406151"},{"issue":"2","key":"19_CR31","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"key":"19_CR32","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124\u2013134 (1994)","DOI":"10.1109\/SFCS.1994.365700"},{"key":"19_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-642-10366-7_36","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"D Stehl\u00e9","year":"2009","unstructured":"Stehl\u00e9, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 617\u2013635. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10366-7_36"},{"key":"19_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45708-9_19","volume-title":"Advances in Cryptology \u2014 CRYPTO 2002","author":"D Wagner","year":"2002","unstructured":"Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288\u2013304. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45708-9_19"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-40003-2_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T22:49:06Z","timestamp":1729896546000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-40003-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031400025","9783031400032"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-40003-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"10 August 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PQCrypto","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Post-Quantum Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"College Park, MD","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 August 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pqcrypto2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/pqcrypto2023.umiacs.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.16","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.30","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}