Paper 2024/044

Adaptive Distributional Security for Garbling Schemes with $\mathcal{O}(|x|)$ Online Complexity

Estuardo Alpírez Bock, Xiphera LTD
Chris Brzuska, Aalto University
Pihla Karanko, Aalto University
Sabine Oechsner, University of Edinburgh
Kirthivaasan Puniamurthy, Aalto University

Garbling schemes allow to garble a circuit $C$ and an input $x$ such that $C(x)$ can be computed while hiding both $C$ and $x$. In the context of adaptive security, an adversary specifies the input to the circuit after seeing the garbled circuit, so that one can pre-process the garbling of $C$ and later only garble the input $x$ in the online phase. Since the online phase may be time-critical, it is an interesting question how much information needs to be transmitted in this phase and ideally, this should be close to $|x|$. Unfortunately, Applebaum, Ishai, Kushilevitz, and Waters (AIKW, CRYPTO 2013) show that for some circuits, specifically PRGs, achieving online complexity close to $|x|$ is impossible with simulation-based security, and Hubáček and Wichs (HW, ITCS 2015) show that online complexity of maliciously secure two-party computation needs to grow with the incompressibility entropy of the function. We thus seek to understand under which circumstances optimal online complexity is feasible despite these strong lower bounds. Our starting point is the observation that lower bounds (only) concern cryptographic circuits and that, when an embedded secret is not known to the adversary (distinguisher), then the lower bound techniques do not seem to apply. Our main contribution is distributional simulation-based security (DSIM), a framework for capturing weaker, yet meaningful simulation-based (adaptive) security which does not seem to suffer from impossibility results akin to AIKW. We show that DSIM can be used to prove security of a distributed symmetric encryption protocol built around garbling. We also establish a bootstrapping result from DSIM-security for $\text{NC}^0$ circuits to DSIM-security for arbitrary polynomial-size circuits while preserving their online complexity.

Available format(s)
Publication info
A major revision of an IACR publication in ASIACRYPT 2023
garbled circuitsgarbling schemeadaptive securityonline complexitylower bounds
Contact author(s)
estuardo alpirezbock @ xiphera com
chris brzuska @ aalto fi
pihla karanko @ aalto fi
s oechsner @ ed ac uk
kirthivaasan puniamurthy @ aalto fi
2024-02-16: revised
2024-01-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Estuardo Alpírez Bock and Chris Brzuska and Pihla Karanko and Sabine Oechsner and Kirthivaasan Puniamurthy},
      title = {Adaptive Distributional Security for Garbling Schemes with $\mathcal{O}(|x|)$ Online Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2024/044},
      year = {2024},
      doi = {10.1007/978-981-99-8721-4_5},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.