Efficient Arithmetic in Garbled Circuits

David Heath

doi:10.1007/978-3-031-58740-5_1

Efficient Arithmetic in Garbled Circuits

David Heath

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from strong assumptions, such as LWE. We construct symmetric-key-based arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let λ denote a security parameter, and consider the integers Z_m for any m≥2. Let ℓ=log₂m be the bit length of Z_m values. We garble arithmetic circuits over Z_m where the garbling of each gate has size O(ℓ·λ) bits. Contrast this with Boolean-circuit-based arithmetic, requiring O(ℓ²·λ) bits via the schoolbook multiplication algorithm, or O(ℓ^1.585·λ) bits via Karatsuba’s algorithm. Our arithmetic gates are compatible with Boolean operations and with Garbled RAM, allowing to garble complex programs of arithmetic values.

Original language	English (US)
Title of host publication	Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings
Editors	Marc Joye, Gregor Leander
Publisher	Springer
Pages	3-31
Number of pages	29
ISBN (Print)	9783031587399
DOIs	https://doi.org/10.1007/978-3-031-58740-5_1
State	Published - 2024
Event	43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024 - Zurich, Switzerland Duration: May 26 2024 → May 30 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14655 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024
Country/Territory	Switzerland
City	Zurich
Period	5/26/24 → 5/30/24

Keywords

Arithmetic Circuits
Garbled Circuits

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-031-58740-5_1

Library availability

Discover UIUC Full Text

Cite this

Heath, D. (2024). Efficient Arithmetic in Garbled Circuits. In M. Joye, & G. Leander (Eds.), Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings (pp. 3-31). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14655 LNCS). Springer. https://doi.org/10.1007/978-3-031-58740-5_1

Efficient Arithmetic in Garbled Circuits. / Heath, David.
Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings. ed. / Marc Joye; Gregor Leander. Springer, 2024. p. 3-31 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14655 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Heath, D 2024, Efficient Arithmetic in Garbled Circuits. in M Joye & G Leander (eds), Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14655 LNCS, Springer, pp. 3-31, 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024, Zurich, Switzerland, 5/26/24. https://doi.org/10.1007/978-3-031-58740-5_1

Heath D. Efficient Arithmetic in Garbled Circuits. In Joye M, Leander G, editors, Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings. Springer. 2024. p. 3-31. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-58740-5_1

Heath, David. / Efficient Arithmetic in Garbled Circuits. Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings. editor / Marc Joye ; Gregor Leander. Springer, 2024. pp. 3-31 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{eefa518d8e9c4129b7ba64de6d662098,

title = "Efficient Arithmetic in Garbled Circuits",

abstract = "Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from strong assumptions, such as LWE. We construct symmetric-key-based arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let λ denote a security parameter, and consider the integers Zm for any m≥2. Let ℓ=log2m be the bit length of Zm values. We garble arithmetic circuits over Zm where the garbling of each gate has size O(ℓ·λ) bits. Contrast this with Boolean-circuit-based arithmetic, requiring O(ℓ2·λ) bits via the schoolbook multiplication algorithm, or O(ℓ1.585·λ) bits via Karatsuba{\textquoteright}s algorithm. Our arithmetic gates are compatible with Boolean operations and with Garbled RAM, allowing to garble complex programs of arithmetic values.",

keywords = "Arithmetic Circuits, Garbled Circuits",

author = "David Heath",

note = "This research was developed with funding from NSF grant CNS-2246353, and from USDA APHIS, under opportunity number USDA-APHIS-10025-VSSP0000-23-0003.; 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024 ; Conference date: 26-05-2024 Through 30-05-2024",

year = "2024",

doi = "10.1007/978-3-031-58740-5_1",

language = "English (US)",

isbn = "9783031587399",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "3--31",

editor = "Marc Joye and Gregor Leander",

booktitle = "Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Efficient Arithmetic in Garbled Circuits

AU - Heath, David

N1 - This research was developed with funding from NSF grant CNS-2246353, and from USDA APHIS, under opportunity number USDA-APHIS-10025-VSSP0000-23-0003.

PY - 2024

Y1 - 2024

N2 - Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from strong assumptions, such as LWE. We construct symmetric-key-based arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let λ denote a security parameter, and consider the integers Zm for any m≥2. Let ℓ=log2m be the bit length of Zm values. We garble arithmetic circuits over Zm where the garbling of each gate has size O(ℓ·λ) bits. Contrast this with Boolean-circuit-based arithmetic, requiring O(ℓ2·λ) bits via the schoolbook multiplication algorithm, or O(ℓ1.585·λ) bits via Karatsuba’s algorithm. Our arithmetic gates are compatible with Boolean operations and with Garbled RAM, allowing to garble complex programs of arithmetic values.

AB - Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from strong assumptions, such as LWE. We construct symmetric-key-based arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let λ denote a security parameter, and consider the integers Zm for any m≥2. Let ℓ=log2m be the bit length of Zm values. We garble arithmetic circuits over Zm where the garbling of each gate has size O(ℓ·λ) bits. Contrast this with Boolean-circuit-based arithmetic, requiring O(ℓ2·λ) bits via the schoolbook multiplication algorithm, or O(ℓ1.585·λ) bits via Karatsuba’s algorithm. Our arithmetic gates are compatible with Boolean operations and with Garbled RAM, allowing to garble complex programs of arithmetic values.

KW - Arithmetic Circuits

KW - Garbled Circuits

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

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

U2 - 10.1007/978-3-031-58740-5_1

DO - 10.1007/978-3-031-58740-5_1

M3 - Conference contribution

AN - SCOPUS:85193616787

SN - 9783031587399

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 31

BT - Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings

A2 - Joye, Marc

A2 - Leander, Gregor

PB - Springer

T2 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024

Y2 - 26 May 2024 through 30 May 2024

ER -