International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Batch-OT with Optimal Rate

Authors:
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)
Download:
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ϵ for any ϵ>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 \bbZ2 (or any other small-order group) inside a prime-order group \bbZp \emph{in a function-private manner}. That is, \bbZ2 operations are mapped to \bbZp operations such that the outcome of the latter do not reveal additional information beyond the \bbZ2 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
BibTeX
@inproceedings{eurocrypt-2022-31828,
  title={Batch-OT with Optimal Rate},
  publisher={Springer-Verlag},
  author={Zvika Brakerski and Pedro Branco and Nico Döttling and Sihang Pu},
  year=2022
}