Rate-1 Arithmetic Garbling From Homomorphic Secret Sharing
Published in TCC 2024, 2024
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,~\emph{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_\times+2D_\times)\cdot (\zeta + 1) \cdot \log N$, where $n$ is the number of inputs, $s_\times$ is the number of multiplications, $D_\times$ is the multiplicative depth of the circuit, $N$ is an RSA modulus and $N^{\zeta-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_\times + 1) \cdot (\zeta + 1) \cdot \log N$, where the parameters are as above, except $N^{\zeta-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.