Explore Shamir secret sharing (was "Multiple protocol runs and/or threshold secret sharing") #22
Labels
parking-lot
Parking lot for future discussions
Comments
|
This will be interesting :) |
|
#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. |
Merged
cjpatton
changed the title
|
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). |
cjpatton
added a commit
to cfrg/draft-irtf-cfrg-vdaf
that referenced
this issue
Oct 31, 2024
Demonstration of the composition of FLP with Shamir's secret sharing. This could be the basis of a Prio3 variant that tolerates drop out of an Aggregator. Imagine a DAP setup [1] where a Leader wants to be able to run the protocol with one of two Helpers so that if the first Helper goes offline, it can continue the computation with the other. For this to work, the Client still needs to know the identities of the two Helpers prior to generating its report. [1] ietf-wg-ppm/draft-ietf-ppm-dap#22
cjpatton
added a commit
to cfrg/draft-irtf-cfrg-vdaf
that referenced
this issue
Oct 31, 2024
A demonstration of the composition of FLP with Shamir's secret sharing. This could be the basis of a Prio3 variant that tolerates drop out of an Aggregator. Imagine a DAP setup [1] where a Leader wants to be able to run the protocol with one of two Helpers so that if the first Helper goes offline, it can continue the computation with the other. For this to work, the Client still needs to know the identities of the two Helpers prior to generating its report. [1] ietf-wg-ppm/draft-ietf-ppm-dap#22
|
Said variant of Prio3: cfrg/draft-irtf-cfrg-vdaf#520 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
The text was updated successfully, but these errors were encountered: