Polynomials Whose Secret Shares Multiplication Preserves Degree for 2-CNF Circuits Over a Dynamic Set of Secrets

Daniel Berend; Dor Bitan; Shlomi Dolev

Paper 2019/1192

Polynomials Whose Secret Shares Multiplication Preserves Degree for 2-CNF Circuits Over a Dynamic Set of Secrets

Daniel Berend, Dor Bitan, and Shlomi Dolev

Abstract

One of the most interesting research topics in cryptography is finding efficient homomorphic encryption schemes, preferably information-theoretically secure, which are not based on unproven computational hardness assumptions. The most significant breakthrough in this field was made by Craig Gentry in 2009, and since then, there were various developments. We suggest here an information-theoretically secure secret sharing scheme that efficiently supports one homomorphic multiplication of secrets in addition to homomorphic additions of, practically, any number of such multiplied secrets. In particular, our scheme enables sharing a dynamic set of secrets amongst N participants, using polynomials of degree N-1. Quadratic functions and 2-CNF circuits over the set of secrets can then be homomorphically evaluated, while no information is revealed to any single participant, both before and after the computation. Our scheme is statistically secure against coalitions of less than N-1 participants. One possible application of our scheme is a secure homomorphic evaluation of multi-variate quadratic functions and 2-CNF circuits.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: Secret sharing Information-theoretic security Outsourcing computation
Contact author(s): dorbi @ post bgu ac il
History: 2019-10-15: received
Short URL: https://ia.cr/2019/1192
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1192,
      author = {Daniel Berend and Dor Bitan and Shlomi Dolev},
      title = {Polynomials Whose Secret Shares Multiplication Preserves Degree for 2-CNF Circuits Over a Dynamic Set of Secrets},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1192},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1192}},
      url = {https://eprint.iacr.org/2019/1192}
}