CISPA
Browse
cispa_all_3712.pdf (570.3 kB)

Batch-OT with Optimal Rate

Download (570.3 kB)
conference contribution
posted on 2023-11-29, 18:21 authored by Zvika Brakerski, Pedro Branco, Nico DöttlingNico Döttling, Sihang PuSihang 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� 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 Z2 (or any other small-order group) inside a prime-order group Zp in a function-private manner. That is, Z2 operations are mapped to Zp operations such that the outcome of the latter do not reveal additional information beyond the Z2 outcome. Our encoding technique uses the discrete Gaussian distribution, which to our knowledge was not done before in the context of DDH.

History

Preferred Citation

Zvika Brakerski, Pedro Branco, Nico Döttling and Sihang Pu. Batch-OT with Optimal Rate. In: International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT)

Legacy Posted Date

2022-06-08

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3712, title = "Batch-OT with Optimal Rate", author = "Brakerski, Zvika and Branco, Pedro and Döttling, Nico and Pu, Sihang", booktitle="{International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC