A combiner securely implements a functionality out of a set implementations of another functionality from which some may be insecure. We present two efficient combiners for oblivious linear function evaluation (OLFE). The first is a constant-rate OLFE combiner in the semihonest model, the second combiner implements Rabin string oblivious transfer (RabinOT) from OLFE in the malicious model. As an application, we show a very efficient reductions in the malicious model of RabinOT over strings to one-out-of-two oblivious transfer over bits (OT) that is only secure in the semihonest model. For string of size ℓ = ω(k 2), our reductions uses only 4ℓ + o(ℓ) instances of OT, while previous results required Ω(ℓk 2). Our new reduction leads to an efficiency improvement for general multi-party computation (MPC) based on semi-honest OT, and makes it almost as efficient as MPC based on malicious OT. All reductions are unconditionally secure, black-box, universally composable and secure against adaptive adversaries. 1 1A combiner securely implements a functionality out of a set implementations of another functionality from which some may be insecure. We present two efficient combiners for oblivious linear function evaluation (OLFE). The first is a constant-rate OLFE combiner in the semihonest model, the second combiner implements Rabin string oblivious transfer (RabinOT) from OLFE in the malicious model. As an application, we show a very efficient reductions in the malicious model of RabinOT over strings to one-out-of-two oblivious transfer over bits (OT) that is only secure in the semihonest model. For string of size ℓ = ω(k 2), our reductions uses only 4ℓ + o(ℓ) instances of OT, while previous results required Ω(ℓk 2). Our new reduction leads to an efficiency improvement for general multi-party computation (MPC) based on semi-honest OT, and makes it almost as efficient as MPC based on malicious OT. All reductions are unconditionally secure, black-box, universally composable and secure against adaptive adversaries. 1 1

Jan 1, 20091 citation

Secure Arithmetic Computation with Constant Computational Overhead

Benny Applebaum, Ivan Damgård, Yuval Ishai +2 more

Lecture notes in computer scienceJan 1, 201788 citations

Efficient Maliciously Secure Oblivious Exponentiations

Carsten Baum, Jens Berlips, W Q Chen +17 more

Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009). It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance. Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor o ( 1 ) as the batch size increases. The obvious solution using zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments. Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model. We also present a variant of our maliciously secure protocol that does not rely on the OEP but nevertheless only has overhead o ( 1 ) over the known semi-honest protocol. Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against malicious attackers.Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009). It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance. Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor o ( 1 ) as the batch size increases. The obvious solution using zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments. Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model. We also present a variant of our maliciously secure protocol that does not rely on the OEP but nevertheless only has overhead o ( 1 ) over the known semi-honest protocol. Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against malicious attackers.

IACR Communications in CryptologyOct 7, 20243 citations

Efficient Protocols for Oblivious Linear Function Evaluation from Ring-LWE

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

Lecture notes in computer scienceJan 1, 202020 citations

Gold OPRF: Post-Quantum Oblivious Power-Residue PRF

Yibin Yang, Fabrice Benhamouda, Shai Halevi +2 more

We propose plausible post-quantum (PQ) oblivious pseudorandom functions (OPRFs) based on the Power-Residue PRF (Damgård CRYPTO'88), a generalization of the Legendre PRF. For security parameter $\lambda$ , we consider the PRF Gold $k(x)$ that maps an integer $x$ modulo a public prime $p=2^{\lambda}\cdot g+1$ to the element $(k+x)^{g}\text{mod}\ p$ , where $g$ is public and $\log g\approx 2\lambda$ . At the core of our constructions are efficient novel methods for evaluating Gold within two-party computation (2PC-Gold), achieving different security requirements. Here, the server $\mathcal{P}_{s}$ holds the PRF key $k$ whereas the client $\mathcal{P}_{c}$ holds the PRF input $x$ , and they jointly evaluate Gold in $2\mathbf{PC}$ . 2 PC-Gold uses standard Vector Oblivious Linear Evaluation (VOLE) correlations and is information-theoretic and constant-round in the (V)OLE-hybrid model. We show: •For a semi-honest $\mathcal{P}_{s}$ and a malicious $\mathcal{P}_{c}$ : a 2PC-Gold that just uses a single (V)OLE correlation, and has a communication complexity of 3 field elements (2 field elements if we only require a uniformly sampled key) and a computational complexity of $\mathcal{O}(\lambda)$ field operations. We refer to this as half-malicious security. •For malicious $\mathcal{P}_{s}$ and $\mathcal{P}_{c}$ : a 2PC-Gold that just uses $\frac{\lambda}{4}+\mathcal{O}(1)$ VOLE correlations, and has a communication complexity of $\frac{\lambda}{4}+\mathcal{O}(1)$ field elements and a computational complexity of $\mathcal{O}(\lambda)$ field operations. These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs where $\mathcal{P}_{c}$ repeatedly evaluates the PRF under the same key. Furthermore, we extend 2PC-Gold to Verifiable OPRFs and use the methodology from Beullens et al. (Eurocrypt'25) to get strong OPRF security in the universally composable setting. All the protocols are efficient in practice. We implemented 2PC-Gold-with (PQ) VOLEs-and benchmarked them. For example, our half-malicious (resp. malicious) n-batched PQ OPRFs incur about 100B (resp. 1.9KB) of amortized communication for $\lambda=128$ .We propose plausible post-quantum (PQ) oblivious pseudorandom functions (OPRFs) based on the Power-Residue PRF (Damgård CRYPTO'88), a generalization of the Legendre PRF. For security parameter$\lambda$, we consider the PRF Gold$k(x)$that maps an integer$x$modulo a public prime$p=2^{\lambda}\cdot g+1$to the element$(k+x)^{g}\text{mod}\ p$, where$g$is public and$\log g\approx 2\lambda$. At the core of our constructions are efficient novel methods for evaluating Gold within two-party computation (2PC-Gold), achieving different security requirements. Here, the server$\mathcal{P}_{s}$holds the PRF key$k$whereas the client$\mathcal{P}_{c}$holds the PRF input$x$, and they jointly evaluate Gold in$2\mathbf{PC}$. 2 PC-Gold uses standard Vector Oblivious Linear Evaluation (VOLE) correlations and is information-theoretic and constant-round in the (V)OLE-hybrid model. We show: •For a semi-honest$\mathcal{P}_{s}$and a malicious$\mathcal{P}_{c}$: a 2PC-Gold that just uses a single (V)OLE correlation, and has a communication complexity of 3 field elements (2 field elements if we only require a uniformly sampled key) and a computational complexity of$\mathcal{O}(\lambda)$field operations. We refer to this as half-malicious security. •For malicious$\mathcal{P}_{s}$and$\mathcal{P}_{c}$: a 2PC-Gold that just uses$\frac{\lambda}{4}+\mathcal{O}(1)$VOLE correlations, and has a communication complexity of$\frac{\lambda}{4}+\mathcal{O}(1)$field elements and a computational complexity of$\mathcal{O}(\lambda)$field operations. These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs where$\mathcal{P}_{c}$repeatedly evaluates the PRF under the same key. Furthermore, we extend 2PC-Gold to Verifiable OPRFs and use the methodology from Beullens et al. (Eurocrypt'25) to get strong OPRF security in the universally composable setting. All the protocols are efficient in practice. We implemented 2PC-Gold-with (PQ) VOLEs-and benchmarked them. For example, our half-malicious (resp. malicious) n-batched PQ OPRFs incur about 100B (resp. 1.9KB) of amortized communication for$\lambda=128$.

IEEE Symposium on Security and Privacy (S&P)May 12, 20258 citations

We propose plausible post-quantum (PQ) oblivious pseudorandom functions (OPRFs) based on the Power-Residue PRF (Damgård CRYPTO'88), a generalization of the Legendre PRF. For security parameter

\lambda

, we consider the PRF Gold

k(x)

that maps an integer

x

modulo a public prime

p=2^{\lambda}\cdot g+1

to the element

(k+x)^{g}\text{mod}\ p

, where

g

is public and

\log g\approx 2\lambda

. At the core of our constructions are efficient novel methods for evaluating Gold within two-party computation (2PC-Gold), achieving different security requirements. Here, the server

\mathcal{P}_{s}

holds the PRF key

k

whereas the client

\mathcal{P}_{c}

holds the PRF input

x

, and they jointly evaluate Gold in

2\mathbf{PC}

. 2 PC-Gold uses standard Vector Oblivious Linear Evaluation (VOLE) correlations and is information-theoretic and constant-round in the (V)OLE-hybrid model. We show: •For a semi-honest

\mathcal{P}_{s}

and a malicious

\mathcal{P}_{c}

: a 2PC-Gold that just uses a single (V)OLE correlation, and has a communication complexity of 3 field elements (2 field elements if we only require a uniformly sampled key) and a computational complexity of

\mathcal{O}(\lambda)

field operations. We refer to this as half-malicious security. •For malicious

\mathcal{P}_{s}

and

\mathcal{P}_{c}

: a 2PC-Gold that just uses

\frac{\lambda}{4}+\mathcal{O}(1)

VOLE correlations, and has a communication complexity of

\frac{\lambda}{4}+\mathcal{O}(1)

field elements and a computational complexity of

\mathcal{O}(\lambda)

field operations. These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs where

\mathcal{P}_{c}

repeatedly evaluates the PRF under the same key. Furthermore, we extend 2PC-Gold to Verifiable OPRFs and use the methodology from Beullens et al. (Eurocrypt'25) to get strong OPRF security in the universally composable setting. All the protocols are efficient in practice. We implemented 2PC-Gold-with (PQ) VOLEs-and benchmarked them. For example, our half-malicious (resp. malicious) n-batched PQ OPRFs incur about 100B (resp. 1.9KB) of amortized communication for

\lambda=128