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)

Committed Vector Oblivious Linear Evaluation and Its Applications

Yunqing Sun, Hanlin Liu, Kang Yang, Yu Yu, Xiao Shaun Wang, Chenkai Weng

Published Nov 19, 2025• 5 citations
Publisher

Abstract

We introduce the notion of committed vector oblivious linear evaluation (C-VOLE), which allows a party holding a pre-committed vector to generate VOLE correlations with multiple parties on the committed value. It is a unifying tool that can be found useful in zero-knowledge proofs (ZKPs) of committed values, actively secure multi-party computation, private set intersection (PSI), etc.

DOI
10.1145/3719027.3744887

Related papers

Compressing Vector OLE

Elette Boyle, Geoffroy Couteau, Niv Gilboa +1 more

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 15, 2018•222 citations

LogVOLE: Succinct and Efficient Chosen-Input VOLE for ZK and Beyond

Lucien K. L. Ng, Peter Rindal, Shah Akash

Random Vector Oblivious Linear Evaluation (VOLE) correlations can be generated efficiently for zero-knowledge proofs and secure computation. Applications that need correlations on the receiver's actual input typically derandomize random VOLE by sending a linear-size vector, a main communication bottleneck. We study chosen-input VOLE (CI-VOLE), where the receiver privately chooses a large vector x, the sender fixes Δ, and the parties obtain shares of x · Δ without communicating a linearsize object. This work presents LogVOLE, a concretely efficient CIVOLE protocol with polylogarithmic end-to-end communication under Ring-LWE. The construction uses a recursive shrink/expand design: it authenticates short digests of the chosen input and then uses a succinct telescope to expand those relations back to the full vector. The protocol has O (λ log 2 (|x| + m msg )) one-time setup and query communication and O (|x|/ n ) ring operations. Here, λ is the underlying ring degree, n is the computational security parameter, and m msg is the size of the shares. LogVOLE also supports a public-key non-interactive mode: for a fixed Δ, the sender publishes reusable parameters, and a receiver sends one compact x-dependent message to obtain the matching VOLE shares. This gives a route to non-interactive VOLE-based ZK with polylogarithmic communication for arbitrary circuits. We also give a malicious-security extension in the random oracle model. Using LogVOLE, we construct the first concretely efficient VOLEbased (designated-verifier) ZK protocol for arbitrary circuits with polylogarithmic communication. At 128-bit computational and 40- bit statistical security, our implementation achieves online throughput of 13.9 million Z p correlations/s and 12.9 million ZK multiplication gates/s using 16 cores per party. With golden-seed optimization and reusable setup, our GPU implementation processes 532.3 million Z p correlations/s and 451.7 million ZK multiplication gates/s online on an H200 GPU. Using a CPU with a single thread, our implementation proves 1024 × 1024 matrix multiplication in about 4 seconds with 226 kB of communication.

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

Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures from VOLE-in-the-Head

Carsten Baum, Lennart Braun, Cyprien Delpech de Saint Guilhem +4 more

We present a new method for transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our transformation applies to a large class of ZK protocols based on oblivious transfer. In particular, we show that it can be applied to recent, fast protocols based on vector oblivious linear evaluation (VOLE), with a technique we call VOLE-in-the-head, upgrading these protocols to support public verifiability. Our resulting ZK protocols have linear proof size, and are simpler, smaller and faster than related approaches based on MPC-in-the-head. To build VOLE-in-the-head while supporting both binary circuits and large finite fields, we develop several new technical tools. One of these is a new proof of security for the SoftSpokenOT protocol (Crypto 2022), which generalizes it to produce certain types of VOLE correlations over large fields. Secondly, we present a new ZK protocol that is tailored to take advantage of this form of VOLE, which leads to a publicly verifiable VOLE-in-the-head protocol with only 2x more communication than the best, designated-verifier VOLE-based protocols. We analyze the soundness of our approach when made non-interactive using the Fiat-Shamir transform, using round-by-round soundness. As an application of the resulting NIZK, we present $$\textsf{FAEST}$$ , a post-quantum signature scheme based on AES. FAEST is the first AES-based signature scheme to be smaller than SPHINCS+, with signature sizes between 5.6 and 6.6kB at the 128-bit security level. Compared with the smallest version of SPHINCS+ (7.9kB), FAEST verification is slower, but the signing times are between 8x and 40x faster.

Lecture notes in computer science•Jan 1, 2023•95 citations

Quantum Universally Composable Oblivious Linear Evaluation

Manuel B. Santos, Paulo Mateus, Chrysoula Vlachou

Oblivious linear evaluation is a generalization of oblivious transfer, whereby two distrustful parties obliviously compute a linear function, f(x)=ax+b , i.e., each one provides their inputs that remain unknown to the other, in order to compute the output f(x) that only one of them receives. From both a structural and a security point of view, oblivious linear evaluation is fundamental for arithmetic-based secure multi-party computation protocols. In the classical case, oblivious linear evaluation protocols can be generated using oblivious transfer, and their quantum counterparts can, in principle, be constructed as straightforward extensions using quantum oblivious transfer. Here, we present the first, to the best of our knowledge, quantum protocol for oblivious linear evaluation that, furthermore, does not rely on quantum oblivious transfer. We start by presenting a semi-honest protocol, and then extend it to the dishonest setting employing a commit−and−open strategy. Our protocol uses high-dimensional quantum states to obliviously compute f(x) on Galois Fields of prime and prime-power dimension. These constructions utilize the existence of a complete set of mutually unbiased bases in prime-power dimension Hilbert spaces and their linear behaviour upon the Heisenberg-Weyl operators. We also generalize our protocol to achieve vector oblivious linear evaluation, where several instances of oblivious linear evaluation are generated, thus making the protocol more efficient. We prove the protocols to have static security in the framework of quantum universal composability.

arXiv:2204.14171•Quantum•Oct 23, 2024•2 citations

Efficient protocols for oblivious linear function evaluation from ring-LWE1

Carsten Baum, Daniel E. Escudero, Alberto Pedrouzo-Ulloa +2 more

An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function f ( x ) = a x + b, where a sender inputs the field elements a, b, and a receiver inputs x and learns f ( x ). OLE can be used to build secret-shared multiplication, and is an essential component of many secure computation applications including general-purpose multi-party computation, private set intersection and more. In this work, we present several efficient OLE protocols from the ring learning with errors (RLWE) assumption. Technically, we build two new passively secure protocols, which build upon recent advances in homomorphic secret sharing from (R)LWE (Boyle et al. in: EUROCRYPT 2019, Part II (2019) 3–33 Springer), with optimizations tailored to the setting of OLE. We upgrade these to active security using efficient amortized zero-knowledge techniques for lattice relations (Baum et al. in: CRYPTO 2018, Part II (2018) 669–699 Springer), and design new variants of zero-knowledge arguments that are necessary for some of our constructions. Our protocols offer several advantages over existing constructions. Firstly, they have the lowest communication complexity amongst previous, practical protocols from RLWE and other assumptions; secondly, they are conceptually very simple, and have just one round of interaction for the case of OLE where b is randomly chosen. We demonstrate this with an implementation of one of our passively secure protocols, which can perform more than 1 million OLEs per second over the ring Z m , for a 120-bit modulus m, on standard hardware.

Journal of Computer Security•Nov 5, 2021•7 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•2 citations
We introduce the notion of committed vector oblivious linear evaluation (C-VOLE), which allows a party holding a pre-committed vector to generate VOLE correlations with multiple parties on the committed value. It is a unifying tool that can be found useful in zero-knowledge proofs (ZKPs) of committed values, actively secure multi-party computation, private set intersection (PSI), etc.
Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.
Random Vector Oblivious Linear Evaluation (VOLE) correlations can be generated efficiently for zero-knowledge proofs and secure computation. Applications that need correlations on the receiver's actual input typically derandomize random VOLE by sending a linear-size vector, a main communication bottleneck. We study chosen-input VOLE (CI-VOLE), where the receiver privately chooses a large vector x, the sender fixes Δ, and the parties obtain shares of x · Δ without communicating a linearsize object. This work presents LogVOLE, a concretely efficient CIVOLE protocol with polylogarithmic end-to-end communication under Ring-LWE. The construction uses a recursive shrink/expand design: it authenticates short digests of the chosen input and then uses a succinct telescope to expand those relations back to the full vector. The protocol has O (λ log 2 (|x| + m msg )) one-time setup and query communication and O (|x|/ n ) ring operations. Here, λ is the underlying ring degree, n is the computational security parameter, and m msg is the size of the shares. LogVOLE also supports a public-key non-interactive mode: for a fixed Δ, the sender publishes reusable parameters, and a receiver sends one compact x-dependent message to obtain the matching VOLE shares. This gives a route to non-interactive VOLE-based ZK with polylogarithmic communication for arbitrary circuits. We also give a malicious-security extension in the random oracle model. Using LogVOLE, we construct the first concretely efficient VOLEbased (designated-verifier) ZK protocol for arbitrary circuits with polylogarithmic communication. At 128-bit computational and 40- bit statistical security, our implementation achieves online throughput of 13.9 million Z p correlations/s and 12.9 million ZK multiplication gates/s using 16 cores per party. With golden-seed optimization and reusable setup, our GPU implementation processes 532.3 million Z p correlations/s and 451.7 million ZK multiplication gates/s online on an H200 GPU. Using a CPU with a single thread, our implementation proves 1024 × 1024 matrix multiplication in about 4 seconds with 226 kB of communication.
We present a new method for transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our transformation applies to a large class of ZK protocols based on oblivious transfer. In particular, we show that it can be applied to recent, fast protocols based on vector oblivious linear evaluation (VOLE), with a technique we call VOLE-in-the-head, upgrading these protocols to support public verifiability. Our resulting ZK protocols have linear proof size, and are simpler, smaller and faster than related approaches based on MPC-in-the-head. To build VOLE-in-the-head while supporting both binary circuits and large finite fields, we develop several new technical tools. One of these is a new proof of security for the SoftSpokenOT protocol (Crypto 2022), which generalizes it to produce certain types of VOLE correlations over large fields. Secondly, we present a new ZK protocol that is tailored to take advantage of this form of VOLE, which leads to a publicly verifiable VOLE-in-the-head protocol with only 2x more communication than the best, designated-verifier VOLE-based protocols. We analyze the soundness of our approach when made non-interactive using the Fiat-Shamir transform, using round-by-round soundness. As an application of the resulting NIZK, we present FAEST\textsf{FAEST}FAEST , a post-quantum signature scheme based on AES. FAEST is the first AES-based signature scheme to be smaller than SPHINCS+, with signature sizes between 5.6 and 6.6kB at the 128-bit security level. Compared with the smallest version of SPHINCS+ (7.9kB), FAEST verification is slower, but the signing times are between 8x and 40x faster.
Oblivious linear evaluation is a generalization of oblivious transfer, whereby two distrustful parties obliviously compute a linear function, f(x)=ax+b , i.e., each one provides their inputs that remain unknown to the other, in order to compute the output f(x) that only one of them receives. From both a structural and a security point of view, oblivious linear evaluation is fundamental for arithmetic-based secure multi-party computation protocols. In the classical case, oblivious linear evaluation protocols can be generated using oblivious transfer, and their quantum counterparts can, in principle, be constructed as straightforward extensions using quantum oblivious transfer. Here, we present the first, to the best of our knowledge, quantum protocol for oblivious linear evaluation that, furthermore, does not rely on quantum oblivious transfer. We start by presenting a semi-honest protocol, and then extend it to the dishonest setting employing a commit−and−open strategy. Our protocol uses high-dimensional quantum states to obliviously compute f(x) on Galois Fields of prime and prime-power dimension. These constructions utilize the existence of a complete set of mutually unbiased bases in prime-power dimension Hilbert spaces and their linear behaviour upon the Heisenberg-Weyl operators. We also generalize our protocol to achieve vector oblivious linear evaluation, where several instances of oblivious linear evaluation are generated, thus making the protocol more efficient. We prove the protocols to have static security in the framework of quantum universal composability.
An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function f ( x ) = a x + b, where a sender inputs the field elements a, b, and a receiver inputs x and learns f ( x ). OLE can be used to build secret-shared multiplication, and is an essential component of many secure computation applications including general-purpose multi-party computation, private set intersection and more. In this work, we present several efficient OLE protocols from the ring learning with errors (RLWE) assumption. Technically, we build two new passively secure protocols, which build upon recent advances in homomorphic secret sharing from (R)LWE (Boyle et al. in: EUROCRYPT 2019, Part II (2019) 3–33 Springer), with optimizations tailored to the setting of OLE. We upgrade these to active security using efficient amortized zero-knowledge techniques for lattice relations (Baum et al. in: CRYPTO 2018, Part II (2018) 669–699 Springer), and design new variants of zero-knowledge arguments that are necessary for some of our constructions. Our protocols offer several advantages over existing constructions. Firstly, they have the lowest communication complexity amongst previous, practical protocols from RLWE and other assumptions; secondly, they are conceptually very simple, and have just one round of interaction for the case of OLE where b is randomly chosen. We demonstrate this with an implementation of one of our passively secure protocols, which can perform more than 1 million OLEs per second over the ring Z m , for a 120-bit modulus m, on standard hardware.
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.