Cryptology ePrint Archive: Report 2021/302

Post-Quantum Verifiable Random Function from Symmetric Primitives in PoS Blockchain

Maxime Buser and Rafael Dowsley and Muhammed F. Esgin and Shabnam Kasra Kermanshahi and Veronika Kuchta and Joseph K. Liu and Raphael Phan and Zhenfei Zhang

Abstract: In this work, we study verifiable random functions (VRF) that may resist quantum threats. VRFs have a wide range of applications and play a key role in Proof-of-Stake blockchains, such as Algorand. Our main proposal is a VRF construction X-VRF based on XMSS signature scheme. Our construction is the first quantum-safe VRF proposal based on symmetric primitives. Being based on symmetric-key primitives that have long been studied, X-VRF provides strong confidence that it can withstand quantum attacks in the long run. Despite its stateful nature, we empower XMSS with blockchain so that the users do not need to maintain individual states. While increasing the usability of XMSS, our technique also enforces honest behaviour when creating an X-VRF output so as to satisfy the fundamental uniqueness property of VRFs. We show how X-VRF can be used in the Algorand setting to extend it to a quantum-safe blockchain, and provide various instances of X-VRF, each may suit a different setting. Our X-VRF instances are the most efficient quantum-safe VRF proposals in the literature.Our extensive performance evaluation, analysis, and implementation indicates the effectiveness of our pro-posed constructions in practice. In particular, we show that X-VRF can maintain a very competitive throughput close to the existing Algorand protocol and can produce substantially more transactions per second than Bitcoin.

Category / Keywords: applications / verifiable random function, symmetric cryptography, blockchain

Date: received 7 Mar 2021, last revised 2 Aug 2021

Contact author: maxime buser at monash edu, rafael dowsley at monash edu, muhammed esgin at monash edu, shabnam kasra kermanshahi at rmit edu au, v kuchta at uq edu au, joseph liu at monash edu, raphael phan at monash edu, zhenfei at manta network

Available format(s): PDF | BibTeX Citation

Version: 20210803:013453 (All versions of this report)

Short URL: ia.cr/2021/302


[ Cryptology ePrint archive ]