Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

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

Muhammed F. Esgin, Veronika Kuchta, Amin Sakzad, Ron Steinfeld, Zhenfei Zhang, Shi-Feng Sun, Shumo Chu

Published Jan 1, 2021• 40 citations
Publisher
DOI
10.1007/978-3-662-64331-0_29

Related papers

Proofs of Isogeny Knowledge and Application to Post-quantum One-Time Verifiable Random Function.

Antonin Leroux

•Jan 1, 2021•2 citations

Post-quantum verifiable random functions from ring signatures.

Endre Abraham

•Jan 1, 2018•4 citations

Post-Quantum Verifiable Random Function from Symmetric Primitives in PoS Blockchain

Maxime Buser, Rafael Dowsley, Muhammed F. Esgin +5 more

Lecture notes in computer science•Jan 1, 2022•31 citations

NTRU-VRF: A Verifiable Random Function from NTRU Lattices with Applications to Post-Quantum Leader Election in Proof-of-Stake Blockchains

Kishore K

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.

•Jul 10, 2026•0 citations

Post-Quantum VRF and its Applications in Future-Proof Blockchain System

Zengpeng Li, Teik Guan Tan, Paweł Szałachowski +2 more

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.

arXiv:2109.02012•Sep 5, 2021•7 citations

Papercraft: Lattice-Based Verifiable Delay Function Implemented

Michal Osadnik, Darya Kaviani, Valerio Cini +2 more

A verifiable delay function (VDF) requires a specified number of sequential steps to compute, yet the validity of its output can be verified efficiently, much faster than recomputing the function from scratch. VDFs are a versatile cryptographic tool, with many industrial applications, such as blockchain consensus protocols, lotteries and verifiable randomness. Unfortunately, without exceptions, all known practical VDF constructions are broken by quantum algorithms. In this work, we investigate the practicality of VDFs with plausible post-quantum security. We propose Papercraft, a working implementation of a VDF based entirely on lattice techniques and thus plausibly post-quantum secure. Our VDF is based on new observations on lattice-based succinct argument systems with many low-level optimisations, yielding the first lattice-based VDF that is implementable on today's hardware. As an example, our Papercraft implementation can verify a computation of over 6 minutes in just 7 seconds. Overall, our work demonstrates that lattice-based VDFs are not just a theoretical construct, paving the way for their practical deployment.

IEEE Symposium on Security and Privacy (S&P)•May 12, 2025•3 citations
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.
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 delay function (VDF) requires a specified number of sequential steps to compute, yet the validity of its output can be verified efficiently, much faster than recomputing the function from scratch. VDFs are a versatile cryptographic tool, with many industrial applications, such as blockchain consensus protocols, lotteries and verifiable randomness. Unfortunately, without exceptions, all known practical VDF constructions are broken by quantum algorithms. In this work, we investigate the practicality of VDFs with plausible post-quantum security. We propose Papercraft, a working implementation of a VDF based entirely on lattice techniques and thus plausibly post-quantum secure. Our VDF is based on new observations on lattice-based succinct argument systems with many low-level optimisations, yielding the first lattice-based VDF that is implementable on today's hardware. As an example, our Papercraft implementation can verify a computation of over 6 minutes in just 7 seconds. Overall, our work demonstrates that lattice-based VDFs are not just a theoretical construct, paving the way for their practical deployment.