International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Batch-OT with Optimal Rate

Zvika Brakerski , Weizmann Institute of Science
Pedro Branco , IT, IST University of Lisbon
Nico Döttling , Helmholtz Center for Information Security (CISPA)
Sihang Pu , Helmholtz Center for Information Security (CISPA)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
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 $\bbZ_2$ (or any other small-order group) inside a prime-order group $\bbZ_p$ \emph{in a function-private manner}. That is, $\bbZ_2$ operations are mapped to $\bbZ_p$ operations such that the outcome of the latter do not reveal additional information beyond the $\bbZ_2$ outcome. Our encoding technique uses the discrete Gaussian distribution, which to our knowledge was not done before in the context of DDH.
Video from EUROCRYPT 2022
  title={Batch-OT with Optimal Rate},
  author={Zvika Brakerski and Pedro Branco and Nico Döttling and Sihang Pu},