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: ia.cr/2022/314