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

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

doi:10.1007/978-981-99-8721-4_5

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

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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

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

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Jian Guo, Ron Steinfeld
Publisher	Springer
Pages	139-171
Number of pages	33
ISBN (Print)	9789819987207
DOIs	https://doi.org/10.1007/978-981-99-8721-4_5
Publication status	Published - 2023
MoE publication type	A4 Conference publication
Event	International Conference on the Theory and Application of Cryptology and Information Security - Guangzhou, China Duration: 4 Dec 2023 → 8 Dec 2023 Conference number: 29

Publication series

Name	Lecture Notes in Computer Science
Volume	14438 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on the Theory and Application of Cryptology and Information Security
Abbreviated title	ASIACRYPT
Country/Territory	China
City	Guangzhou
Period	04/12/2023 → 08/12/2023

Access to Document

10.1007/978-981-99-8721-4_5

https://eprint.iacr.org/2024/044Licence: CC BY

Cite this

Bock, E. A., Brzuska, C., Karanko, P., Oechsner, S., & Puniamurthy, K. (2023). Adaptive Distributional Security for Garbling Schemes with O(| x| ) Online Complexity. In J. Guo, & R. Steinfeld (Eds.), Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 139-171). (Lecture Notes in Computer Science; Vol. 14438 LNCS). Springer. https://doi.org/10.1007/978-981-99-8721-4_5

Bock, Estuardo Alpírez ; Brzuska, Chris ; Karanko, Pihla et al. / Adaptive Distributional Security for Garbling Schemes with O(| x| ) Online Complexity. Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Jian Guo ; Ron Steinfeld. Springer, 2023. pp. 139-171 (Lecture Notes in Computer Science).

@inproceedings{a5d63316e07b41428f952a344cd2163c,

title = "Adaptive Distributional Security for Garbling Schemes with O(| x| ) Online Complexity",

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{\'a}{\v c}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.",

author = "Bock, {Estuardo Alp{\'i}rez} and Chris Brzuska and Pihla Karanko and Sabine Oechsner and Kirthivaasan Puniamurthy",

note = "Funding Information: We thank Christoph Egger, Pierre Meyer, the cryptography group at ENS Paris and the anonymous reviewers of Asiacrypt 2023 for the interesting discussion, and for pointing us towards the work of Hub{\'a}{\v c}ek and Wichs [31]. This work was supported by the Research Council of Finland, Blockchain Technology Laboratory at the University of Edinburgh and Input Output Global. Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2023.; International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT ; Conference date: 04-12-2023 Through 08-12-2023",

year = "2023",

doi = "10.1007/978-981-99-8721-4_5",

language = "English",

isbn = "9789819987207",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "139--171",

editor = "Jian Guo and Ron Steinfeld",

booktitle = "Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

}

Bock, EA, Brzuska, C, Karanko, P, Oechsner, S & Puniamurthy, K 2023, Adaptive Distributional Security for Garbling Schemes with O(| x| ) Online Complexity. in J Guo & R Steinfeld (eds), Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science, vol. 14438 LNCS, Springer, pp. 139-171, International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, 04/12/2023. https://doi.org/10.1007/978-981-99-8721-4_5

Adaptive Distributional Security for Garbling Schemes with O(| x| ) Online Complexity. / Bock, Estuardo Alpírez; Brzuska, Chris; Karanko, Pihla et al.
Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Jian Guo; Ron Steinfeld. Springer, 2023. p. 139-171 (Lecture Notes in Computer Science; Vol. 14438 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

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

AU - Bock, Estuardo Alpírez

AU - Brzuska, Chris

AU - Karanko, Pihla

AU - Oechsner, Sabine

AU - Puniamurthy, Kirthivaasan

N1 - Conference code: 29

PY - 2023

Y1 - 2023

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

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

UR - http://www.scopus.com/inward/record.url?scp=85180627492&partnerID=8YFLogxK

U2 - 10.1007/978-981-99-8721-4_5

DO - 10.1007/978-981-99-8721-4_5

M3 - Conference article in proceedings

AN - SCOPUS:85180627492

SN - 9789819987207

T3 - Lecture Notes in Computer Science

SP - 139

EP - 171

BT - Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Guo, Jian

A2 - Steinfeld, Ron

PB - Springer

T2 - International Conference on the Theory and Application of Cryptology and Information Security

Y2 - 4 December 2023 through 8 December 2023

ER -

Bock EA, Brzuska C, Karanko P, Oechsner S, Puniamurthy K. Adaptive Distributional Security for Garbling Schemes with O(| x| ) Online Complexity. In Guo J, Steinfeld R, editors, Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer. 2023. p. 139-171. (Lecture Notes in Computer Science). doi: 10.1007/978-981-99-8721-4_5