Welcome to the resource topic for 2024/820
Title:
Rate-1 Arithmetic Garbling from Homomorphic Secret-Sharing
Authors: Pierre Meyer, Claudio Orlandi, Lawrence Roy, Peter Scholl
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 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 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-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.
ePrint: https://eprint.iacr.org/2024/820
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .