Rate-1 Arithmetic Garbling From Homomorphic Secret Sharing

TY - GEN

T1 - Rate-1 Arithmetic Garbling From Homomorphic Secret Sharing

AU - Meyer, Pierre

AU - Orlandi, Claudio

AU - Roy, Lawrence

AU - Scholl, Peter

PY - 2025

Y1 - 2025

N2 - We present a new approach to garbling arithmetic circuits using techniques from homomorphic secret sharing, obtaining constructions with high rate that support free addition gates. In particular, we build upon non-interactive protocols for computing distributed discrete logarithms in groups with an easy discrete-log subgroup, further demonstrating the versatility of tools from homomorphic secret sharing. Relying on distributed discrete log for the Damgård-Jurik cryptosystem (Roy and Singh, Crypto ‘21), whose security follows from the decisional composite residuosity assumption (DCR), we get the following main results: Two ciphertexts per multiplication, from IND-CPA security of Damgård-Jurik. Assuming the Damgård-Jurik cryptosystem is semantically secure (which follows from DCR), there is a garbling scheme for circuits with B-bounded integer arithmetic using only two ciphertexts per multiplication. The total bit-size of the resulting garbled circuit is: (n+2s×+2D×)·(ζ+1)·logN where n is the number of inputs, s× is the number of multiplications, D× is the multiplicative depth of the circuit, N is an RSA modulus and Nζ-1 is roughly the bound B on the magnitude of wire values in the computation.One ciphertext per multiplication, from KDM security of Damgård-Jurik. Assuming the Damgård-Jurik encryption scheme remains secure given encryption of the key and its inverse, the construction achieves rate-1. The total bit-size of the resulting garbled circuit is: (n+s×+1)·(ζ+1)·logN where the parameters are as above, except Nζ-2 is the magnitude bound. Two ciphertexts per multiplication, from IND-CPA security of Damgård-Jurik. Assuming the Damgård-Jurik cryptosystem is semantically secure (which follows from DCR), there is a garbling scheme for circuits with B-bounded integer arithmetic using only two ciphertexts per multiplication. The total bit-size of the resulting garbled circuit is: (n+2s×+2D×)·(ζ+1)·logN where n is the number of inputs, s× is the number of multiplications, D× is the multiplicative depth of the circuit, N is an RSA modulus and Nζ-1 is roughly the bound B on the magnitude of wire values in the computation. One ciphertext per multiplication, from KDM security of Damgård-Jurik. Assuming the Damgård-Jurik encryption scheme remains secure given encryption of the key and its inverse, the construction achieves rate-1. The total bit-size of the resulting garbled circuit is: (n+s×+1)·(ζ+1)·logN where the parameters are as above, except Nζ-2 is the magnitude bound. As a side result, we show that our scheme based on IND-CPA security achieves rate 3/5 for levelled circuits.

AB - We present a new approach to garbling arithmetic circuits using techniques from homomorphic secret sharing, obtaining constructions with high rate that support free addition gates. In particular, we build upon non-interactive protocols for computing distributed discrete logarithms in groups with an easy discrete-log subgroup, further demonstrating the versatility of tools from homomorphic secret sharing. Relying on distributed discrete log for the Damgård-Jurik cryptosystem (Roy and Singh, Crypto ‘21), whose security follows from the decisional composite residuosity assumption (DCR), we get the following main results: Two ciphertexts per multiplication, from IND-CPA security of Damgård-Jurik. Assuming the Damgård-Jurik cryptosystem is semantically secure (which follows from DCR), there is a garbling scheme for circuits with B-bounded integer arithmetic using only two ciphertexts per multiplication. The total bit-size of the resulting garbled circuit is: (n+2s×+2D×)·(ζ+1)·logN where n is the number of inputs, s× is the number of multiplications, D× is the multiplicative depth of the circuit, N is an RSA modulus and Nζ-1 is roughly the bound B on the magnitude of wire values in the computation.One ciphertext per multiplication, from KDM security of Damgård-Jurik. Assuming the Damgård-Jurik encryption scheme remains secure given encryption of the key and its inverse, the construction achieves rate-1. The total bit-size of the resulting garbled circuit is: (n+s×+1)·(ζ+1)·logN where the parameters are as above, except Nζ-2 is the magnitude bound. Two ciphertexts per multiplication, from IND-CPA security of Damgård-Jurik. Assuming the Damgård-Jurik cryptosystem is semantically secure (which follows from DCR), there is a garbling scheme for circuits with B-bounded integer arithmetic using only two ciphertexts per multiplication. The total bit-size of the resulting garbled circuit is: (n+2s×+2D×)·(ζ+1)·logN where n is the number of inputs, s× is the number of multiplications, D× is the multiplicative depth of the circuit, N is an RSA modulus and Nζ-1 is roughly the bound B on the magnitude of wire values in the computation. One ciphertext per multiplication, from KDM security of Damgård-Jurik. Assuming the Damgård-Jurik encryption scheme remains secure given encryption of the key and its inverse, the construction achieves rate-1. The total bit-size of the resulting garbled circuit is: (n+s×+1)·(ζ+1)·logN where the parameters are as above, except Nζ-2 is the magnitude bound. As a side result, we show that our scheme based on IND-CPA security achieves rate 3/5 for levelled circuits.

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

U2 - 10.1007/978-3-031-78023-3_3

DO - 10.1007/978-3-031-78023-3_3

M3 - Article in proceedings

SN - 978-3-031-78023-3

T3 - Lecture Notes in Computer Science

SP - 71

EP - 97

BT - Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings

A2 - Boyle, Elette

A2 - Mahmoody, Mohammad

PB - Springer Nature

CY - Cham

ER -