Welcome to the resource topic for 2022/314
Title:
Batch-OT with Optimal Rate
Authors: Zvika Brakerski, Pedro Branco, Nico Döttling, Sihang Pu
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 \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.
ePrint: https://eprint.iacr.org/2022/314
Talk: https://www.youtube.com/watch?v=QpgrjEZPXFI
Slides: https://iacr.org/submit/files/slides/2022/eurocrypt/eurocrypt2022/280/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .