Hash-Based Multi-Signatures for Post-Quantum Ethereum
Authors
Justin Drake, Dmitry Khovratovich, Mikhail Kudinov, Benedikt Wagner
Dmitry Khovratovich
Ethereum Foundation, Switzerland
dmitry dot khovratovich at ethereum dot org
dmitry dot khovratovich at ethereum dot org
Mikhail Kudinov
Eindhoven University of Technology, Netherlands
mishel dot kudinov at gmail dot com
mishel dot kudinov at gmail dot com
Benedikt Wagner
Ethereum Foundation, Switzerland
benedikt dot wagner at ethereum dot org
benedikt dot wagner at ethereum dot org
Keywords:
Post-Quantum
Ethereum
Multi-Signatures
Hash-Based
Tweakable Hash
Poseidon
Succinct Arguments
Abstract
With the threat posed by quantum computers on the horizon, systems like Ethereum must transition to cryptographic primitives resistant to quantum attacks. One of the most critical of these primitives is the non-interactive multi-signature scheme used in Ethereum's proof-of-stake consensus, currently implemented with BLS signatures. This primitive enables validators to independently sign blocks, with their signatures then publicly aggregated into a compact aggregate signature.
In this work, we introduce a family of hash-based signature schemes as post-quantum alternatives to BLS. We consider the folklore method of aggregating signatures via (hash-based) succinct arguments, and our work is focused on instantiating the underlying signature scheme. The proposed schemes are variants of the XMSS signature scheme, analyzed within a novel and unified framework. While being generic, this framework is designed to minimize security loss, facilitating efficient parameter selection. A key feature of our work is the avoidance of random oracles in the security proof. Instead, we define explicit standard model requirements for the underlying hash functions. This eliminates the paradox of simultaneously treating hash functions as random oracles and as explicit circuits for aggregation. Furthermore, this provides cryptanalysts with clearly defined targets for evaluating the security of hash functions. Finally, we provide recommendations for practical instantiations of hash functions and concrete parameter settings, supported by known and novel heuristic bounds on the standard model properties.
References
[AAB+24]
Marius A. Aardal, Diego F. Aranha, Katharina Boudgoust, Sebastian Kolby, and Akira Takahashi. Aggregating Falcon Signatures with LaBRADOR. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part I, volume 14920 of LNCS, pages 71–106. August 2024. Springer, Cham. DOI: 10.1007/978-3-031-68376-3_3
[ACFY24a]
Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, and Eylon Yogev. STIR: Reed-Solomon Proximity Testing with Fewer Queries. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part X, volume 14929 of LNCS, pages 380–413. August 2024. Springer, Cham. DOI: 10.1007/978-3-031-68403-6_12
[ACFY24b]
Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, and Eylon Yogev. WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification. Cryptology ePrint Archive, Paper 2024/1586. 2024.
[ACL+22]
Martin R. Albrecht, Valerio Cini, Russell W. F. Lai, Giulio Malavolta, and Sri Aravinda Krishnan Thyagarajan. Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable - (Extended Abstract). In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 102–132. August 2022. Springer, Cham. DOI: 10.1007/978-3-031-15979-4_4
[ADP24]
Nabil Alkeilani Alkadri, Nico Döttling, and Sihang Pu. Practical Lattice-Based Distributed Signatures for a Small Number of Signers. In Christina Pöpper and Lejla Batina, editors, ACNS 24International Conference on Applied Cryptography and Network Security, Part I, volume 14583 of LNCS, pages 376–402. March 2024. Springer, Cham. DOI: 10.1007/978-3-031-54770-6_15
[AdSGK24]
Shahla Atapoor, Cyprien Delpech de Saint Guilhem, and Al Kindi. STARK-based Signatures from the RPO Permutation. Cryptology ePrint Archive, Paper 2024/1553. 2024.
[AGH10]
Jae Hyun Ahn, Matthew Green, and Susan Hohenberger. Synchronized aggregate signatures: new definitions, constructions and applications. In Ehab Al-Shaer, Angelos D. Keromytis, and Vitaly Shmatikov, editors, ACM CCS 2010, pages 473–484. October 2010. ACM Press. DOI: 10.1145/1866307.1866360
[BBd+23]
Carsten Baum, Lennart Braun, Cyprien Delpech de Saint Guilhem, Michael Klooß, Christian Majenz, Shibam Mukherjee, Emmanuela Orsini, Sebastian Ramacher, Christian Rechberger, Lawrence Roy, and Peter Scholl. FAEST. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures. 2023.
[BBHR18]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, ICALP 2018, volume 107 of LIPIcs, pages 14:1–14:17. July 2018. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.ICALP.2018.14
[BBK+23]
Zvika Brakerski, Maya Farber Brodsky, Yael Tauman Kalai, Alex Lombardi, and Omer Paneth. SNARGs for Monotone Policy Batch NP. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part II, volume 14082 of LNCS, pages 252–283. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38545-2_9
[BC24]
Dan Boneh and Binyi Chen. LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems. Cryptology ePrint Archive, Paper 2024/257. 2024.
[BCJP24]
Maya Farber Brodsky, Arka Rai Choudhuri, Abhishek Jain, and Omer Paneth. Monotone-Policy Aggregate Signatures. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part IV, volume 14654 of LNCS, pages 168–195. May 2024. Springer, Cham. DOI: 10.1007/978-3-031-58737-5_7
[BDE+11]
Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, and Markus Rückert. On the Security of the Winternitz One-Time Signature Scheme. In Abderrahmane Nitaj and David Pointcheval, editors, AFRICACRYPT 11, volume 6737 of LNCS, pages 363–378. July 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-21969-6_23
[BDF+11]
Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random Oracles in a Quantum World. In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011, volume 7073 of LNCS, pages 41–69. December 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-25385-0_3
[BDH11]
Johannes A. Buchmann, Erik Dahmen, and Andreas Hülsing. XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions. In Bo-Yin Yang, editor, Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011, pages 117–129. 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-25405-5_8
[Beu22]
Ward Beullens. MAYO: Practical Post-quantum Signatures from Oil-and-Vinegar Maps. In Riham AlTawy and Andreas Hülsing, editors, SAC 2021, volume 13203 of LNCS, pages 355–376. 2022. Springer, Cham. DOI: 10.1007/978-3-030-99277-4_17
[BH19]
Daniel J. Bernstein and Andreas Hülsing. Decisional Second-Preimage Resistance: When Does SPR Imply PRE?. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part III, volume 11923 of LNCS, pages 33–62. December 2019. Springer, Cham. DOI: 10.1007/978-3-030-34618-8_2
[BHH+15]
Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O'Hearn. SPHINCS: Practical Stateless Hash-Based Signatures. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 368–397. April 2015. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-46800-5_15
[BHK+19]
Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe. The SPHINCS$^+$ Signature Framework. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 2129–2146. November 2019. ACM Press. DOI: 10.1145/3319535.3363229
[BHRvV21]
Joppe W. Bos, Andreas Hülsing, Joost Renes, and Christine van Vredendaal. Rapidly Verifiable XMSS Signatures. IACR TCHES, 2021(1):137–168, 2021. DOI: 10.46586/tches.v2021.i1.137-168
[BK20]
Dan Boneh and Sam Kim. One-time and interactive aggregate signatures from lattices. 2020.
[BKPV23]
Luk Bettale, Delaram Kahrobaei, Ludovic Perret, and Javier Verbel. Biscuit. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures. 2023.
[BS20]
Dan Boneh and Victor Shoup. A graduate course in applied cryptography. 2020.
[BS23]
Ward Beullens and Gregor Seiler. LaBRADOR: Compact Proofs for R1CS from Module-SIS. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part V, volume 14085 of LNCS, pages 518–548. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38554-4_17
[BTT22]
Cecilia Boschini, Akira Takahashi, and Mehdi Tibouchi. MuSig-L: Lattice-Based Multi-signature with Single-Round Online Phase. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 276–305. August 2022. Springer, Cham. DOI: 10.1007/978-3-031-15979-4_10
[CF24]
Alessandro Chiesa and Giacomo Fenzi. zkSNARKs in the ROM with Unconditional UC-Security. In Theory of Cryptography Conference, pages 67–89. 2024. Springer. DOI: 10.1007/978-3-031-78011-0_3
[CFS01]
Nicolas Courtois, Matthieu Finiasz, and Nicolas Sendrier. How to Achieve a McEliece-Based Digital Signature Scheme. In Colin Boyd, editor, ASIACRYPT 2001, volume 2248 of LNCS, pages 157–174. December 2001. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45682-1_10
[Che23]
Yanbo Chen. DualMS: Efficient Lattice-Based Two-Round Multi-signature with Trapdoor-Free Simulation. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part V, volume 14085 of LNCS, pages 716–747. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38554-4_23
[CMS19]
Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. Succinct Arguments in the Quantum Random Oracle Model. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part II, volume 11892 of LNCS, pages 1–29. December 2019. Springer, Cham. DOI: 10.1007/978-3-030-36033-7_1
[DFMS24]
Giuseppe D'Alconzo, Andrea Flamini, Alessio Meneghetti, and Edoardo Signorini. A Framework for Group Action-Based Multi-Signatures and Applications to LESS, MEDS, and ALTEQ. Cryptology ePrint Archive, Paper 2024/1691. 2024.
[DGKV22]
Lalita Devadas, Rishab Goyal, Yael Kalai, and Vinod Vaikuntanathan. Rate-1 Non-Interactive Arguments for Batch-NP and Applications. In 63rd FOCS, pages 1057–1068. 2022. IEEE Computer Society Press. DOI: 10.1109/FOCS54457.2022.00103
[DGNW20]
Manu Drijvers, Sergey Gorbunov, Gregory Neven, and Hoeteck Wee. Pixel: Multi-signatures for Consensus. In Srdjan Capkun and Franziska Roesner, editors, USENIX Security 2020, pages 2093–2110. August 2020. USENIX Association.
[DHSS20]
Yarkın Doröz, Jeffrey Hoffstein, Joseph H. Silverman, and Berk Sunar. MMSAT: A Scheme for Multimessage Multiuser Signature Aggregation. Cryptology ePrint Archive, Report 2020/520. 2020.
[DKL+20]
Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin Wesolowski. SQISign: Compact Post-quantum Signatures from Quaternions and Isogenies. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part I, volume 12491 of LNCS, pages 64–93. December 2020. Springer, Cham. DOI: 10.1007/978-3-030-64837-4_3
[DLL+17]
Léo Ducas, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS – Dilithium: Digital Signatures from Module Lattices. Cryptology ePrint Archive, Report 2017/633. 2017.
[DLRW24]
Pierrick Dartois, Antonin Leroux, Damien Robert, and Benjamin Wesolowski. SQIsignHD: New Dimensions in Cryptography. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part I, volume 14651 of LNCS, pages 3–32. May 2024. Springer, Cham. DOI: 10.1007/978-3-031-58716-0_1
[DOTT21]
Ivan Damgård, Claudio Orlandi, Akira Takahashi, and Mehdi Tibouchi. Two-Round n-out-of-n and Multi-signatures and Trapdoor Commitment from Lattices. In Juan Garay, editor, PKC 2021, Part I, volume 12710 of LNCS, pages 99–130. May 2021. Springer, Cham. DOI: 10.1007/978-3-030-75245-3_5
[DSS05]
C. Dods, Nigel P. Smart, and Martijn Stam. Hash Based Digital Signature Schemes. In Nigel P. Smart, editor, 10th IMA International Conference on Cryptography and Coding, volume 3796 of LNCS, pages 96–115. December 2005. Springer, Berlin, Heidelberg. DOI: 10.1007/11586821_8
[FHSZ23]
Nils Fleischhacker, Gottfried Herold, Mark Simkin, and Zhenfei Zhang. Chipmunk: Better Synchronized Multi-Signatures from Lattices. In Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda, editors, ACM CCS 2023, pages 386–400. November 2023. ACM Press. DOI: 10.1145/3576915.3623219
[FKNP24]
Giacomo Fenzi, Christian Knabenhans, Ngoc Khanh Nguyen, and Duc Tu Pham. Lova: Lattice-Based Folding Scheme from Unstructured Lattices. Cryptology ePrint Archive, Paper 2024/1964. 2024.
[Flu17]
Scott Fluhrer. Reassessing Grover's Algorithm. Cryptology ePrint Archive, Report 2017/811. 2017.
[FS87]
Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, CRYPTO'86, volume 263 of LNCS, pages 186–194. August 1987. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-47721-7_12
[FSZ22]
Nils Fleischhacker, Mark Simkin, and Zhenfei Zhang. Squirrel: Efficient Synchronized Multi-Signatures from Lattices. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022, pages 1109–1123. November 2022. ACM Press. DOI: 10.1145/3548606.3560655
[GHHM21]
Alex B. Grilo, Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz. Tight Adaptive Reprogramming in the QROM. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part I, volume 13090 of LNCS, pages 637–667. December 2021. Springer, Cham. DOI: 10.1007/978-3-030-92062-3_22
[GKR+21]
Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. In Michael Bailey and Rachel Greenstadt, editors, USENIX Security 2021, pages 519–535. August 2021. USENIX Association.
[GKS23]
Lorenzo Grassi, Dmitry Khovratovich, and Markus Schofnegger. Poseidon2: A Faster Version of the Poseidon Hash Function. In Nadia El Mrabet, Luca De Feo, and Sylvain Duquesne, editors, AFRICACRYPT 23, volume 14064 of LNCS, pages 177–203. July 2023. Springer, Cham. DOI: 10.1007/978-3-031-37679-5_8
[GPV08]
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 197–206. May 2008. ACM Press. DOI: 10.1145/1374376.1374407
[GR06]
Craig Gentry and Zulfikar Ramzan. Identity-Based Aggregate Signatures. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, PKC 2006, volume 3958 of LNCS, pages 257–273. April 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11745853_17
[Gro96]
Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In 28th ACM STOC, pages 212–219. May 1996. ACM Press. DOI: 10.1145/237814.237866
[GW11]
Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, pages 99–108. June 2011. ACM Press. DOI: 10.1145/1993636.1993651
[HBD+22]
Andreas Hülsing, Daniel J. Bernstein, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Panos Kampanakis, Stefan Kölbl, Tanja Lange, Martin M. Lauridsen, Florian Mendel, Ruben Niederhagen, Christian Rechberger, Joost Rijneveld, Peter Schwabe, Jean-Philippe Aumasson, Bas Westerbaan, and Ward Beullens. SPHINCS+. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022. 2022.
[HBG+18]
Andreas Huelsing, Denis Butin, Stefan-Lukas Gazdag, Joost Rijneveld, and Aziz Mohaisen. XMSS: eXtended Merkle Signature Scheme. RFC 8391. May 2018.
[HK22]
Andreas Hülsing and Mikhail A. Kudinov. Recovering the Tight Security Proof of SPHINCS$^\textrm{+}$. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part IV, volume 13794 of LNCS, pages 3–33. December 2022. Springer, Cham. DOI: 10.1007/978-3-031-22972-5_1
[HKRY23]
Andreas Hülsing, Mikhail A. Kudinov, Eyal Ronen, and Eylon Yogev. SPHINCS+C: Compressing SPHINCS+ With (Almost) No Cost. In 2023 IEEE Symposium on Security and Privacy, pages 1435–1453. May 2023. IEEE Computer Society Press. DOI: 10.1109/SP46215.2023.10179381
[HLP24]
Ulrich Haböck, David Levit, and Shahar Papini. Circle STARKs. Cryptology ePrint Archive, Report 2024/278. 2024.
[HRB13]
Andreas Hülsing, Lea Rausch, and Johannes Buchmann. Optimal Parameters for XMSS MT. In Alfredo Cuzzocrea, Christian Kittl, Dimitris E. Simos, Edgar R. Weippl, and Lida Xu, editors, Security Engineering and Intelligence Informatics - CD-ARES 2013 Workshops: MoCrySEn and SeCIHD, Regensburg, Germany, September 2-6, 2013. Proceedings, volume 8128 of Lecture Notes in Computer Science, pages 194–208. 2013. Springer. DOI: 10.1007/978-3-642-40588-4_14
[HRS16]
Andreas Hülsing, Joost Rijneveld, and Fang Song. Mitigating Multi-target Attacks in Hash-Based Signatures. In Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang, editors, PKC 2016, Part I, volume 9614 of LNCS, pages 387–416. March 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49384-7_15
[H{\"u}l13]
Andreas Hülsing. W-OTS+ - Shorter Signatures for Hash-Based Signature Schemes. In Amr Youssef, Abderrahmane Nitaj, and Aboul Ella Hassanien, editors, AFRICACRYPT 13, volume 7918 of LNCS, pages 173–188. June 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-38553-7_10
[HW18]
Susan Hohenberger and Brent Waters. Synchronized Aggregate Signatures from the RSA Assumption. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 197–229. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78375-8_7
[KBM23]
Dmitry Khovratovich, Mario Marhuenda Beltrán, and Bart Mennink. Generic Security of the SAFE API and Its Applications. In ASIACRYPT (8), volume 14445 of Lecture Notes in Computer Science, pages 301–327. 2023. Springer. DOI: 10.1007/978-981-99-8742-9_10
[KCLM22]
Irakliy Khaburzaniya, Konstantinos Chalkias, Kevin Lewi, and Harjasleen Malvai. Aggregating and Thresholdizing Hash-based Signatures using STARKs. In Yuji Suga, Kouichi Sakurai, Xuhua Ding, and Kazue Sako, editors, ASIACCS 22, pages 393–407. 2022. ACM Press. DOI: 10.1145/3488932.3524128
[KKF21]
Mikhail Aleksandrovich Kudinov, Evgeniy Olegovich Kiktenko, and Aleksey Konstantinovich Fedorov. Security analysis of the W-OTS$^+$ signature scheme: Updating security bounds. Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography], 12(2):129–145, June 2021. DOI: 10.4213/mvk362
[KLM06]
Phillip Kaye, Raymond Laflamme, and Michele Mosca. An Introduction to Quantum Computing. Oxford University Press. 2006.
[LDK+20]
Vadim Lyubashevsky, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Peter Schwabe, Gregor Seiler, Damien Stehlé, and Shi Bai. CRYSTALS-DILITHIUM. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
[LLL+24]
Qiqi Lai, Feng-Hao Liu, Yang Lu, Haiyang Xue, and Yong Yu. Scalable Two-Round $n$-out-of-$n$ and Multi-Signatures from Lattices in the Quantum Random Oracle Model. Cryptology ePrint Archive, Paper 2024/1574. 2024.
[LM08]
Vadim Lyubashevsky and Daniele Micciancio. Asymptotically Efficient Lattice-Based Digital Signatures. In Ran Canetti, editor, TCC 2008, volume 4948 of LNCS, pages 37–54. March 2008. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-78524-8_3
[LMQW22]
Alex Lombardi, Ethan Mook, Willy Quach, and Daniel Wichs. Post-quantum Insecurity from LWE. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022, Part I, volume 13747 of LNCS, pages 3–32. November 2022. Springer, Cham. DOI: 10.1007/978-3-031-22318-1_1
[Mer79]
Ralph Charles Merkle. Secrecy, authentication, and public key systems.. Stanford university 1979.
[{Nat}15]
National Institute of Standards and Technology. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. Federal Information Processing Standards Publication (FIPS), 2015.
[{Nat}16]
National Institute of Standards and Technology. Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. National Institute of Standards and Technology Reports, 2016. available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf
[PFH+20]
Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. FALCON. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
[SEMR24]
Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer, and Krijn Reijnders. AprèsSQI: Extra Fast Verification for SQIsign Using Extension-Field Signing. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part I, volume 14651 of LNCS, pages 63–93. May 2024. Springer, Cham. DOI: 10.1007/978-3-031-58716-0_3
[Ste94]
Jacques Stern. A New Identification Scheme Based on Syndrome Decoding. In Douglas R. Stinson, editor, CRYPTO'93, volume 773 of LNCS, pages 13–21. August 1994. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48329-2_2
[TS23]
Toi Tomita and Junji Shikata. Compact Aggregate Signature from Module-Lattices. Cryptology ePrint Archive, Report 2023/471. 2023.
[Unr17]
Dominique Unruh. Post-quantum Security of Fiat-Shamir. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, pages 65–95. December 2017. Springer, Cham. DOI: 10.1007/978-3-319-70694-8_3
[Unr21]
Dominique Unruh. Compressed Permutation Oracles (And the Collision-Resistance of Sponge/SHA3). Cryptology ePrint Archive, Paper 2021/062. 2021.
[WW22]
Brent Waters and David J. Wu. Batch Arguments for NP and More from Standard Bilinear Group Assumptions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 433–463. August 2022. Springer, Cham. DOI: 10.1007/978-3-031-15979-4_15
[Zal99]
Christof Zalka. Grover's quantum searching algorithm is optimal. Phys. Rev. A, 60:2746–2751, October 1999. DOI: 10.1103/PhysRevA.60.2746
[ZCF24]
Hadas Zeilberger, Binyi Chen, and Ben Fisch. BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part X, volume 14929 of LNCS, pages 138–169. August 2024. Springer, Cham. DOI: 10.1007/978-3-031-68403-6_5
[ZCY23]
Kaiyi Zhang, Hongrui Cui, and Yu Yu. Revisiting the Constant-Sum Winternitz One-Time Signature with Applications to SPHINCS+ and XMSS. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part V, volume 14085 of LNCS, pages 455–483. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38554-4_15
[Zha12]
Mark Zhandry. How to Construct Quantum Random Functions. In 53rd FOCS, pages 679–687. October 2012. IEEE Computer Society Press. DOI: 10.1109/FOCS.2012.37
PDF
History
Submitted: 2025-01-14
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Justin Drake, Dmitry Khovratovich, Mikhail Kudinov, and Benedikt Wagner, Hash-Based Multi-Signatures for Post-Quantum Ethereum. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/aey7qjp10.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.