Paper 2024/820

Rate-1 Arithmetic Garbling from Homomorphic Secret-Sharing

Abstract

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 $$-bounded integer arithmetic using only two ciphertexts per multiplication. The total bit-size of the resulting garbled circuit is: $$ where $$ is the number of inputs, $$ is the number of multiplications, $$ is the multiplicative depth of the circuit, $$ is an RSA modulus and $$ is a rough bound 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-$$. The total bit-size of the resulting garbled circuit is: $$ where the parameters are as above, except $$ is the magnitude bound. As a side result, we show that our scheme based on IND-CPA security achieves rate $$ for levelled circuits.