基于环上容错学习的异步分布式随机信标及其在异步共识中的应用  

Ring Learning with Errors Based Asynchronous Distributed Random Beacon and its Application in Asynchronous Consensus

作　　者：张宗洋 李天宇 胡斌 周游 周星光 ZHANG Zong-Yang;LI Tian-Yu;HU Bin;ZHOU You;ZHOU Xing-Guang(School of Cyber Science and Technology,Beihang University,Beijing 100191;Department of Big Data and Artificial Intelligence,Civil Aviation Management Institute of China,Beijing 100102)

机构地区：[1]北京航空航天大学网络空间安全学院,北京100191 [2]中国民航管理干部学院大数据与人工智能系,北京100102

出　　处：《计算机学报》2024年第8期1813-1831,共19页Chinese Journal of Computers

基　　金：国家重点研发计划(2022YFB2702702);国家自然科学基金面上项目(62372020,61972017,72031007);北京市自然科学基金(M22038,L222050);中央高校基本科研业务费(YWF-23-L-1032);中国民航管理干部学院青年教师科研启动基金(23QN06)资助。

摘　　要：安全高效的异步分布式随机信标是异步共识协议能够快速终止的必要保障.2008年以来,比特币中区块链技术的成功促进了分布式应用的蓬勃发展,为分布式应用提供随机性来源的分布式随机信标也受到了学者的广泛研究.现有的分布式随机信标一般选取公开可验证秘密共享、可验证随机函数、可验证延迟函数之一作为基础结构进行设计,其中公开可验证秘密共享结构简单、模块清晰、实用性较强,是现有分布式随机信标协议中数量最多、分析最为透彻的类别,其它结构的协议研究开始时间较晚,设计方法并未固定,在形式化安全定义和安全分析中尚有较大空白等待填补.目前,只有少数基于公开可验证秘密共享的方案支持异步网络模型,并且这些方案都是利用不抗量子的离散对数问题构建的.因此,在后量子安全的异步网络模型下,现有异步共识成果不得不采用期望运行轮数为指数的本地抛币协议来保障全栈量子安全.本文主要研究抗量子安全假设下基于公开可验证秘密共享的方案,具体贡献如下:(1)本文首先基于抗量子困难假设环上容错学习和公开可验证秘密共享的结构范式,设计了具备O(N log N)证明及验证复杂度的公钥更新协议,其中N为多项式次数,该协议保证了节点在每一轮产生随机数份额的过程中采用了一致且正确的新公钥.(2)在此基础上,本文设计了计算复杂度为O(n),通信复杂度为O(n2)的异步分布式随机信标协议,其中n为节点规模.在相同的安全参数下,本文提出的随机信标协议相较于基于离散对数的协议运行时延减小约34%.(3)最后,本文给出了一种基于异步分布式随机信标的异步共识协议,并证明其满足标准的安全需求.A secure and efficient asynchronous distributed random beacon is necessary to guarantee the termination of asynchronous consensus.Since 2008,the success of blockchain technology in Bitcoin has promoted the vigorous development of distributed applications,and distributed random beacons that provide a source of randomness for distributed applications have also been widely studied by scholars.Although several distributed random beacons have been proposed,the development of quantum computing necessitates reevaluating the security assumptions underlying existing schemes.In the field of cryptography,it is possible to quickly calculate the order of any element in a multiplication group using quantum Fourier transform,and then efficiently solve mathematical difficulties such as large integer factorization or discrete logarithm.Once quantum computers with a sufficient number of qubits become available,most protocols constructed based on these assumptions will be vulnerable to attacks.Consequently,international standardization organizations,headed by NIST,have initiated quantum-resistant cryptography protocol evaluations,recommending example instances for widely used protocols like public key encapsulations and digital signatures.However,the distributed random beacon protocols and asynchronous consensus have yet to be included in the evaluation scope.Most existing distributed random beacons can be divided into protocols based on public verifiable secret sharing,protocols based on verifiable random function,and protocols based on verifiable delay function.The public verifiable secret sharing model has a simple structure,clear modules,and strong practicality,making it the most numerous and thoroughly analyzed category among existing distributed random beacon protocols,the other structures started relatively late,and the design methods as well as the formal security definitions and analysis were not fixed.At present,only a few public verifiable secret sharing based schemes support asynchronous networks,and these schemes are c

关 键 词：分布式随机信标 异步网络 量子安全 门限密码 零知识证明 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]