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

ACM SIGSAC Conference on Computer and Communications Security (CCS)

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

Jie Xu

Published Nov 19, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1145/3719027.3765572

Related papers

Efficient Post-Quantum OPRF from TFHE Key Transformation with Application to OPAQUE

Mihail Plesa, Robert Poenaru, S Ebert David

Abstract We present a highly efficient post-quantum Randomized Oblivious Pseudorandom Function (OPRF) construction based on a novel TFHE key transformation technique. Unlike prior lattice-based OPRF schemes that rely on complex homomorphic PRF evaluation, our approach leverages the algebraic structure of TFHE to enable direct ciphertext transformation, resulting in significant performance improvements. Our protocol achieves strong security under the Learning With Errors (LWE) assumption and provides session unlinkability, making it well-suited for privacy-preserving applications. We demonstrate the practical efficiency of our construction with a Rust implementation, achieving substantial speedups over existing schemes. Furthermore, we show how our Randomized OPRF can be adapted for use in the OPAQUE password-authenticated key exchange protocol by employing a singularization technique to ensure deterministic outputs when required. This work highlights a new, practical path for post-quantum OPRFs with strong privacy and efficiency guarantees.

•Mar 18, 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•4 citations

A Survey of Post-Quantum Oblivious Protocols

Altana Felixovna Khutsaeva, Леевик Антон Георгиевич, Sergey Valentinovich Bezzateev

Modern distributed computing systems and applications with strict privacy requirements demand robust data confidentiality. A primary challenge involves enabling parties to exchange data or perform joint computations. These interactions must avoid revealing private information about the data. Protocols with the obliviousness property, known as oblivious protocols, address this issue. They ensure that no party learns more than necessary. This survey analyzes the security and performance of post-quantum oblivious protocols, with a focus on oblivious transfer and oblivious pseudorandom functions. The evaluation assesses resilience against malicious adversaries in the Universal Composability framework. Efficiency is quantified through communication and computational overhead. It identifies optimal scenarios for these protocols. This paper also surveys related primitives, such as oblivious signatures and data structures, along with their applications. Key findings highlight the inherent trade-offs between computational cost and communication complexity in post-quantum oblivious constructions. Open challenges and future research directions are outlined. Emphasis is placed on quantum-resistant designs and formal security proofs in stronger adversarial models.

Cryptography•Sep 27, 2025•2 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•2 citations

Lattice-Based Simulatable VRFs: Challenges and Future Directions

Carlo Brunetta, Bei Liang, Aikaterini Mitrokotsa

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.

Journal of Internet Services and Information Security•Jan 1, 2018•3 citations

A Maliciously-Secure Post-Quantum OPRF from Crypto Dark Matter

Diego F. Aranha, Aron van Baarsen, A C Hansen +2 more

We construct protocols for oblivious pseudorandom functions (OPRFs) based on alternating moduli assumptions in the 'Crypto Dark Matter' paradigm (Boneh et al, TCC 2016). Prior OPRFs based on this type of assumption were only secure against a semi-honest adversary. We show how to obtain maliciously secure protocols, by leveraging new cut-and-choose techniques for generating correlated randomness based on vector oblivious linear evaluation (VOLE), which allow efficient conversions between different moduli in zero-knowledge and secure two-party computation. Compared with the state-of-the-art GOLD OPRF (Yang et al, S&P 2025), our construction has a faster online phase in all settings, as well as overall better efficiency in the small-batch setting. Furthermore, our construction supports obtaining a secret-shared output, and can be extended to handle secretshared inputs. This opens up additional applications in variants of private set intersection and secure database operations.

IEEE Symposium on Security and Privacy (S&P)•May 18, 2026•0 citations
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.
Abstract We present a highly efficient post-quantum Randomized Oblivious Pseudorandom Function (OPRF) construction based on a novel TFHE key transformation technique. Unlike prior lattice-based OPRF schemes that rely on complex homomorphic PRF evaluation, our approach leverages the algebraic structure of TFHE to enable direct ciphertext transformation, resulting in significant performance improvements. Our protocol achieves strong security under the Learning With Errors (LWE) assumption and provides session unlinkability, making it well-suited for privacy-preserving applications. We demonstrate the practical efficiency of our construction with a Rust implementation, achieving substantial speedups over existing schemes. Furthermore, we show how our Randomized OPRF can be adapted for use in the OPAQUE password-authenticated key exchange protocol by employing a singularization technique to ensure deterministic outputs when required. This work highlights a new, practical path for post-quantum OPRFs with strong privacy and efficiency guarantees.
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].
Modern distributed computing systems and applications with strict privacy requirements demand robust data confidentiality. A primary challenge involves enabling parties to exchange data or perform joint computations. These interactions must avoid revealing private information about the data. Protocols with the obliviousness property, known as oblivious protocols, address this issue. They ensure that no party learns more than necessary. This survey analyzes the security and performance of post-quantum oblivious protocols, with a focus on oblivious transfer and oblivious pseudorandom functions. The evaluation assesses resilience against malicious adversaries in the Universal Composability framework. Efficiency is quantified through communication and computational overhead. It identifies optimal scenarios for these protocols. This paper also surveys related primitives, such as oblivious signatures and data structures, along with their applications. Key findings highlight the inherent trade-offs between computational cost and communication complexity in post-quantum oblivious constructions. Open challenges and future research directions are outlined. Emphasis is placed on quantum-resistant designs and formal security proofs in stronger adversarial models.
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.
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.
We construct protocols for oblivious pseudorandom functions (OPRFs) based on alternating moduli assumptions in the 'Crypto Dark Matter' paradigm (Boneh et al, TCC 2016). Prior OPRFs based on this type of assumption were only secure against a semi-honest adversary. We show how to obtain maliciously secure protocols, by leveraging new cut-and-choose techniques for generating correlated randomness based on vector oblivious linear evaluation (VOLE), which allow efficient conversions between different moduli in zero-knowledge and secure two-party computation. Compared with the state-of-the-art GOLD OPRF (Yang et al, S&P 2025), our construction has a faster online phase in all settings, as well as overall better efficiency in the small-batch setting. Furthermore, our construction supports obtaining a secret-shared output, and can be extended to handle secretshared inputs. This opens up additional applications in variants of private set intersection and secure database operations.