Homomorphic Secret Sharing (HSS) is a form of multi-party computation (MPC) that works over secret shares. To understand the basis of HSS, you only need to know three things!
Secret Shares: A secret sharing scheme is a method to split up information (the secret) into multiple parts with two conditions. Firstly, no individual part shall reveal the secret. Secondly, combining enough parts together shall reconstruct the secret. The most famous secret sharing algorithm is Shamir’s secret sharing which works over polynomials. Consider a polynomial of degree t-1 that is uniquely defined by t points. If we let the y-intercept be our secret value, then we can give each party a point on the polynomial. With t points, we can calculate the polynomial and hence compute the ‘secret’.
Multi-Party Computation: MPC is a distributed form of computation where multiple parties work together to compute on secret data. No other party should learn what the other parties input, however they can learn the output. For example, with our earlier Shamir secret sharing scheme, we could easily compute the sum of two different shares, as the degree of the polynomial does not change. Where we run into issues are when we start multiplying values, as that does raise the degree of the resultant polynomial.
Homomorphic properties: In group theory, a homomorphism is a structure-preserving map between two groups. An intuitive way to understand this is with the log function. Hopefully you remember the product rule of logarithms, where the log of A plus the log of B is equivalent to the log of A times B. We can view this relationship as a type of homomorphism that maps strictly positive real number under multiplication to real numbers under addition.
Bringing all these concepts together takes us to HSS. In short, we can exploit homomorphic properties of common cryptographic primitives to reduce the degree of polynomials (i.e. from multiplication back to addition) in order to have MPC via secret shares for a complex class of programs. If you would like to read more, send me an e-mail and I would be happy to share the full paper.