TransWikia.com

Why does verifiable secret sharing with an honest majority require a broadcast channel?

Cryptography Asked on November 23, 2021

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

One Answer

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

Answered by Yehuda Lindell on November 23, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP