Paper 2021/302

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

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


Verifiable Random Functions (VRFs) play a key role in Proof-of-Stake blockchains such as Algorand to achieve highly scalable consensus, but currently deployed VRFs lack post-quantum security, which is crucial for future-readiness of blockchain systems. This work presents the first quantum-safe VRF scheme based on symmetric primitives. Our main proposal is a practical many-time quantum-safe VRF construction, X-VRF, based on the XMSS signature scheme. An innovation of our work is to use the state of the blockchain to counter the undesired stateful nature of XMSS by constructing a blockchain-empowered VRF. While increasing the usability of XMSS, our technique also enforces honest behavior 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 four instances of X-VRF with different key life-time. Our extensive performance evaluation, analysis and implementation indicate the effectiveness of our proposed constructions in practice. Particularly, we demonstrate that X-VRF is the most efficient quantum-safe VRF with a maximum proof size of 3 KB and a possible TPS of 449 for a network of thousand nodes.

Available format(s)
Publication info
Published elsewhere. MINOR revision.ESORICS 2022
verifiable random functionsymmetric cryptographyblockchain
Contact author(s)
maxime buser @ monash edu
rafael dowsley @ monash edu
muhammed esgin @ monash edu
shabnam kasra kermanshahi @ rmit edu au
v kuchta @ uq edu au
joseph liu @ monash edu
raphael phan @ monash edu
zhenfei @ manta network
2022-05-11: last of 2 revisions
2021-03-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {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},
      title = {Post-Quantum Verifiable Random Function from Symmetric Primitives in PoS Blockchain},
      howpublished = {Cryptology ePrint Archive, Paper 2021/302},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.