Explore Shamir secret sharing (was "Multiple protocol runs and/or threshold secret sharing")

[tgeoghegan]

Prio v2 employs a linear secret sharing scheme in which all input shares are required in order to produce coherent outputs. This gives us robustness against malicious clients, but not malicious servers (robustness per section 2 of the 2017 paper).

We could provide robustness against a minority of malicious servers by running the protocol over multiple subsets of aggregators. If the outputs across all aggregator subsets do not agree, then participants know that there is at least one malicious server.

If linear secret sharing is employed, then clients would have to generate input shares once for each subset. We could also use a threshold secret sharing scheme (e.g., Shamir), which would reduce work for clients.

[cjpatton]

This will be interesting :)

[cjpatton]

43 partially addresses this issue by deciding that multiple helpers will be used for resilience. Whether we can use Shamir secret sharing to provide robustness against cheating servers is still an open question. Though IMO we shouldn't try to change the spec to allow for this.

[cjpatton]

This issue predates the VDAF abstraction and no longer applies (directly) to DAP. However, it's an interesting consideration for a future variant of Prio3 (or other VDAF).