Paper 2020/1222

Practical Post-Quantum Few-Time Verifiable Random Function with Applications to Algorand

Muhammed F. Esgin, Veronika Kuchta, Amin Sakzad, Ron Steinfeld, Zhenfei Zhang, Shifeng Sun, and Shumo Chu


In this work, we introduce the first practical post-quantum verifiable random function (VRF) that relies on well-known (module) lattice problems, namely Module-SIS and Module-LWE. Our construction, named LB-VRF, results in a VRF value of only 84 bytes and a proof of around only 5 KB (in comparison to several MBs in earlier works), and runs in about 3 ms for evaluation and about 1 ms for verification. In order to design a practical scheme, we need to restrict the number of VRF outputs per key pair, which makes our construction few-time. Despite this restriction, we show how our few-time LB-VRF can be used in practice and, in particular, we estimate the performance of Algorand using LB-VRF. We find that, due to the significant increase in the communication size in comparison to classical constructions, which is inherent in all existing lattice-based schemes, the throughput in LB-VRF-based consensus protocol is reduced, but remains practical. In particular, in a medium-sized network with 100 nodes, our platform records a 1.14x to 3.4x reduction in throughput, depending on the accompanying signature used. In the case of a large network with 500 nodes, we can still maintain at least 24 transactions per second. This is still much better than Bitcoin, which processes only about 5 transactions per second.

Note: typo in Table 1 is corrected

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Financial Cryptography and Data Security 2021
Post-QuantumVerifiable Random FunctionBlockchainLatticeAlgorand
Contact author(s)
muhammed esgin @ monash edu
2021-03-25: last of 3 revisions
2020-10-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Muhammed F.  Esgin and Veronika Kuchta and Amin Sakzad and Ron Steinfeld and Zhenfei Zhang and Shifeng Sun and Shumo Chu},
      title = {Practical Post-Quantum Few-Time Verifiable Random Function with Applications to Algorand},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1222},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.