Adaptive Distributional Security for Garbling Schemes with O(| x| ) Online Complexity

Estuardo Alpírez Bock, Chris Brzuska, Pihla Karanko, Sabine Oechsner*, Kirthivaasan Puniamurthy

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu


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 2-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 NC 0 circuits to DSIM-security for arbitrary polynomial-size circuits while preserving their online complexity.

OtsikkoAdvances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
ToimittajatJian Guo, Ron Steinfeld
ISBN (painettu)9789819987207
DOI - pysyväislinkit
TilaJulkaistu - 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Conference on the Theory and Application of Cryptology and Information Security - Guangzhou, Kiina
Kesto: 4 jouluk. 20238 jouluk. 2023
Konferenssinumero: 29


NimiLecture Notes in Computer Science
Vuosikerta14438 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349


ConferenceInternational Conference on the Theory and Application of Cryptology and Information Security


Sukella tutkimusaiheisiin 'Adaptive Distributional Security for Garbling Schemes with O(| x| ) Online Complexity'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä