Which are the current solutions to the illegal values in the homomorphic secret sharing?

Question

There is a usual example about homomorphic secret sharing, focused on e-voting. Supposing we use Shamir's scheme for the Secret Sharing system, a participant generates a polynomial whose a0 is +1 (yes), 0 (abstention), or -1 (no), and then distributes the calculated n points to the tellers. Each teller will calculate the sum of every point, and publish the result. Everyone is able to calculate the resulting polynomial, which is equal to the sum of all the generated polynomials by the voters. The secret revealed then, is the sum of every +1, 0, or -1.

One of the vulnerabilities this system has, is that a malicious player could generate a polynomial with a0 = 7893. If the a0 value is out of the {-1,+1} range, it will corrupt the final outcome. Which are the current solutions to this problem? In other words... How is it possible to ensure that the a0 is between a and b, without revealing its value?

Answer 1

This is a "known vulnerability" of Shamir's secret scheme. While it is known to be information-theoretically secure, here security means privacy. Shamir's scheme has no authenticity properties --- a single party can change the output by modifying a single share.

There have been recent suggestions to augment the notion of "secret sharing" to impart it with a notion of authenticity as well. This can be viewed similarly to how the primitive of "Encryption" (which only gives privacy) was augmented to "Authenticated Encryption" (which gives both privacy and authenticity).

I've seen this proposed in the RealWorldCrypto 2020 talk Adept Secret Sharing, presented by Phil Rogaway (Mihir Bellare and Wei Dai are listed as co-authors/co-contributors though). It seems that there hasn't been a paper/slides made public as a result of the talk though. The talk itself is available here. I don't remember the entirety of the talk, but the conclusion was something along the lines of a generic transformation to get private + authentic secret sharing, but the privacy becomes computational (rather than information theoretic).

This likely does not work for your purposes though --- such a scheme is likely no longer homomorphic (I cannot remember details from the talk currently though). So what do people do in practice? I believe some combination of "standard" Shamir's secret sharing, and a non-interactive zero knowledge (NIZK) proof that $a_0\in (a,b)$. This is called a "Range proof" (see for example this).