CryptoDB
Rate1 Arithmetic Garbling From Homomorphic Secret Sharing
Authors: 


Download:  
Conference:  TCC 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 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: 1) [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 Bbounded 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. 2) [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 rate1. 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. 
BibTeX
@inproceedings{tcc202434770, title={Rate1 Arithmetic Garbling From Homomorphic Secret Sharing}, publisher={SpringerVerlag}, author={Pierre Meyer and Claudio Orlandi and Lawrence Roy and Peter Scholl}, year=2024 }