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

A General Construction of Secure Distributed Randomness Generation for Asynchronous Networks

随机数在密码学和区块链领域扮演着极其重要的角色,如密码学中的安全参数生成、共识机制中的委员会重配置以及电子投票的智能合约应用等.近年来针对不依赖可信第三方的分布式随机数生成技术的研究受到了越来越多的关注,其中基于秘密共享的方案数量最多,但普遍通信复杂度较高,而通信复杂度较低的一些方案通常牺牲了随机数的抗偏置性和不可预测性.另外,现有大多数方案基于同步网络模型,网络假设较强,与现实网络环境不符.本文主要研究基于秘密共享的分布式随机数生成技术,抽象出不同方案的共性并兼容特殊性,以及弱化网络假设和优化通信开销.具体贡献如下:(1)提出了交互的分布式随机数生成通用构造.满足伪随机性、唯一性和鲁棒性安全目标,并使用该通用构造对一个分布式随机数生成方案进行了分析,从而更加证明其通用性;(2)设计了面向异步网络的安全分布式随机数生成方案.将现有方案O(n^(3))和O(f^(2)n^(2))的通信复杂度降为O(fn^(2)),将O(fn^(2))计算复杂度降为O(n^(2));(3)实现了分布式随机数仿真系统.针对不同节点数进行了性能测试,测试结果表明,相同节点数下,本方案比现有异步方案的通信开销更低,性能有所提升.最好情况下本方案比现有异步方案在通信开销方面分别降低了11%和47%.

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^(2))communication complexity and O(n^(2))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.