Ring Learning with Errors Based Asynchronous Distributed Random Beacon and its Application in Asynchronous Consensus
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 constructed using the quantum-non-resistant discrete logarithm problem.Therefore,in the context of post-quantum security,existing asynchronous consensus solutions have to rely on local coins with exponential complexity to achieve full-stack quantum security.This paper does further research on public verifiable secret sharing and quantum-resistant security assumptions.The main innovations include the following aspects:(1)A public key update protocol with O(NlogN)prover and verification complexity is designed first,where N is the order of a polynomial.This protocol is based on the quantum-resistant assumption ring learning with errors and the structural paradigm of public verifiable secret sharing,which ensures that the nodes use consistent and correct random seeds in each round of randomness generation.(2)Using the aforementioned public key update protocol,a quantum-resistant asynchronous distributed random beacon protocol based on public verifiable secret sharing is proposed,which ensures that the nodes who use the same random seeds in each round can generate a consistent and secure random beacon.This protocol achieves O(n)computational complexity and O(n2)communication complexity,where n is the node size of the asynchronous network.Under the same security parameter λ=256,our protocol,implemented using Python,saves about 34％execution latency with n=10 compared to the variant protocol based on the discrete logarithm assumption.(3)This paper presents an asynchronous consensus based on the Quadratic-ABA in WaterBear using our asynchronous distributed random beacon protocol and proves it meets the standard security requirements.
distributed random beaconasynchronous networkpost-quantumthreshold cryptographyzero-knowledge proof
万方数据
维普
