Paper 2024/102

Laconic Branching Programs from the Diffie-Hellman Assumption

Sanjam Garg, NTT Research, University of California, Berkeley
Mohammad Hajiabadi, University of Waterloo
Peihan Miao, Brown University
Alice Murphy, University of Waterloo

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$.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in PKC 2024
Laconic cryptographyunbalanced secure computationbranching programs
Contact author(s)
sanjamg @ berkeley edu
mdhajiabadi @ uwaterloo ca
peihan_miao @ brown edu
anlmurph @ uwaterloo ca
2024-01-26: approved
2024-01-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Mohammad Hajiabadi and Peihan Miao and Alice Murphy},
      title = {Laconic Branching Programs from the Diffie-Hellman Assumption},
      howpublished = {Cryptology ePrint Archive, Paper 2024/102},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.