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

IEEE Symposium on Security and Privacy (S&P)

Papercraft: Lattice-Based Verifiable Delay Function Implemented

Michal Osadnik, Darya Kaviani, Valerio Cini, Russell W. F. Lai, Giulio Malavolta

Published May 12, 2025• 3 citations
Publisher

Abstract

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.

DOI
10.1109/sp61157.2025.00159

Related papers

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

Turning Uncertainty into Efficiency: Toward Practical, Quantum-Resistant Verifiable Privacy Tools

Jie Xu

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.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 19, 2025•0 citations

Towards Practical Post-Quantum Voting Protocol: Shorter Exact Lattice-Based Proof of a Shuffle

Farzaliyev, Valeh

Electronic voting solutions are built on complex cryptographic tools to guarantee security and fairness. Currently, those tools are based on hardness assumptions of discrete logarithm, factorization and other classical problems. While they are hard to break in classical computers, there are efficient quantum algorithms to solve using quantum computers of the near future. Thus, there is a need to develop voting protocols that are resistant to quantum attacks. Verifiable shuffling based voting systems are a popular use-case of mix-networks first proposed by Chaum four decades ago [Cha81] as a general tool for building anonymous communication systems. A decade later the quantum threat was known and since then only a few studies searched for post-quantum secure mix-nets. Recently, Costa, Martinez and Morillo introduced new arguments of shuffle for RLWE ciphertexts and how to prove the correctness of the shuffling without leaking sensitive info [CMM17]. In this thesis, we provide exact, shorter proof of Costa et al.’s lattice-based shuffling arguments. As a result, we obtain a practical non-interactive zero-knowledge proof having a runtime of 1 second per voter.

•Jan 1, 2020•0 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

Research on Lattice-Based Cryptographic Algorithms

WU Kun, TANG Jinyi, LI Peiqi, WANG Xiaorui, WANG Xiaoyu

The security of classical public-key cryptosystems, which operate based on the computational intractability of integer factorization and discrete logarithm problems, is profoundly threatened by the rapid development of quantum computing. Post-Quantum Cryptography (PQC) has been proposed to improve security against quantum attacks. Lattice-based cryptography is widely regarded as one of the most promising PQC method because of its proven security, efficient implementation, and functional versatility, and it has achieved significant progress in both algorithmic design and engineering implementation in recent years. This paper presents a systematic survey of the status of research on lattice-based cryptographic algorithms. First, the fundamental theory of lattices and their core hard problems are discussed. Next, the technical characteristics and performance of encryption and key encapsulation mechanisms, digital signature schemes, and key exchange protocols constructed based on lattice hard problems are reviewed and compared. Subsequently, the principles and optimization paths of two key technologies for lattice cryptography implementation, namely polynomial multiplication using the fast Number Theoretic Transform (NTT) and pre-image sampling algorithms, are discussed. Finally, considering the PQC standardization process of the National Institute of Standards and Technology (NIST), an outlook on future research directions for lattice-based cryptography is presented. The research directions include the development of more "succinct" fundamental hard problems, strengthening security proofs, improving algorithm efficiency, and countering novel attacks. This review serves as a reference for promoting the practical deployment and further research of lattice-based cryptography.

•Sep 1, 2026•0 citations

Post-Quantum Zero-Knowledge Proofs and Applications

Ron Steinfeld

Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 20, 2023•5 citations
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.
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.
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.
Electronic voting solutions are built on complex cryptographic tools to guarantee security and fairness. Currently, those tools are based on hardness assumptions of discrete logarithm, factorization and other classical problems. While they are hard to break in classical computers, there are efficient quantum algorithms to solve using quantum computers of the near future. Thus, there is a need to develop voting protocols that are resistant to quantum attacks. Verifiable shuffling based voting systems are a popular use-case of mix-networks first proposed by Chaum four decades ago [Cha81] as a general tool for building anonymous communication systems. A decade later the quantum threat was known and since then only a few studies searched for post-quantum secure mix-nets. Recently, Costa, Martinez and Morillo introduced new arguments of shuffle for RLWE ciphertexts and how to prove the correctness of the shuffling without leaking sensitive info [CMM17]. In this thesis, we provide exact, shorter proof of Costa et al.’s lattice-based shuffling arguments. As a result, we obtain a practical non-interactive zero-knowledge proof having a runtime of 1 second per voter.
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.
The security of classical public-key cryptosystems, which operate based on the computational intractability of integer factorization and discrete logarithm problems, is profoundly threatened by the rapid development of quantum computing. Post-Quantum Cryptography (PQC) has been proposed to improve security against quantum attacks. Lattice-based cryptography is widely regarded as one of the most promising PQC method because of its proven security, efficient implementation, and functional versatility, and it has achieved significant progress in both algorithmic design and engineering implementation in recent years. This paper presents a systematic survey of the status of research on lattice-based cryptographic algorithms. First, the fundamental theory of lattices and their core hard problems are discussed. Next, the technical characteristics and performance of encryption and key encapsulation mechanisms, digital signature schemes, and key exchange protocols constructed based on lattice hard problems are reviewed and compared. Subsequently, the principles and optimization paths of two key technologies for lattice cryptography implementation, namely polynomial multiplication using the fast Number Theoretic Transform (NTT) and pre-image sampling algorithms, are discussed. Finally, considering the PQC standardization process of the National Institute of Standards and Technology (NIST), an outlook on future research directions for lattice-based cryptography is presented. The research directions include the development of more "succinct" fundamental hard problems, strengthening security proofs, improving algorithm efficiency, and countering novel attacks. This review serves as a reference for promoting the practical deployment and further research of lattice-based cryptography.
Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].