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.
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.
A trustworthy source of randomness is a crucial component of many decentralized and crypto-based application systems, especially blockchain consensus. A decentralized random beacon (DRB) periodically outputs a new source of randomness generated using a distributed technique, such as publicly verifiable secret sharing (PVSS) or distributed verifiable random functions (VRFs). These protocols offer a variety of efficiency versus randomness quality tradeoffs, but guarantee security under a variety of configurations, assumptions, and adversarial models. This article aims to provide a future-proof unbiased decentralized randomness (abbreviated as Funder) via a post-quantum threshold VRF for sustainable proof-of-stake blockchain. We also provide a generic compiler for achieving post-quantum VRF from a classical VRF solution, but our approach makes use of symmetric-key primitives Our novel compiler is validated and evaluated using the ZKBoo and ZKB++ quantum-secure zero-knowledge systems, respectively. The implementation of the proof-of-concept demonstrates that the overheads introduced by our solution are acceptable for real-world deployments even in the present day. In addition, we demonstrate the protocol’s possible application in lottery-based proof-of-stake consensus protocols.
We introduce NTRU-VRF, the first verifiable random function (VRF) constructed directly from the NTRU lattice hardness assumption, and instantiated concretely using the NIST-standardized Falcon-512 (FN-DSA) signature scheme. A VRF is a pseudorandom function that produces a publicly verifiable proof of correctness for each output. All currently deployed VRFs (IETF RFC 9381, Algorand, Ethereum) rely on elliptic-curve assumptions broken by Shor's algorithm. Prior post-quantum VRF constructions either require only a few-time security guarantee (Esgin et al., ePrint 2020/1222), rely on symmetric primitives that lack a worst-case lattice hardness reduction (Buser et al., ePrint 2021/302), or are based on Module-LWE/Module-SIS rather than NTRU. No prior work constructs a many-time, lattice-based VRF from NTRU hardness with a formal security proof. Our construction exploits a fundamental and previously unformalized property of Falcon's deterministic signing mode: for any fixed public key and input, there exists exactly one valid short-norm signature. This unique-signature property is the key structural feature that transforms a lattice signature into a VRF. We prove three theorems: Uniqueness: For any input, the NTRU-VRF output is unique. This follows directly from the unique-short-coset-vector property of the NTRU lattice. Pseudorandomness: If the Short Integer Solution (SIS) problem on NTRU lattices is hard and the hash function is modelled as a random oracle, then the VRF output is computationally indistinguishable from a uniformly random value. Provability: The Falcon signature is an efficient, publicly verifiable proof, checkable by any party holding the public key. As a concrete application, we define PQ-Sortition, a post-quantum proof-of-stake leader-election protocol that replaces ECVRF-based sortition with our NTRU-VRF construction. We provide the entropy-chain design, stake-weighted win condition, adaptive liveness mechanism, equivocation slashing, and a formal security analysis of the resulting consensus protocol. Instantiated with Falcon-512, NTRU-VRF achieves a VRF output of 32 bytes, a proof size of <= 666 bytes, evaluation time of ~0.8 ms, and verification time of ~0.1 ms on standard hardware—significantly outperforming all existing post-quantum VRF constructions and making it the first many-time, compact, lattice-based VRF suitable for high-throughput blockchain consensus.
Blockchain systems based on the proof-of-work (PoW) consensus introduce entropy to the system in a natural way due to the randomness of mining. However, for non-PoW consensus (e.g., proof-of-stake and delegated proof-of-stake consensus) blockchain systems, a different approach to introducing entropy, such as the distributed random number generation (dRNG) algorithm, must be established. The dRNG algorithm is one of the key challenges in developing the consensus mechanism, as well as one of the relevant parameters for determining the merit of the consensus mechanism. In this paper, we first derive a publicly verifiable quantum random numbers generation protocol based on the certifiable randomness scheme from any untrusted quantum device, which offers features, such as fairness, no trusted third party, and publicly verifiable. Then, based on verifiable quantum random numbers, we propose a new consensus algorithm. The algorithm selects block proposer and block verification committees for each round using verifiable quantum random numbers, resulting in better randomness, fairness, and efficiency of the entire consensus process. In addition, the new consensus algorithm is not only resistant to adaptive adversary models as well as to collusion attacks, but also requires negligible computation for each user to avoid unnecessary consumption of power resources. Finally, we analyze the verifiable randomness, fairness, liveness, and communication complexity of the consensus algorithm.
Verifiable Random Functions (VRFs) and Oblivious Pseudorandom Functions (OPRFs) are essential cryptographic primitives in privacy-preserving applications such as anonymous authentication, private set intersection (PSI), and decentralized identity. Existing constructions, however, rely on number-theoretic assumptions that are vulnerable to quantum attacks. This PhD research project focuses on constructing efficient and practical VRFs and OPRFs from lattice-based assumptions to ensure post-quantum security. A key obstacle in these constructions is the overhead of zero-knowledge proofs (ZKPs), particularly range proofs, which are costly in terms of size and prover complexity. To address this, we investigate probabilistic techniques that relax exact correctness. In particular, we explore approximate range proofs and algebraic transformations, such as using automorphisms in polynomial rings to simulate inner product arguments via polynomial multiplication. These methods enable more efficient and scalable lattice-based constructions of VRFs, including group and context-bound variants, as well as OPRFs. The goal is to make these primitives practical for deployment in post-quantum privacy-preserving systems.
Lattice-based cryptography is evolving rapidly and is often employed to design cryptographic primitives that hold a great promise to be post-quantum resistant and can be employed in multiple application settings such as: e-cash, unique digital signatures, non-interactive lottery and others.In such application scenarios, a user is often required to prove non-interactively the correct computation of a pseudo-random function F_k(x) without revealing the secret key k used.Commitment schemes are also useful in application settings requiring to commit to a chosen but secret value that could be revealed later.In this short paper, we provide our insights on constructing a lattice-based simulatable verifiable random function (sVRF) using non interactive zero knowledge arguments and dual-mode commitment schemes and we point out the main challenges that need to be addressed in order to achieve it.
Quantum Random Number Generators (QRNGs) produce high-quality randomness derived from quantum phenomena, offering strong security assurances. However, relying on a single QRNG device centralizes trust and creates a single point of failure. This paper presents a decentralized architecture integrating multiple geographically distributed QRNG nodes using the Kirk network's quantum and classical channels. We incorporate Post-Quantum Verifiable Random Functions (PQ-VRFs), threshold secret sharing, and Byzantine Fault Tolerant (BFT) consensus protocols to ensure unbiased, verifiable, and tamper-resistant randomness. We detail a blockchain oracle system that transforms quantum-secure keys into various blockchain-compatible formats (Ethereum, Bitcoin, Polkadot), creating a future-proof, monetizable service for quantum-era blockchain infrastructures.