{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T16:24:36Z","timestamp":1761582276091,"version":"3.40.3"},"publisher-location":"Cham","reference-count":43,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031308710"},{"type":"electronic","value":"9783031308727"}],"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-30872-7_3","type":"book-chapter","created":{"date-parts":[[2023,4,18]],"date-time":"2023-04-18T09:03:56Z","timestamp":1681808636000},"page":"57-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Concrete Quantum Cryptanalysis of\u00a0Binary Elliptic Curves via\u00a0Addition Chain"],"prefix":"10.1007","author":[{"given":"Ren","family":"Taguchi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9310-6976","authenticated-orcid":false,"given":"Atsushi","family":"Takayasu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,19]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"012305","DOI":"10.1103\/PhysRevA.100.012305","volume":"100","author":"M Amico","year":"2019","unstructured":"Amico, M., Saleem, Z.H., Kumph, M.: Experimental study of Shor\u2019s factoring algorithm using the IBM Q experience. Phys. Rev. A 100, 012305 (2019)","journal-title":"Phys. Rev. A"},{"issue":"4","key":"3_CR2","first-page":"1041","volume":"63","author":"R Azarderakhsh","year":"2012","unstructured":"Azarderakhsh, R., J\u00e4rvinen, K., Dimitrov, V.: Fast inversion in $${\\text{ gf }(2^m)}$$ with normal basis using hybrid-double multipliers. IEEE Trans. Comput. 63(4), 1041\u20131047 (2012)","journal-title":"IEEE Trans. Comput."},{"key":"3_CR3","doi-asserted-by":"publisher","unstructured":"Babbush, R., et al.: Encoding electronic spectra in quantum circuits with linear T complexity. Phys. Rev. X 8(4) (2018). https:\/\/doi.org\/10.1103\/physrevx.8.041015","DOI":"10.1103\/physrevx.8.041015"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Banegas, G., Bernstein, D.J., van Hoof, I., Lange, T.: Concrete quantum cryptanalysis of binary elliptic curves. IACR Trans. CHES 2021(1), 451\u2013472 (2020)","DOI":"10.46586\/tches.v2021.i1.451-472"},{"key":"3_CR5","first-page":"175","volume":"3","author":"S Beauregard","year":"2003","unstructured":"Beauregard, S.: Circuit for Shor\u2019s algorithm using $$2n+3$$ qubits. Quantum Inf. Comput. 3, 175\u2013185 (2003)","journal-title":"Quantum Inf. Comput."},{"issue":"3","key":"3_CR6","doi-asserted-by":"publisher","first-page":"340","DOI":"10.46586\/tches.v2019.i3.340-398","volume":"2019","author":"DJ Bernstein","year":"2019","unstructured":"Bernstein, D.J., Yang, B.: Fast constant-time GCD computation and modular inversion. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2019(3), 340\u2013398 (2019)","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-030-56880-1_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"F Boudot","year":"2020","unstructured":"Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thom\u00e9, E., Zimmermann, P.: Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 62\u201391. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56880-1_3"},{"key":"3_CR8","unstructured":"Cameron, F., Patrick, D.: FIPS pub 186-4 Digital Signature Standard (DSS). In: NIST, pp. 92\u2013101 (2013)"},{"issue":"5","key":"3_CR9","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1109\/TVLSI.2021.3061987","volume":"29","author":"AC Canto","year":"2021","unstructured":"Canto, A.C., Kermani, M.M., Azarderakhsh, R.: CRC-based error detection constructions for FLT and ITA finite field inversions over $$\\text{ GF }(2^m)$$. IEEE Trans. VLSI Syst. 29(5), 1033\u20131037 (2021)","journal-title":"IEEE Trans. VLSI Syst."},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"18917","DOI":"10.1364\/OE.390209","volume":"28","author":"ZC Duan","year":"2020","unstructured":"Duan, Z.C., et al.: Proof-of-principle demonstration of compiled Shor\u2019s algorithm using a quantum dot single-photon source. Opt. Express 28, 18917\u201318930 (2020)","journal-title":"Opt. Express"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"032324","DOI":"10.1103\/PhysRevA.86.032324","volume":"86","author":"AG Fowler","year":"2012","unstructured":"Fowler, A.G., Mariantoni, M., Martinis, J.M., Cleland, A.N.: Surface codes: towards practical large-scale quantum computation. Phys. Rev. A 86, 032324 (2012)","journal-title":"Phys. Rev. A"},{"key":"3_CR12","unstructured":"Gidney, C.: Windowed quantum arithmetic (2019)"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"433","DOI":"10.22331\/q-2021-04-15-433","volume":"5","author":"C Gidney","year":"2021","unstructured":"Gidney, C., Eker\u00e5, M.: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5, 433 (2021)","journal-title":"Quantum"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"140503","DOI":"10.1103\/PhysRevLett.127.140503","volume":"127","author":"E Gouzien","year":"2021","unstructured":"Gouzien, E., Sangouard, N.: Factoring 2048-bit RSA integers in 177 days with 13 436 qubits and a multimode memory. Phys. Rev. Lett. 127, 140503 (2021)","journal-title":"Phys. Rev. Lett."},{"issue":"17","key":"3_CR15","doi-asserted-by":"publisher","first-page":"3228","DOI":"10.1103\/physrevlett.76.3228","volume":"76","author":"RB Griffiths","year":"1996","unstructured":"Griffiths, R.B., Niu, C.S.: Semiclassical Fourier transform for quantum computation. Phys. Rev. Lett. 76(17), 3228\u20133231 (1996). https:\/\/doi.org\/10.1103\/physrevlett.76.3228","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"3_CR16","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1023\/A:1013860532636","volume":"25","author":"J Guajardo","year":"2002","unstructured":"Guajardo, J., Paar, C.: Itoh-Tsujii inversion in standard basis and its application in cryptography and codes. Des. Codes Crypt. 25(2), 207\u2013216 (2002)","journal-title":"Des. Codes Crypt."},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s11128-021-03398-1","volume":"21","author":"J Ha","year":"2022","unstructured":"Ha, J., Lee, J., Heo, J.: Resource analysis of quantum computing with noisy qubits for Shor\u2019s factoring algorithms. Quantum Inf. Process. 21(2), 60 (2022)","journal-title":"Quantum Inf. Process."},{"issue":"7\u20138","key":"3_CR18","first-page":"673","volume":"18","author":"T Haener","year":"2017","unstructured":"Haener, T., Roetteler, M., Svore, K.M.: Factoring using $$2n+2$$ qubits with Toffoli based modular multiplication. Quantum Inf. Comput. 18(7\u20138), 673\u2013684 (2017)","journal-title":"Quantum Inf. Comput."},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/978-3-030-44223-1_23","volume-title":"Post-Quantum Cryptography","author":"T H\u00e4ner","year":"2020","unstructured":"H\u00e4ner, T., Jaques, S., Naehrig, M., Roetteler, M., Soeken, M.: Improved quantum circuits for elliptic curve discrete logarithms. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 425\u2013444. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-44223-1_23"},{"issue":"4","key":"3_CR20","first-page":"367","volume":"62","author":"J Hu","year":"2015","unstructured":"Hu, J., Guo, W., Wei, J., Cheung, R.C.: Fast and generic inversion architectures over $$\\text{ GF }(2^m)$$ using modified Itoh\u2013Tsujii algorithms. IEEE Trans. Circuits Syst. II Express Briefs 62(4), 367\u2013371 (2015)","journal-title":"IEEE Trans. Circuits Syst. II Express Briefs"},{"key":"3_CR21","unstructured":"Iggy, V.H.: Quantum modulo karatsuba multiplier for binary polynomials (2019). https:\/\/github.com\/ikbenbeter\/QMKMBP"},{"key":"3_CR22","unstructured":"Iggy, V.H.: Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count. CoRR abs\/1910.02849 (2019)"},{"issue":"3","key":"3_CR23","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0890-5401(88)90024-7","volume":"78","author":"T Itoh","year":"1988","unstructured":"Itoh, T., Tsujii, S.: A fast algorithm for computing multiplicative inverses in $$\\text{ GF }(2^m)$$ using normal bases. Inf. Comput. 78(3), 171\u2013177 (1988)","journal-title":"Inf. Comput."},{"issue":"177","key":"3_CR24","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1090\/S0025-5718-1987-0866109-5","volume":"48","author":"N Koblitz","year":"1987","unstructured":"Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203\u2013209 (1987)","journal-title":"Math. Comput."},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Kunihiro, N.: Exact analyses of computational time for factoring in quantum computers. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 88-A(1), 105\u2013111 (2005)","DOI":"10.1093\/ietfec\/E88-A.1.105"},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"250505","DOI":"10.1103\/PhysRevLett.99.250505","volume":"99","author":"BP Lanyon","year":"2007","unstructured":"Lanyon, B.P., et al.: Experimental demonstration of a compiled version of Shor\u2019s algorithm with quantum entanglement. Phys. Rev. Lett. 99, 250505 (2007)","journal-title":"Phys. Rev. Lett."},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"250504","DOI":"10.1103\/PhysRevLett.99.250504","volume":"99","author":"CY Lu","year":"2007","unstructured":"Lu, C.Y., Browne, D.E., Yang, T., Pan, J.W.: Demonstration of a compiled version of Shor\u2019s quantum factoring algorithm using photonic qubits. Phys. Rev. Lett. 99, 250504 (2007)","journal-title":"Phys. Rev. Lett."},{"key":"3_CR28","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1038\/nphys2385","volume":"8","author":"E Lucero","year":"2012","unstructured":"Lucero, E., et al.: Computing prime factors with a Josephson phase qubit quantum processor. Nat. Phys. 8, 719\u2013723s (2012)","journal-title":"Nat. Phys."},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1038\/nphoton.2012.259","volume":"6","author":"E Martin-Lopez","year":"2012","unstructured":"Martin-Lopez, E., Laing, A., Lawson, T., Alvarez, R., Zhou, X.Q., O\u2019Brien, J.L.: Experimental realisation of Shor\u2019s quantum factoring algorithm using qubit recycling. Nat. Photon 6, 773\u2013776 (2012)","journal-title":"Nat. Photon"},{"key":"3_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/3-540-39799-X_31","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201985 Proceedings","author":"VS Miller","year":"1986","unstructured":"Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417\u2013426. Springer, Heidelberg (1986). https:\/\/doi.org\/10.1007\/3-540-39799-X_31"},{"key":"3_CR31","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1126\/science.aad9480","volume":"351","author":"T Monz","year":"2016","unstructured":"Monz, T., et al.: Realization of a scalable Shor algorithm. Science 351, 1068\u20131070 (2016)","journal-title":"Science"},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1126\/science.1173731","volume":"325","author":"A Politi","year":"2009","unstructured":"Politi, A., Matthews, J.C.F., O\u2019Brien, J.L.: Shor\u2019s quantum factoring algorithm on a photonic chip. Science 325, 1221 (2009)","journal-title":"Science"},{"key":"3_CR33","doi-asserted-by":"crossref","unstructured":"Proos, J., Zalka, C.: Shor\u2019s discrete logarithm quantum algorithm for elliptic curves. Quantum Inf. Comput. 3(4) (2003)","DOI":"10.26421\/QIC3.4-3"},{"key":"3_CR34","unstructured":"Putranto, D.S.C., Wardhani, R.W., Larasati, H.T., Kim, H.: Another concrete quantum cryptanalysis of binary elliptic curves. Cryptology ePrint Archive, Paper 2022\/501 (2022). https:\/\/eprint.iacr.org\/2022\/501"},{"issue":"2","key":"3_CR35","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":"3_CR36","doi-asserted-by":"crossref","unstructured":"Rodriguez-Henriquez, F., Cruz-Cortes, N., Saqib, N.: A fast implementation of multiplicative inversion over $$\\text{ GF }(2^m)$$. In: ITCC 2005, vol. 1, pp. 574\u2013579. IEEE (2005)","DOI":"10.1109\/ITCC.2005.8"},{"key":"3_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-319-70697-9_9","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2017","author":"M Roetteler","year":"2017","unstructured":"Roetteler, M., Naehrig, M., Svore, K.M., Lauter, K.: Quantum resource estimates for computing elliptic curve discrete logarithms. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 241\u2013270. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70697-9_9"},{"key":"3_CR38","unstructured":"Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring. In: FOCS 1994, pp. 124\u2013134 (1994)"},{"key":"3_CR39","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1038\/nature12290","volume":"499","author":"JA Smolin","year":"2013","unstructured":"Smolin, J.A., Smith, G., Vargo, A.: Oversimplifying quantum factoring. Nature 499, 163\u2013165 (2013)","journal-title":"Nature"},{"issue":"2","key":"3_CR40","first-page":"184","volume":"6","author":"Y Takahashi","year":"2006","unstructured":"Takahashi, Y., Kunihiro, N.: A quantum circuit for Shor\u2019s factoring algorithm using 2n + 2 qubits. Quantum Inf. Comput. 6(2), 184\u2013192 (2006)","journal-title":"Quantum Inf. Comput."},{"key":"3_CR41","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1038\/414883a","volume":"414","author":"L Vandersypen","year":"2001","unstructured":"Vandersypen, L., Steffen, M., Breyta, G., Yannoni, C.S., Sherwood, M.H., Chuang, I.L.: Experimental realization of Shor\u2019s quantum factoring algorithm using nuclear magnetic resonance. Nature 414, 883\u2013887 (2001)","journal-title":"Nature"},{"key":"3_CR42","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1103\/PhysRevA.54.147","volume":"54","author":"V Vedral","year":"1996","unstructured":"Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Phys. Rev. A 54, 147\u2013153 (1996)","journal-title":"Phys. Rev. A"},{"key":"3_CR43","doi-asserted-by":"publisher","unstructured":"Zalka, C.: Fast versions of Shor\u2019s quantum factoring algorithm (1998). https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/9806084","DOI":"10.48550\/ARXIV.QUANT-PH\/9806084"}],"container-title":["Lecture Notes in Computer Science","Topics in Cryptology \u2013 CT-RSA 2023"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30872-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,18]],"date-time":"2023-04-18T18:03:15Z","timestamp":1681840995000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30872-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031308710","9783031308727"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30872-7_3","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":"19 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CT-RSA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cryptographers\u2019 Track at the RSA Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"San Francisco, CA","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":"24 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ctrsa2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ct-rsa-2023.eecs.oregonstate.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"hotcrp","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"76","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":"26","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":"34% - 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","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":"6","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)"}}]}}