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


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Secret sharingInformation-theoretic securityOutsourcing computation
Contact author(s)
dorbi @ post bgu ac il
2019-10-15: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.