Byzantine Fault-Tolerant Aggregate Signatures
Pages 1831 - 1843
Abstract
Efficient (non-interactive) aggregate signature schemes in the post-quantum setting are still missing. We define the concept of Byzantine fault-tolerant aggregate signature schemes. This notion fills a middle-ground between interactive and non-interactive signature aggregation. Signers are required to interact but some may fail or misbehave at any point in the signing protocol.
Then, we provide efficient constructions of such schemes based on lattice assumptions. We show their security in the programmable random oracle model. For N participants they tolerate up to N - 1 Byzantine failures assuming a correct aggregator, and [EQUATION] failures in general. Our final construction is more efficient than Squirrel, the state-of-the-art non-interactive scheme, which in contrast to ours is also just a few-time signature scheme. Asymptotically signature sizes are polylogarithmic in the total number of participants. In the failure-free case our scheme becomes essentially equivalent to --- and thus just as efficient as --- a state-of-the-art interactive aggregate signature schemes from lattice assumptions. At the same time we make weaker assumptions on the signing protocol.
Finally, we parameterize, implement, and evaluate our signature scheme. We find that it has aggregate signatures of sizes (i) between 41 KiB (best case) and 151 KiB (worst case) for 1000 signers, (ii) between 59 KiB (best case) and 399 KiB (worst case) for 10,000 signers, and (iii) between 75 KiB (best case) and 750 KiB (worst case) for 100,000 signers. Verification times for our Rust implementation are in practice faster than those of a state-of-the-art implementation of aggregate BLS signatures, at the cost of slower signature aggregation, both by about one order of magnitude.
References
[1]
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: 17th Conference on Computer and Communications Security, pages 473--484, Chicago, Illinois, USA, October 4--8, 2010. ACM Press.
[2]
Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In 28th Annual ACM Symposium on Theory of Computing, pages 99--108, Philadephia, PA, USA, May 22--24, 1996. ACM Press.
[3]
Navid Alamati, Hart Montgomery, and Sikhar Patranabis. Symmetric primitives with structured secrets. Cryptology ePrint Archive, Report 2019/608, 2019. https://eprint.iacr.org/2019/608.
[4]
Navid Alamati, Hart Montgomery, Sikhar Patranabis, and Arnab Roy. Minicrypt primitives with algebraic structure and applications. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019, Part II, volume 11477 of Lecture Notes in Computer Science, pages 55--82, Darmstadt, Germany, May 19--23, 2019. Springer, Heidelberg, Germany.
[5]
Nabil Alkeilani Alkadri, Poulami Das, Andreas Erwig, Sebastian Faust, Juliane Krämer, Siavash Riahi, and Patrick Struck. Deterministic wallets in a quantum world. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020: 27th Conference on Computer and Communications Security, pages 1017--1031, Virtual Event, USA, November 9--13, 2020. ACM Press.
[6]
Foteini Baldimtsi, Konstantinos Kryptos Chalkias, Francois Garillot, Jonas Lindstrom, Ben Riva, Arnab Roy, Alberto Sonnino, Pun Waiwitlikhit, and Joy Wang. Subset-optimized BLS multi-signature with key aggregation. In Financial Cryptography and Data Security (FC), Willemstad, Curaçao, March 2024.
[7]
Dan Boneh and Sam Kim. One-time and interactive aggregate signatures from lattices. preprint, 4, 2020.
[8]
Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. In Colin Boyd, editor, Advances in Cryptology - ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, pages 514--532, Gold Coast, Australia, December 9--13, 2001. Springer, Heidelberg, Germany.
[9]
Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Eli Biham, editor, Advances in Cryptology - EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 416--432, Warsaw, Poland, May 4--8, 2003. Springer, Heidelberg, Germany.
[10]
Dan Boneh, Manu Drijvers, and Gregory Neven. Compact multi-signatures for smaller blockchains. In Thomas Peyrin and Steven Galbraith, editors, Advances in Cryptology - ASIACRYPT 2018, Part II, volume 11273 of Lecture Notes in Computer Science, pages 435--464, Brisbane, Queensland, Australia, December 2--6, 2018. Springer, Heidelberg, Germany.
[11]
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, Advances in Cryptology - CRYPTO 2022, Part II, volume 13508 of Lecture Notes in Computer Science, pages 276--305, Santa Barbara, CA, USA, August 15--18, 2022. Springer, Heidelberg, Germany.
[12]
Katharina Boudgoust and Adeline Roux-Langlois. Compressed linear aggregate signatures based on module lattices. Cryptology ePrint Archive, Report 2021/263, 2021. https://eprint.iacr.org/2021/263.
[13]
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, Tapei, Taiwan, November 29 -- December 2 2011. Springer, Heidelberg, Germany.
[14]
Ivan Damgård, Claudio Orlandi, Akira Takahashi, and Mehdi Tibouchi. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices. Journal of Cryptology, 35(2):14, 2022.
[15]
Poulami Das, Sebastian Faust, and Julian Loss. A formal treatment of deterministic wallets. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019: 26th Conference on Computer and Communications Security, pages 651--668, London, UK, November 11--15, 2019. ACM Press.
[16]
Rachid El Bansarkhani and Jan Sturm. An efficient lattice-based multisignature scheme with applications to bitcoins. In Sara Foresti and Giuseppe Persiano, editors, CANS 16: 15th International Conference on Cryptology and Network Security, volume 10052 of Lecture Notes in Computer Science, pages 140--155, Milan, Italy, November 14--16, 2016. Springer, Heidelberg, Germany.
[17]
Rachid El Bansarkhani and Jan Sturm. An efficient lattice-based multisignature scheme with applications to bitcoins. In Cryptology and Network Security: 15th International Conference, CANS 2016, Milan, Italy, November 14-16, 2016, Proceedings 15, pages 140--155. Springer, 2016.
[18]
Nils Fleischhacker, Johannes Krupp, Giulio Malavolta, Jonas Schneider, Dominique Schröder, and Mark Simkin. Efficient unlinkable sanitizable signatures from signatures with re-randomizable keys. In Public-Key Cryptography-PKC 2016: 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6--9, 2016, Proceedings, Part I, pages 301--330. Springer, 2016.
[19]
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: 29th Conference on Computer and Communications Security, pages 1109--1123, Los Angeles, CA, USA, November 7--11, 2022. ACM Press.
[20]
Masayuki Fukumitsu and Shingo Hasegawa. A tightly-secure lattice-based multisignature. In Proceedings of the 6th on ASIA Public-Key Cryptography Workshop, pages 3--11, 2019.
[21]
Masayuki Fukumitsu and Shingo Hasegawa. A lattice-based provably secure multisignature scheme in quantum random oracle model. In International Conference on Provable Security, pages 45--64. Springer, 2020.
[22]
Juan Carlos Garcia-Escartin, Vicent Gimeno, and Julio José Moyano-Fernández. Quantum collision finding for homomorphic hash functions. Cryptology ePrint Archive, Report 2021/1016, 2021. https://eprint.iacr.org/2021/1016.
[23]
Meenakshi Kansal and Ratna Dutta. Round optimal secure multisignature schemes from lattice with public key aggregation and signature compression. In International Conference on Cryptology in Africa, pages 281--300. Springer, 2020.
[24]
Irakliy Khaburzaniya, Konstantinos Chalkias, Kevin Lewi, and Harjasleen Malvai. Aggregating hash-based signatures using STARKs. Cryptology ePrint Archive, Report 2021/1048, 2021. https://eprint.iacr.org/2021/1048.
[25]
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: 17th ACM Symposium on Information, Computer and Communications Security, pages 393--407, Nagasaki, Japan, May 30 -- June 3, 2022. ACM Press.
[26]
Benoît Libert, San Ling, Khoa Nguyen, and Huaxiong Wang. Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 1--31, Vienna, Austria, May 8--12, 2016. Springer, Heidelberg, Germany.
[27]
Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In Mitsuru Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 598--616, Tokyo, Japan, December 6--10, 2009. Springer, Heidelberg, Germany.
[28]
Vadim Lyubashevsky. Lattice signatures without trapdoors. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 738--755, Cambridge, UK, April 15--19, 2012. Springer, Heidelberg, Germany.
[29]
Vadim Lyubashevsky and Daniele Micciancio. Asymptotically efficient lattice-based digital signatures. In Ran Canetti, editor, TCC 2008: 5th Theory of Cryptography Conference, volume 4948 of Lecture Notes in Computer Science, pages 37--54, San Francisco, CA, USA, March 19--21, 2008. Springer, Heidelberg, Germany.
[30]
Changshe Ma and Mei Jiang. Practical lattice-based multisignature schemes for blockchains. IEEE Access, 7:179765--179778, 2019.
[31]
Ralph C. Merkle. A digital signature based on a conventional encryption function. In Carl Pomerance, editor, Advances in Cryptology - CRYPTO'87, volume 293 of Lecture Notes in Computer Science, pages 369--378, Santa Barbara, CA, USA, August 16--20, 1988. Springer, Heidelberg, Germany.
[32]
Charalampos Papamanthou, Elaine Shi, Roberto Tamassia, and Ke Yi. Streaming authenticated data structures. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 353--370, Athens, Greece, May 26--30, 2013. Springer, Heidelberg, Germany.
[33]
Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science, pages 124--134, Santa Fe, NM, USA, November 20--22, 1994. IEEE Computer Society Press.
Index Terms
- Byzantine Fault-Tolerant Aggregate Signatures
Recommendations
Fault-Tolerant Aggregate Signatures
Proceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 9614Aggregate signature schemes allow for the creation of a short aggregate of multiple signatures. This feature leads to significant reductions of bandwidth and storage space in sensor networks, secure routing protocols, certificate chains, software ...
ID-Based aggregate signatures from bilinear pairings
CANS'05: Proceedings of the 4th international conference on Cryptology and Network SecurityAggregate signature scheme was recently proposed by Boneh, Gentry, Lynn and Shacham, which presented a method for combining n signatures from n different signers on n different messages into one signature. In this paper, we propose an identity-based ...
Sequential aggregate signatures with lazy verification from trapdoor permutations
Sequential aggregate signature schemes allow n signers, in order, to sign a message each, at a lower total cost than the cost of n individual signatures. We present a sequential aggregate signature scheme based on trapdoor permutations (e.g., RSA). ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
1987 pages
ISBN:9798400704826
DOI:10.1145/3634737
- Chair:
- Jianying Zhou,
- Co-chair:
- Tony Q. S. Quek,
- Program Chairs:
- Debin Gao,
- Alvaro Cardenas
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ASIA CCS '24
Sponsor:
ASIA CCS '24: 19th ACM Asia Conference on Computer and Communications Security
July 1 - 5, 2024
Singapore, Singapore
Acceptance Rates
Overall Acceptance Rate 418 of 2,322 submissions, 18%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 138Total Downloads
- Downloads (Last 12 months)138
- Downloads (Last 6 weeks)23
Reflects downloads up to 08 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in