Title: Batch-OT with Optimal Rate

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.

Joint work with Pedro Branco, Zvika Brakerski and Sihang Pu

About the speaker: Nico Döttling is a tenure-track faculty at the Helmholtz Center for Information Security (CISPA) in Saarbrücken. This week, he is visiting the Aarhus Crypto group.

About the seminar: The Aarhus Crypto Seminars are weekly seminars open to everyone with an interest in recent research in cryptology and information security. The seminars are hosted by the Cryptography and Security Research Group at Aarhus University. Further details about the research group and the weekly seminars can be found here: https://cs.au.dk/da/research/cryptography-and-security/seminar