A State-Separating Proof for Yao's Garbling Scheme

Chris Brzuska; Sabine Oechsner

doi:10.1109/CSF57540.2023.00009

A State-Separating Proof for Yao's Garbling Scheme

Chris Brzuska
, Sabine Oechsner

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Secure multiparty computation enables mutually distrusting parties to compute a public function of their secret inputs. One of the main approaches for designing MPC protocols are garbled circuits whose core component is usually referred to as a garbling scheme. In this work, we revisit the security of Yao's garbling scheme and provide a modular security proof which composes the security of multiple layer garblings to prove security of the full circuit garbling. We perform our security proof in the style of state-separating proofs (ASIACRYPT 2018).

Original language	English
Title of host publication	2023 IEEE 36th Computer Security Foundations Symposium (CSF)
Publisher	IEEE Computer Society
Pages	137-152
Number of pages	16
ISBN (Electronic)	9798350321920
ISBN (Print)	9798350321937
DOIs	https://doi.org/10.1109/CSF57540.2023.00009
Publication status	Published - 2023
Externally published	Yes
Event	36th IEEE Computer Security Foundations Symposium, CSF 2023 - Haifa, Israel Duration: 9 Jul 2023 → 13 Jul 2023

Publication series

Name	Proceedings - IEEE Computer Security Foundations Symposium
ISSN (Print)	1940-1434

Conference

Conference	36th IEEE Computer Security Foundations Symposium, CSF 2023
Country/Territory	Israel
City	Haifa
Period	9/07/23 → 13/07/23

Funding

We are grateful to Christoph Egger, Pihla Karanko, Markulf Kohlweiss, Kirthivaasan Puniamurthy, Jan Winkelmann, Luisa Zeppelin, and the participants of the Advanced Topics in Cryptography course 2021 at Aalto University for useful suggestions on the presentation. We thank Franc ois Dupressoir for insightful discussions about the EasyCrypt security proof of Yao s garbled circuits in [2]. Finally, we thank the reviewers of CSF 2022 for their thorough comments and helpful sug- gestions that significantly improved the article. All remaining shortcomings of this article are, of course, our responsibility. Sabine Oechsner was supported by the European Research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme under grant agreement No 669255 (MPCPRO), the Concordium Blockhain Research Center, Aarhus University, Denmark, and the Danish Independent Research Council under Grant-ID DFF-8021-00366B (BETHE). This work was supported by the Blockchain Technology Laboratory at the University of Edinburgh and funded by Input Output Global and the Academy of Finland.

Funders	Funder number
Blockchain Technology Laboratory
Concordium Blockhain Research Center
European Unions’s Horizon 2020 research and innovation programme	669255
Aarhus Universitet
European Research Council
University of Edinburgh
Academy of Finland
Aalto-Yliopisto
Danmarks Frie Forskningsfond	DFF-8021-00366B

Access to Document

10.1109/CSF57540.2023.00009

Persistent URL (handle)

Persistent link

Cite this

@inproceedings{5a51987acaa84c43bb4bf5bcc7d01683,

title = "A State-Separating Proof for Yao's Garbling Scheme",

abstract = "Secure multiparty computation enables mutually distrusting parties to compute a public function of their secret inputs. One of the main approaches for designing MPC protocols are garbled circuits whose core component is usually referred to as a garbling scheme. In this work, we revisit the security of Yao's garbling scheme and provide a modular security proof which composes the security of multiple layer garblings to prove security of the full circuit garbling. We perform our security proof in the style of state-separating proofs (ASIACRYPT 2018).",

author = "Chris Brzuska and Sabine Oechsner",

year = "2023",

doi = "10.1109/CSF57540.2023.00009",

language = "English",

isbn = "9798350321937",

series = "Proceedings - IEEE Computer Security Foundations Symposium",

publisher = "IEEE Computer Society",

pages = "137--152",

booktitle = "2023 IEEE 36th Computer Security Foundations Symposium (CSF)",

note = "36th IEEE Computer Security Foundations Symposium, CSF 2023 ; Conference date: 09-07-2023 Through 13-07-2023",

}

Brzuska, C & Oechsner, S 2023, A State-Separating Proof for Yao's Garbling Scheme. in 2023 IEEE 36th Computer Security Foundations Symposium (CSF). Proceedings - IEEE Computer Security Foundations Symposium, IEEE Computer Society, pp. 137-152, 36th IEEE Computer Security Foundations Symposium, CSF 2023, Haifa, Israel, 9/07/23. https://doi.org/10.1109/CSF57540.2023.00009

A State-Separating Proof for Yao's Garbling Scheme. / Brzuska, Chris; Oechsner, Sabine.
2023 IEEE 36th Computer Security Foundations Symposium (CSF). IEEE Computer Society, 2023. p. 137-152 (Proceedings - IEEE Computer Security Foundations Symposium).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A State-Separating Proof for Yao's Garbling Scheme

AU - Brzuska, Chris

AU - Oechsner, Sabine

PY - 2023

Y1 - 2023

N2 - Secure multiparty computation enables mutually distrusting parties to compute a public function of their secret inputs. One of the main approaches for designing MPC protocols are garbled circuits whose core component is usually referred to as a garbling scheme. In this work, we revisit the security of Yao's garbling scheme and provide a modular security proof which composes the security of multiple layer garblings to prove security of the full circuit garbling. We perform our security proof in the style of state-separating proofs (ASIACRYPT 2018).

AB - Secure multiparty computation enables mutually distrusting parties to compute a public function of their secret inputs. One of the main approaches for designing MPC protocols are garbled circuits whose core component is usually referred to as a garbling scheme. In this work, we revisit the security of Yao's garbling scheme and provide a modular security proof which composes the security of multiple layer garblings to prove security of the full circuit garbling. We perform our security proof in the style of state-separating proofs (ASIACRYPT 2018).

UR - https://www.scopus.com/pages/publications/85171987172

UR - https://www.scopus.com/pages/publications/85171987172#tab=citedBy

U2 - 10.1109/CSF57540.2023.00009

DO - 10.1109/CSF57540.2023.00009

M3 - Conference contribution

SN - 9798350321937

T3 - Proceedings - IEEE Computer Security Foundations Symposium

SP - 137

EP - 152

BT - 2023 IEEE 36th Computer Security Foundations Symposium (CSF)

PB - IEEE Computer Society

T2 - 36th IEEE Computer Security Foundations Symposium, CSF 2023

Y2 - 9 July 2023 through 13 July 2023

ER -

A State-Separating Proof for Yao's Garbling Scheme

Abstract

Publication series

Conference

Funding

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this