TY - GEN
T1 - New Ways to Garble Arithmetic Circuits
AU - Ball, Marshall
AU - Li, Hanjun
AU - Lin, Huijia
AU - Liu, Tianren
N1 - Publisher Copyright:
© 2023, International Association for Cryptologic Research.
PY - 2023
Y1 - 2023
N2 - The beautiful work of Applebaum, Ishai, and Kushilevitz [FOCS’11] initiated the study of arithmetic variants of Yao’s garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit C: Rn→ Rm over a ring R into a garbled circuit C^ and n affine functions Li for i∈ [ n], such that C^ and Li(xi) reveals only the output C(x) and no other information of x. AIK presented the first arithmetic garbling scheme supporting computation over integers from a bounded (possibly exponentially large) range, based on Learning With Errors (LWE). In contrast, converting C into a Boolean circuit and applying Yao’s garbled circuit treats the inputs as bit strings instead of ring elements, and hence is not “arithmetic”. In this work, we present new ways to garble arithmetic circuits, which improve the state-of-the-art on efficiency, modularity, and functionality. To measure efficiency, we define the rate of a garbling scheme as the maximal ratio between the bit-length of the garbled circuit | C^ | and that of the computation tableau | C| ℓ in the clear, where ℓ is the bit length of wire values (e.g., Yao’s garbled circuit has rate O(λ) ). We present the first constant-rate arithmetic garbled circuit for computation over large integers based on the Decisional Composite Residuosity (DCR) assumption, significantly improving the efficiency of the schemes of Applebaum, Ishai, and Kushilevitz.We construct an arithmetic garbling scheme for modular computation over R= Zp for any integer modulus p, based on either DCR or LWE. The DCR-based instantiation achieves rate O(λ) for large p. Furthermore, our construction is modular and makes black-box use of the underlying ring and a simple key extension gadget.We describe a variant of the first scheme supporting arithmetic circuits over bounded integers that are augmented with Boolean computation (e.g., truncation of an integer value, and comparison between two values), while keeping the constant rate when garbling the arithmetic part. To the best of our knowledge, constant-rate (Boolean or arithmetic) garbling was only achieved before using the powerful primitive of indistinguishability obfuscation, or for restricted circuits with small depth.
AB - The beautiful work of Applebaum, Ishai, and Kushilevitz [FOCS’11] initiated the study of arithmetic variants of Yao’s garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit C: Rn→ Rm over a ring R into a garbled circuit C^ and n affine functions Li for i∈ [ n], such that C^ and Li(xi) reveals only the output C(x) and no other information of x. AIK presented the first arithmetic garbling scheme supporting computation over integers from a bounded (possibly exponentially large) range, based on Learning With Errors (LWE). In contrast, converting C into a Boolean circuit and applying Yao’s garbled circuit treats the inputs as bit strings instead of ring elements, and hence is not “arithmetic”. In this work, we present new ways to garble arithmetic circuits, which improve the state-of-the-art on efficiency, modularity, and functionality. To measure efficiency, we define the rate of a garbling scheme as the maximal ratio between the bit-length of the garbled circuit | C^ | and that of the computation tableau | C| ℓ in the clear, where ℓ is the bit length of wire values (e.g., Yao’s garbled circuit has rate O(λ) ). We present the first constant-rate arithmetic garbled circuit for computation over large integers based on the Decisional Composite Residuosity (DCR) assumption, significantly improving the efficiency of the schemes of Applebaum, Ishai, and Kushilevitz.We construct an arithmetic garbling scheme for modular computation over R= Zp for any integer modulus p, based on either DCR or LWE. The DCR-based instantiation achieves rate O(λ) for large p. Furthermore, our construction is modular and makes black-box use of the underlying ring and a simple key extension gadget.We describe a variant of the first scheme supporting arithmetic circuits over bounded integers that are augmented with Boolean computation (e.g., truncation of an integer value, and comparison between two values), while keeping the constant rate when garbling the arithmetic part. To the best of our knowledge, constant-rate (Boolean or arithmetic) garbling was only achieved before using the powerful primitive of indistinguishability obfuscation, or for restricted circuits with small depth.
UR - http://www.scopus.com/inward/record.url?scp=85161660682&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85161660682&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-30617-4_1
DO - 10.1007/978-3-031-30617-4_1
M3 - Conference contribution
AN - SCOPUS:85161660682
SN - 9783031306167
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 34
BT - Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2023, Proceedings
A2 - Hazay, Carmit
A2 - Stam, Martijn
PB - Springer Science and Business Media Deutschland GmbH
T2 - 42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023
Y2 - 23 April 2023 through 27 April 2023
ER -