Welcome to the resource topic for 2024/102
Title:
Laconic Branching Programs from the Diffie-Hellman Assumption
Authors: Sanjam Garg, Mohammad Hajiabadi, Peihan Miao, Alice Murphy
Abstract:Laconic cryptography enables secure two-party computation (2PC) on unbalanced inputs with asymptotically-optimal communication in just two rounds of communication. In particular, the receiver (who sends the first-round message) holds a long input and the sender (who sends the second-round message) holds a short input, and the size of their communication to securely compute a function on their joint inputs only grows with the size of the sender’s input and is independent of the receiver’s input size.
The work on laconic oblivious transfer (OT) [Cho et al. CRYPTO 2017] and laconic private set intersection (PSI) [Alamati et al. TCC 2021] shows how to achieve secure laconic computation for OT and PSI from the Diffie-Hellman assumption.
In this work, we push the limits further and achieve laconic branching programs from the Diffie-Hellman assumption. In particular, the receiver holds a large branching program P and the sender holds a short input x. We present a two-round 2PC protocol that allows the receiver to learn x iff P(x) =1, and nothing else. The communication only grows with the size of x and the depth of P, and does not further depend on the size of P.
ePrint: https://eprint.iacr.org/2024/102
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 .