Document Open Access Logo

Post-Quantum Single Secret Leader Election (SSLE) from Publicly Re-Randomizable Commitments

Authors Dan Boneh, Aditi Partap, Lior Rotem

PDF
Thumbnail PDF

File

LIPIcs.AFT.2023.26.pdf
  • Filesize: 0.87 MB
  • 23 pages

Document Identifiers

Author Details

Dan Boneh
  • Stanford University, CA, USA
Aditi Partap
  • Stanford University, CA, USA
Lior Rotem
  • Stanford University, CA, USA

Funding

This work was funded by NSF, DARPA, the Simons Foundation, UBRI, and NTT Research. Opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of DARPA.

Cite As Get BibTex

Dan Boneh, Aditi Partap, and Lior Rotem. Post-Quantum Single Secret Leader Election (SSLE) from Publicly Re-Randomizable Commitments. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 26:1-26:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.AFT.2023.26

Abstract

A Single Secret Leader Election (SSLE) enables a group of parties to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to publicly reveal her identity and prove that she is the elected leader. The election process itself should work properly even if many registered users are passive and do not send any messages. SSLE is used to strengthen the security of proof-of-stake consensus protocols by ensuring that the identity of the block proposer remains unknown until the proposer publishes a block. Boneh, Eskandarian, Hanzlik, and Greco (AFT'20) defined the concept of an SSLE and gave several constructions. Their most efficient construction is based on the difficulty of the Decision Diffie-Hellman problem in a cyclic group. 
In this work we construct the first efficient SSLE protocols based on the standard Learning With Errors (LWE) problem on integer lattices, as well as the Ring-LWE problem. Both are believed to be post-quantum secure. Our constructions generalize the paradigm of Boneh et al. by introducing the concept of a re-randomizable commitment (RRC). We then construct several post-quantum RRC schemes from lattice assumptions and prove the security of the derived SSLE protocols. Constructing a lattice-based RRC scheme is non-trivial, and may be of independent interest.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
Keywords
  • Consensus
  • Leader Election
  • Post-Quantum
  • Lattice Cryptography
  • Blockchain

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient lattice (h)ibe in the standard model. In Advances in Cryptology - EUROCRYPT 2010, pages 553-572, 2010. Google Scholar
  2. Martin R. Albrecht, Valerio Cini, Russell W. F. Lai, Giulio Malavolta, and Sri AravindaKrishnan Thyagarajan. Lattice-based snarks: Publicly verifiable, preprocessing, and recursively composable. In Advances in Cryptology - CRYPTO 2022, pages 102-132, 2022. Google Scholar
  3. Joël Alwen and Chris Peikert. Generating shorter bases for hard random lattices. Theory of Computing Systems, 48:535-553, 2011. Google Scholar
  4. Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight sublinear arguments without a trusted setup. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 2087-2104, Dallas, TX, USA, October 31 - November 2 2017. ACM Press. URL: https://doi.org/10.1145/3133956.3134104.
  5. Prabhanjan Ananth, Apoorvaa Deshpande, Yael Tauman Kalai, and Anna Lysyanskaya. Fully homomorphic NIZK and NIWI proofs. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part II, volume 11892 of LNCS, pages 356-385, Nuremberg, Germany, December 1-5 2019. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-36033-7_14.
  6. Thomas Attema, Ronald Cramer, and Lisa Kohl. A compressed Σ-protocol theory for lattices. In Advances in Cryptology - CRYPTO 2021, pages 549-579, 2021. Google Scholar
  7. Sarah Azouvi and Daniele Cappelletti. Private attacks in longest chain proof-of-stake protocols with single secret leader elections. In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, AFT '21, pages 170-182, 2021. URL: https://doi.org/10.1145/3479722.3480996.
  8. Sarah Azouvi, Patrick McCorry, and Sarah Meiklejohn. Betting on blockchain consensus with fantomette, 2018. URL: https://arxiv.org/abs/1805.06786.
  9. Michael Backes, Pascal Berrang, Lucjan Hanzlik, and Ivan Pryvalov. A framework for constructing single secret leader election from MPC. In Vijayalakshmi Atluri, Roberto Di Pietro, Christian Damsgaard Jensen, and Weizhi Meng, editors, ESORICS 2022, Part II, volume 13555 of LNCS, pages 672-691, Copenhagen, Denmark, September 26-30 2022. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-031-17146-8_33.
  10. Carsten Baum, Jonathan Bootle, Andrea Cerulli, Rafael del Pino, Jens Groth, and Vadim Lyubashevsky. Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits. In Advances in Cryptology - CRYPTO 2018, pages 669-699, 2018. Google Scholar
  11. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, , and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Paper 2018/046, 2018. URL: https://eprint.iacr.org/2018/046.
  12. Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent succinct arguments for R1CS. In Advances in Cryptology - EUROCRYPT 2019, pages 103-128, 2019. Google Scholar
  13. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Theory of Cryptography, pages 31-60, 2016. Google Scholar
  14. Fabrice Benhamouda, Stephan Krenn, Vadim Lyubashevsky, and Krzysztof Pietrzak. Efficient zero-knowledge proofs for commitments from learning with errors over rings. Cryptology ePrint Archive, Report 2014/889, 2014. URL: https://eprint.iacr.org/2014/889.
  15. Rishabh Bhadauria, Zhiyong Fang, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Tiancheng Xie, and Yupeng Zhang. Ligero++: A new optimized sublinear IOP. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020, pages 2025-2038, Virtual Event, USA, November 9-13 2020. ACM Press. URL: https://doi.org/10.1145/3372297.3417893.
  16. Dan Boneh, Saba Eskandarian, Lucjan Hanzlik, and Nicola Greco. Single secret leader election. In AFT '20, pages 12-24. ACM, 2020. Available online at URL: https://eprint.iacr.org/2020/025.
  17. Dan Boneh and Victor Shoup. A Graduate Course in Applied Cryptography, Draft 0.6. Cambridge University Press, 2023. Google Scholar
  18. Dario Catalano, Dario Fiore, and Emanuele Giunta. Efficient and universally composable single secret leader election from pairings. Cryptology ePrint Archive, Report 2021/344, 2021. URL: https://eprint.iacr.org/2021/344.
  19. Dario Catalano, Dario Fiore, and Emanuele Giunta. Adaptively secure single secret leader election from ddh. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC'22, pages 430-439, 2022. URL: https://doi.org/10.1145/3519270.3538424.
  20. Rutchathon Chairattana-Apirom and Anna Lysyanskaya. Compact cut-and-choose: Boosting the security of blind signature schemes, compactly. Cryptology ePrint Archive, Paper 2022/003, 2022. URL: https://eprint.iacr.org/2022/003.
  21. Miranda Christ, Valeria Nikolaenko, and Joseph Bonneau. Leader election from randomness beacons and other strategies, 2022. URL: https://a16zcrypto.com/posts/article/leader-election-from-randomness-beacons-and-other-strategies.
  22. Nuria Costa, Ramiro Martínez, and Paz Morillo. Lattice-based proof of a shuffle. In FC 2019: Financial Cryptography and Data Security, pages 330-346, 2019. Google Scholar
  23. Justin Drake. Low-overhead secret single-leader election, 2019. URL: https://ethresear.ch/t/low-overhead-secret-single-leader-election/5994.
  24. Luciano Freitas, Andrei Tonkikh, Adda-Akram Bendoukha, Sara Tucci-Piergiovanni, Renaud Sirdey, Oana Stan, and Petr Kuznetsov. Homomorphic sortition – single secret leader election for pos blockchains. Cryptology ePrint Archive, Paper 2023/113, 2023. URL: https://eprint.iacr.org/2023/113.
  25. Chaya Ganesh, Claudio Orlandi, and Daniel Tschudi. Proof-of-stake protocols for privacy-aware blockchains. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part I, volume 11476 of LNCS, pages 690-719, Darmstadt, Germany, May 19-23 2019. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-030-17653-2_23.
  26. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, pages 197-206, 2008. URL: https://doi.org/10.1145/1374376.1374407.
  27. Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. Cryptology ePrint Archive, Report 2017/454, 2017. URL: https://eprint.iacr.org/2017/454.
  28. Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, , and Riad S. Wahby. Brakedown: Linear-time and post-quantum snarks for R1CS. Cryptology ePrint Archive, Paper 2021/1043, 2021. URL: https://eprint.iacr.org/2021/1043.
  29. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364-1396, 1999. Google Scholar
  30. George Kadianakis. Whisk: A practical shuffle-based ssle protocol for ethereum, 2022. URL: https://ethresear.ch/t/whisk-a-practical-shuffle-based-ssle-protocol-for-ethereum/11763.
  31. Thomas Kerber, Aggelos Kiayias, Markulf Kohlweiss, and Vassilis Zikas. Ouroboros crypsinous: Privacy-preserving proof-of-stake. In 2019 IEEE Symposium on Security and Privacy, pages 157-174, San Francisco, CA, USA, May 19-23 2019. IEEE Computer Society Press. URL: https://doi.org/10.1109/SP.2019.00063.
  32. Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Maxime Plançon. Lattice-based zero-knowledge proofs and applications: Shorter, simpler, and more general. In Advances in Cryptology - CRYPTO 2022, pages 71-101, 2022. Google Scholar
  33. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 1-23, French Riviera, May 30 - June 3 2010. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-642-13190-5_1.
  34. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. URL: http://bitcoin.org/bitcoin.pdf.
  35. Ngoc Khanh Nguyen and Gregor Seiler. Practical sublinear proofs for r1cs from lattices. In Advances in Cryptology - CRYPTO 2022, pages 133-162, 2022. Google Scholar
  36. Chris Peikert. A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science, 10(4):283-424, 2016. Available online at URL: https://eprint.iacr.org/2015/939.pdf.
  37. Mayank Raikwar and Danilo Gligoroski. Sok: Decentralized randomness beacon protocols. In Australasian Conference on Information Security and Privacy, pages 420-446. Springer, 2022. available URL: https://arxiv.org/abs/2205.13333.
  38. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84-93, Baltimore, MA, USA, May 22-24 2005. ACM Press. URL: https://doi.org/10.1145/1060590.1060603.
  39. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1-34:40, 2009. Available online URL: https://cims.nyu.edu/~regev/papers/qcrypto.pdf.
  40. Antonio Sanso. Towards practical post quantum single secret leader election (ssle) - part 1, 2022. URL: https://crypto.ethereum.org/blog/pq-ssle.
  41. Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In 35th FOCS, pages 124-134, Santa Fe, NM, USA, November 20-22 1994. IEEE Computer Society Press. URL: https://doi.org/10.1109/SFCS.1994.365700.
  42. Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key encryption based on ideal lattices. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 617-635, Tokyo, Japan, December 6-10 2009. Springer, Heidelberg, Germany. URL: https://doi.org/10.1007/978-3-642-10366-7_36.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact