2021/09/05 by Zengpeng Li, Li, Zengpeng, Teik Guan Tan +7 · 1 citation
Computer Science · #(Primary) 94A60 #68M25(Secondary) #68Q85 #Blockchain Technology Applications and Security #Cloud Data Security Solutions #Computers and Society (cs.CY) #Cryptography and Data Security #Cryptography and Security (cs.CR) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2109.02012
openalex publication_date 2021/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A verifiable random function (VRF in short) is a powerful pseudo-random function that provides a non-interactively public verifiable proof for the correctness of its output. Recently, VRFs have found essential applications in blockchain design, such as random beacons and proof-of-stake consensus protocols. To our knowledge, the first generation of blockchain systems used inherently inefficient proof-of-work consensuses, and the research community tried to achieve the same properties by proposing proof-of-stake schemes where resource-intensive proof-of-work is emulated by cryptographic constructions. Unfortunately, those most discussed proof-of-stake consensuses (e.g., Algorand and Ouroborous family) are not future-proof because the building blocks are secure only under the classical hard assumptions; in particular, their designs ignore the advent of quantum computing and its implications. In this paper, we propose a generic compiler to obtain the post-quantum VRF from the simple VRF solution using symmetric-key primitives (e.g., non-interactive zero-knowledge system) with an intrinsic property of quantum-secure. Our novel solution is realized via two efficient zero-knowledge systems ZKBoo and ZKB++, respectively, to validate the compiler correctness. Our proof-of-concept implementation indicates that even today, the overheads introduced by our solution are acceptable in real-world deployments. We also demonstrate potential applications of a quantum-secure VRF, such as quantum-secure decentralized random beacon and lottery-based proof of stake consensus blockchain protocol.