**Batch-OT with Optimal Rate**

*Zvika Brakerski and Pedro Branco and Nico DÃ¶ttling and Sihang Pu*

**Abstract: **We show that it is possible to perform $n$ independent copies of $1$-out-of-$2$ oblivious transfer in two messages, where the communication complexity of the receiver and sender (each) is $n(1+o(1))$ for sufficiently large $n$. Note that this matches the information-theoretic lower bound. Prior to this work, this was only achievable by using the heavy machinery of rate-$1$ fully homomorphic encryption (Rate-$1$ FHE, Brakerski et al., TCC 2019).

To achieve rate-$1$ both on the receiver's and sender's end, we use the LPN assumption, with slightly sub-constant noise rate $1/m^{\epsilon}$ for any $\epsilon>0$ together with either the DDH, QR or LWE assumptions. In terms of efficiency, our protocols only rely on linear homomorphism, as opposed to the FHE-based solution which inherently requires an expensive ``bootstrapping'' operation. We believe that in terms of efficiency we compare favorably to existing batch-OT protocols, while achieving superior communication complexity. We show similar results for Oblivious Linear Evaluation (OLE).

For our DDH-based solution we develop a new technique that may be of independent interest. We show that it is possible to ``emulate'' the binary group $\mathbb{Z}_2$ (or any other small-order group) inside a prime-order group $\mathbb{Z}_p$ in a function-private manner. That is, $\mathbb{Z}_2$ operations are mapped to $\mathbb{Z}_p$ operations such that the outcome of the latter do not reveal additional information beyond the $\mathbb{Z}_2$ outcome. Our encoding technique uses the discrete Gaussian distribution, which to our knowledge was not done before in the context of DDH.

**Category / Keywords: **cryptographic protocols / Oblivious transfer

**Original Publication**** (with minor differences): **IACR-EUROCRYPT-2022

**Date: **received 7 Mar 2022, last revised 14 Mar 2022

**Contact author: **pmbranco at math tecnico ulisboa pt, zvika brakerski at weizmann ac il, nico doettling at gmail com, push beni at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20220314:083134 (All versions of this report)

**Short URL: **ia.cr/2022/314

[ Cryptology ePrint archive ]