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
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
Metadata
- Available format(s)
-
PDF
- 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
- 2020-10-06: received
- See all versions
- Short URL
- https://ia.cr/2020/1222
- License
-
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},
url = {https://eprint.iacr.org/2020/1222}
}