3
$\begingroup$

In the information-theoretic model with active adversaries, it seems to be well-known that no protocols with exact reconstruction of the secret exist for the task of verifiable secret sharing (VSS) when $t \geq n/3$. However, one can lift the number of tolerable cheaters by allowing for a small error probability during reconstruction to up to $t < n/2$ cheaters. For such protocols, broadcast channels are assumed to be available (in addition to secure, authenticated communication channels) and it seems to be a well-known result that without this assumption, even this weaker form of VSS is impossible (see e.g. the abstract of the paper linked below).

My question is, why is the assumption of a broadcast channel necessary? To me it seems that a possible reasoning might be that (1) broadcast channel is equivalent to Byzantine agreement, (2) Byzantine agreement is impossible for $n/3 \leq t$ and (3) VSS implies a broadcast channel, hence broadcast needs to be assumed for VSS when $n/3 \leq t < n/2$.

https://web.cs.ucla.edu/~rafail/PUBLIC/145.pdf

$\endgroup$

1 Answer 1

2
$\begingroup$

By definition, VSS implies broadcast. As such, with $t\geq n/3$, it is not possible to achieve VSS (by the bounds on Byzantine Agreement).

$\endgroup$
1
  • $\begingroup$ By the bounds on robust secret sharing, VSS that is secure against $t \geq n/3$ active cheaters must allow for some small error probability during reconstruction. A Byzantine Agreement protocol constructed from such a VSS protocol would thus also have some small error probability. Is such a small error probability also excluded by the bounds on Byzantine Agreement? If so, where can I read more about this impossibility? $\endgroup$
    – jgerrit
    Commented Aug 17, 2020 at 9:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.