Search

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. [ABSTRACT FROM AUTHOR]

In this paper we present the Multidimensional Byzantine Agreement (MBA) Protocol, a leaderless Byzantine agreement protocol defined for complete and synchronous networks that allows a network of nodes to reach consensus on a vector of relevant information regarding a set of observed events. The consensus process is carried out in parallel on each component, and the output is a vector whose components are either values with wide agreement in the network (even if no individual node agrees on every value) or a special value ⊥ that signals irreconcilable disagreement. The MBA Protocol is probabilistic and its execution halts with probability 1, and the number of steps necessary to halt follows a Bernoulli-like distribution. The design combines a Multidimensional Graded Consensus and a Multidimensional Binary Byzantine Agreement, the generalization to the multidimensional case of two protocols presented by Micali et al. (SIAM J Comput 26(4):873–933, 1997; Byzantine agreement, made trivial, 2016). We prove the correctness and security of the protocol assuming a synchronous network where less than a third of the nodes are malicious. [ABSTRACT FROM AUTHOR]

We present an EdDSA-compatible multi-party digital signature scheme that supports an offline participant during the key-generation phase, without relying on a trusted third party. Under standard assumptions, we prove our scheme secure against adaptive malicious adversaries. 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 original EdDSA scheme with non-negligible probability. The scheme requires only two communication rounds in the signature generation phase and avoids expensive multi-party evaluation of cryptographic hash functions. We present our solution in a setting where two parties generate the keys and compute signatures, with a third party which can be brought online after the key generation when one of the other parties becomes unavailable. This setting is a perfect fit for custodial solutions where partially trusted services are employed by a user to increase resiliency. We provide also a possible solution to retain the resiliency of the recovery in the presence of a malicious party. [ABSTRACT FROM AUTHOR]

The maximum likelihood decoding problem (MLD) is known to be NP-hard and its complexity is strictly related to the security of some post-quantum cryptosystems, that is, the so-called code-based primitives. Analogously, the multivariate quadratic system problem (MQ) is NP-hard and its complexity is necessary for the security of the so-called multivariate-based primitives. In this paper we present a closed formula for a polynomial-time reduction from any instance of MLD to an instance of MQ, and viceversa. We also show a polynomial-time isomorphism between MQ and MLD, thus demonstrating the direct link between the two post-quantum cryptographic families. [ABSTRACT FROM AUTHOR]

Blockchain-based platforms utilise cryptographic protocols to enforce the correct behaviour of users, as well as to guarantee a sufficient level of protection against malicious adversaries. Cryptography is, however, an ever-evolving discipline, and any breakthrough would have immediate consequences on the security of blockchain-based applications. A possible threat currently under investigation is given by the development of quantum computers, since several wide-adopted cryptographic protocols have been proved to be unsafe against quantum-capable adversaries. In this work, we propose a novel approach for the management of cryptographic primitives in smart-contract-based ledgers, discussing how it fits in both a (partially) permissioned and a fully permissionless setting. The cryptographic protocols are managed in a flexible manner via a set of smart-contracts defined on the ledger itself, in this way the choice of algorithms and parameters can change quickly. Among the advantages of this approach, we remark how it allows designing an adaptive post-quantum-based blockchain that keeps up with ongoing technological advances. In general, the introduction of new features and the application of fixes to a blockchain cause forks in the chain, which may cause major disruptions. The use of smart contracts in blockchain management allows to avoid this problem, dynamically introducing new protocols or deprecating old ones without compromising previous data. The Cryptographic Kernel approach has been adopted by Quadrans, an open-source, public, decentralised smart-contract-based blockchain with a specific focus on the needs of industry, complex supply chains, and IOT devices. [ABSTRACT FROM AUTHOR]

A (t, n)-threshold signature scheme enables distributed signing among n players such that any subset of size at least t can sign, whereas any subset with fewer players cannot. Our goal is to produce digital signatures that are compatible with an existing centralized signature scheme: the key-generation and signature algorithms are replaced by a communication protocol between the players, but the verification algorithm remains identical to that of a signature issued using the centralized algorithm. Starting from the threshold scheme for the ECDSA signature due to Gennaro and Goldfeder, we present the first protocol that supports multiparty signatures with an offline participant during the key-generation phase and that does not rely on a trusted third party. Under standard assumptions on the underlying algebraic and geometric problems (e.g. the Discrete Logarithm Problem for an elliptic curve and the computation of e th root on semi-prime residue rings), we prove our scheme secure against adaptive malicious adversaries. [ABSTRACT FROM AUTHOR]