### 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

##### 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.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)
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Financial Cryptography and Data Security 2021
Keywords
Post-QuantumVerifiable Random FunctionBlockchainLatticeAlgorand
Contact author(s)
muhammed esgin @ monash edu
History
2021-03-25: last of 3 revisions
See all versions
Short URL
https://ia.cr/2020/1222

CC BY

BibTeX

@misc{cryptoeprint:2020/1222,
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{https://eprint.iacr.org/2020/1222}},
url = {https://eprint.iacr.org/2020/1222}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.