Abstract Starting from links between Coding Theory and Secret Sharing Schemes, we develop an extensible and decentralized version of Shamir Secret Sharing, that allows the addition of new users after the initial share distribution. On top of it we design a totally decentralized ( t , n )-threshold Schnorr signature scheme that needs only t users online during the key generation phase, while the others join later. Under standard assumptions we prove our scheme secure against adaptive malicious adversaries. Furthermore, we show how our security notion can be strengthened when considering a rushing adversary. Using a classical game-based argument, we prove that if there is an adversary capable of forging the scheme with non-negligible probability, then we can build a forger for the centralized Schnorr scheme with non-negligible probability.

Abstract In this paper we extend the Multidimensional Byzantine Agreement (MBA) Protocol, a leaderless Byzantine agreement for lists of arbitrary values, into a protocol suitable for wide gossiping networks: Cob. This generalization allows the consensus process to be run by an incomplete network of nodes provided with (non-synchronized) same-speed clocks. Not all nodes are active in every step, so the network size does not hamper the efficiency, as long as the gossiping broadcast delivers the messages to every node in reasonable time. These network assumptions model more closely real-life communication channels, so Cob may be applicable to a variety of practical problems, such as blockchain platforms implementing sharding. Cob has the same Bernoulli-like distribution that upper-bounds the number of steps as the MBA protocol. We prove its correctness and security assuming a supermajority of honest nodes in the network, and compare its performance with Algorand.