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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in ASIACRYPT 2023
DOI
10.1007/978-981-99-8721-4_5
Keywords
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
History
2024-02-16: revised
2024-01-10: received
See all versions
Short URL
https://ia.cr/2024/044
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/044,
      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},
      url = {https://eprint.iacr.org/2024/044}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.