Paper 2024/820
Rate1 Arithmetic Garbling from Homomorphic SecretSharing
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 noninteractive protocols for computing distributed discrete logarithms in groups with an easy discretelog subgroup, further demonstrating the versatility of tools from homomorphic secret sharing. Relying on distributed discrete log for the DamgårdJurik 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 INDCPA security of DamgårdJurik.**] Assuming the DamgårdJurik 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 bitsize 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^{\zeta1}$ is a rough bound on the magnitude of wire values in the computation. [**One ciphertext per multiplication, from KDM security of DamgårdJurik.**] Assuming the DamgårdJurik encryption scheme remains secure given encryption of the key and its inverse, the construction achieves rate$1$. The total bitsize of the resulting garbled circuit is: $$(n + s_\times + 1) \cdot (\zeta + 1) \cdot \log N$$ where the parameters are as above, except $N^{\zeta2}$ is the magnitude bound. As a side result, we show that our scheme based on INDCPA security achieves rate $3/5$ for levelled circuits.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Keywords
 Arithmetic Garbled CircuitHomomorphic Secret SharingDCRDamgårdJurik cryptosystem
 Contact author(s)

pierre meyer @ cs au dk
orlandi @ cs au dk
ldr709 @ gmail com
peter scholl @ cs au dk  History
 20240527: approved
 20240526: received
 See all versions
 Short URL
 https://ia.cr/2024/820
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/820, author = {Pierre Meyer and Claudio Orlandi and Lawrence Roy and Peter Scholl}, title = {Rate1 Arithmetic Garbling from Homomorphic SecretSharing}, howpublished = {Cryptology ePrint Archive, Paper 2024/820}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/820}}, url = {https://eprint.iacr.org/2024/820} }