Cryptology ePrint Archive: Report 2020/1222

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

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

Abstract: 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.16x to 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 66 transactions per second. This is still much better than Bitcoin, which processes only about 5 transactions per second.

Category / Keywords: public-key cryptography / Post-Quantum, Verifiable Random Function, Blockchain, Lattice, Algorand

Date: received 4 Oct 2020

Contact author: muhammed esgin at monash edu

Available format(s): PDF | BibTeX Citation

Version: 20201006:095132 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]