Cryptology ePrint Archive: Report 2022/314

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:

[ Cryptology ePrint archive ]