面向异步网络的安全分布式随机数通用构造

Randomness plays an extremely important role in the field of cryptography and blockchain, such as the secure generation of protocol parameters for cryptographic schemes, committee reconfiguration in consensus mechanisms, and smart contract applications for electronic voting. However, the generation of randomness in existing applications mostly relies on a trusted third-party. Therefore, in order to improve the transparency of the randomness generation process, the research on distributed randomness generation has received more and more attention in recent years. Existing distributed randomness schemes can be divided into 6 types according to the underlying cryptographic primitives, such as verifiable random function, threshold signature, secret sharing, verifiable delay function and so on. Among them, schemes based on secret sharing are the most, but generally the communication complexity is high, and some schemes with low communication complexity usually sacrifice the bias-resistance and unpredictability. In addition, most of the existing schemes are based on a synchronous network model, which are under strong network assumptions and inconsistent with the real network environment. These limitations make it difficult for the distributed randomness generation to be applied to specific protocols or real applications. This work focuses on the distributed randomness generation technology based on secret sharing. We mainly study on the extraction of the commonalities and compatibility of different schemes, as well as the weakening of network assumptions and the optimization of communication overhead. On the basis of proposing a general structure of distributed randomness, we design and implement a secure distributed randomness generation system for asynchronous networks. Specifically, the main innovations of this paper include the following aspects: (1) We propose a general construction for interactive distributed random beacon. Compared with non-interactive distributed randomness beacon, the general construction proposed in this paper does not rely on a complex distributed key generation protocol. It is composed of secret sharing and consensus, including initialization, node selection, secret sharing, secret recovery, randomness computation, randomness verification, and state update. This construction meets the security goals of pseudo-randomness, uniqueness and robustness. In addition, we analyze an instantiation in this paper, thereby further demonstrating the universality of the construction. (2) We design a secure distributed randomness generation scheme for asynchronous networks. This scheme is mainly oriented to a small-scale permissioned environment. Aiming at the key problem that asynchronous binary agreement cannot be used, asynchronous verifiable secret sharing is used as a sub-module of the scheme, and a voting consensus method is combined on its basis. In addition, this paper presents the formal security proof of the pseudo-randomness, uniqueness and robustness of the scheme. In terms of complexity analysis, this scheme has achieved O(fn²) communication complexity and O(n²) computation complexity and is better than the current asynchronous schemes. (3) We implement the distributed randomness simulation system. This system from bottom to top is the core layer, the network layer, the general layer and the service layer. On this basis, the simulation system has been tested for the computation time and communication overhead under different numbers of nodes. The results show that our scheme has lower communication overhead and the performance is improved, compared with the existing asynchronous schemes, in the case of the same number of nodes. The communication overhead of our scheme is 11% and 47% lower than the existing asynchronous schemes.