I'm working on a secret sharing scheme and facing a challenge in detecting cheaters among the shareholders. Here's the setup:

  • There's a decoder $D$, a set of $2T$ shareholders, and a combiner/detective $C$.
  • Within the set of shareholders, there are $T$ known cheaters.
  • The combiner can provide the decoder with any secret message $m$ and instruct the decoder to distribute shares $(x_i, f(x_i))$ to the shareholders. The function $f(x)$ is defined as $f(x) = m + \sum_{t=1}^{T-1} a_t x^t \mod 2^n$, where $a_t$ are integers randomly chosen from the range $[0, 2^n[$ and $x_i$ are randomly chosen as well.
  • After sharing, the combiner can request the shares back from the shareholders. Honest shareholders will return the correct share, but cheaters will provide the correct $x_i$ with a random $y_i$.

Given this scenario, I'm looking for strategies or algorithms that the detective can use to reliably identify the cheaters. The detective can send as many messages as needed to the decoder for this purpose.

Key questions:

  • What approaches can be employed to detect cheaters in this scenario?
  • Are there specific cryptographic techniques or algorithms that are effective in this setting?
  • What are the limitations or challenges in detecting cheaters in such a system?

Any insights or suggestions on how to approach this problem would be greatly appreciated.

  • $\begingroup$ You can try using a Reed—Solomon decoding algorithm, perhaps some can incorporate the knowledge of $m$. $\endgroup$ Commented Dec 28, 2023 at 6:58
  • $\begingroup$ If you must use the ring $\mathbb Z_{2^n}$ instead of the field $\mathbb F_{2^n}$ as secret-sharing schemes usually do, then all bets are off: secret-sharing schemes over rings have many flaws that make them unusable in practice. If you are wiling to use a field (not necessarily $\mathbb F_{2^n}$; any large enough finite field will do), then @CommandMaster's comment is right on target. See this answer re the necessity of using a field and this one for how RS coding can identify cheaters. $\endgroup$ Commented Dec 30, 2023 at 0:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.