Daniel Berend

One of the most active fields of research in cryptography is finding efficient homomorphic encryption schemes, particularly information-theoretically secure schemes which are not based on unproven computational hardness assumptions. We suggest here an information-theoretically secure secret sharing scheme based on Shamir’s secret sharing scheme. While Shamir’s scheme supports no homomorphic multiplications of secrets, our scheme efficiently supports one homomorphic multiplication of secrets in addition to homomorphic additions of, practically, any number of such multiplied secrets. We focus on the single-client–multi-server setting. Therefore, our scheme enables a single user to share a database of m records (secrets) among N semi-honest servers with O(m2) ciphertext, using a novel variant of Shamir’s secret sharing scheme and polynomials of degree N-1. Then, our scheme enables homomorphic evaluation of quadratic functions and 2-CNF circuits over the database with no communication between the servers. Our scheme is perfectly secure against attacks of a single server and information-theoretically statistically secure against attacks of coalitions of less than N-1 servers. One of the main advantages of our scheme over known schemes is enabling the evaluation of quadratic functions and 2-CNF secrets over a dynamic database of secrets. A dynamic database of secrets is a database of secrets that can grow in the future with no need for storing and re-sharing existing secrets by the user. To the best of our knowledge, the challenging support for the dynamic property was not obtained in this setting elsewhere before.