Abstract. We propose a one-round 1-out-of-n computationally-private information retrieval protocol for ℓ-bit strings with low-degree polylogarithmic receivercomputation, linear sender-computation and communication Θ(k · log 2 n + ℓ · log n), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1out-of-n oblivious-transfer protocol for ℓ-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model. Keywords. Computationally-private information retrieval, length-flexible additively homomorphic public-key cryptosystem, oblivious transfer. 1Abstract. We propose a one-round 1-out-of-n computationally-private information retrieval protocol for ℓ-bit strings with low-degree polylogarithmic receivercomputation, linear sender-computation and communication Θ(k · log 2 n + ℓ · log n), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1out-of-n oblivious-transfer protocol for ℓ-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model. Keywords. Computationally-private information retrieval, length-flexible additively homomorphic public-key cryptosystem, oblivious transfer. 1

Jan 1, 20044 citations

New Communication-Efficient Oblivious Transfer Protocols Based on Pairings

Helger Lipmaa

Lecture notes in computer scienceSep 17, 200810 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

Effective Oblivious Transfer Using a Probabilistic Encryption

Alexander Frolov

Advances in intelligent and soft computingJul 11, 20121 citation

Homomorphic Encryption based k-out-of-n Oblivious Transfer Protocols

Mummoorthy Murugesan, Wei Jiang, Erhan Nergiz +1 more

Oblivious Transfer (OT) is an important cryptographic tool, which has found its usage in many crypto protocols, such as Secure Multiparty Computations [9], Certified E-mail [2] and Simultaneous Contract Signing [20].In this paper, we propose three k-out-of-n OT (OT n k ) protocols based on additive homomorphic encryption.Two of these protocols prohibit malicious behaviors from both sender and receiver.We also achieve efficient communication complexity bounded by O(l • n) in bits, where l is the size of the encryption key.The computational complexity is same or better than the most efficient existing protocols.Due to the semantic security property, the sender cannot get receiver's selection.When the receiver tries to retrieve more than k values, the receiver is caught cheating with 1 -1/m probability (Protocol II) or the receiver is unable to get any value at all (Protocol III).We introduce a novel technique based on the solvability of linear equations, which could find its way into other applications.We also provide an experimental analysis to compare the efficiency of the protocols.Oblivious Transfer (OT) is an important cryptographic tool, which has found its usage in many crypto protocols, such as Secure Multiparty Computations [9], Certified E-mail [2] and Simultaneous Contract Signing [20].In this paper, we propose three k-out-of-n OT (OT n k ) protocols based on additive homomorphic encryption.Two of these protocols prohibit malicious behaviors from both sender and receiver.We also achieve efficient communication complexity bounded by O(l • n) in bits, where l is the size of the encryption key.The computational complexity is same or better than the most efficient existing protocols.Due to the semantic security property, the sender cannot get receiver's selection.When the receiver tries to retrieve more than k values, the receiver is caught cheating with 1 -1/m probability (Protocol II) or the receiver is unable to get any value at all (Protocol III).We introduce a novel technique based on the solvability of linear equations, which could find its way into other applications.We also provide an experimental analysis to compare the efficiency of the protocols.

Jan 1, 20092 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