Paper 2022/314

Batch-OT with Optimal Rate

Zvika Brakerski, Pedro Branco, Nico Döttling, and Sihang Pu


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.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Oblivious transfer
Contact author(s)
pmbranco @ math tecnico ulisboa pt
zvika brakerski @ weizmann ac il
nico doettling @ gmail com
push beni @ gmail com
2022-03-14: revised
2022-03-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zvika Brakerski and Pedro Branco and Nico Döttling and Sihang Pu},
      title = {Batch-OT with Optimal Rate},
      howpublished = {Cryptology ePrint Archive, Paper 2022/314},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.