基于编码问题的密码理论研究

In 1994 Peter Shor showed that quantum computers could break any public-key cryptosystem based on these hard number theory problems. This means that if a reasonably powerful quantum computer could be built, it would put essentially all modern communication into peril. It is predicted that within the next 10 to 20 years quantum computers will be built that are sufficiently powerful to implement Shor's ideas and to break all existing public key schemes. Thus we need to look ahead to a future of quantum computers, and we need to prepare the cryptographic world for that future.. Post-quantum cryptography is a new fast developing area, where public key cryptosystems are studied that could resist these emerging attacks. Currently there are four families of public-key cryptosystems that have the potential to resist quantum computers: the code-based public-key cryptosystems, the hash-based public-key cryptosystems,the latticebased public-key cryptosystems and the multivariate public-key cryptosystems..Our study focus on the code based cryptosystems. We will propose the class of quasi-dyadic Goppa codes, which admit a very compact parity-check or a generator matrix representation,for efficiently instantiating syndrome-based cryptosystems.we will also give a new general way to reduce the public key size through quasi-cyclic codes. Additionally, we will show how to construct t-error correcting quasi-dyadic codes where the density of decodable syndromes is high, while also allowing for a reduction by a factor up to t in the key size, which yields dense binary Goppa codes as needed for practical instantiation of CFS signatures. Finally, we will study code-based threshold ring signature scheme that achieves small signature size and give a security proof of our scheme whose security relies - in both random oracle and ideal cipher models - on two coding theory problems, making our scheme the first provably secure code-based threshold ring signature scheme.

Peter Shor于1994年指出量子计算机能够攻破传统的公钥密码技术（如 RSA、DSA、ECDSA等），这意味着一旦量子计算机出现，当前使用的传统公钥密码算法将全部失去作用。因此人们需要寻找新的公钥密码算法以便在量子计算机时代替代传统密码算法，抵抗量子计算攻击（这种密码技术被称为后-量子密码）。后量子密码是近年来快速发展的研究领域之一，目前有四种密码体制被认为能够抵抗量子计算机攻击：基于编码问题的密码体制、基于HASH 的密码体制、基于格问题的密码体制、基于多变量问题的密码体制。本课题将研究基于编码问题的公钥密码体制，主要内容包括：具有紧性表示的基于准-Coppa码的的公钥加密算法、具有紧性表示的基于准-循环码的公钥加密算法、基于准-二元LDPC码的公钥加密算法、具有紧性密钥表示的基于准-二元 Coppa码的、高效的数字签名算法、具有紧密钥表示、高效率、短签名长度的环签名或门限签名。

Shor算法和Grover算法等量子攻击算法对当前广泛使用的公钥密码体制（RSA、DSA、ECDSA等）造成了严重的威胁，量子计算机时代必须寻求安全性更高的公钥密码体制。基于编码的公钥密码体制是目前被广泛承认的能够抵抗量子攻击的后量子密码体制之一，具有很高的安全性。本课题主要研究基于编码的公钥密码体制，具体研究内容包括：具有紧密钥表示的基于准循环Goppa码和二元LDPC码的公钥加密算法；具有紧密钥表示的高效数字签名算法；具有紧密钥表示的高效安全的特殊数字签名算法。.针对以上研究内容，经过四年不懈的努力，项目组取得了一系列的研究成果，主要包括：1）设计了一种LDPC码的生成算法PWG，该算法具有较低的计算复杂度，且生成的LDPC码的码率接近于LDPC码的理论最高码率；同时利用该算法生成的LDPC码设计了具有更高实现效率的公钥加密算法。2）以经典的基于编码的数字签名算法和基于编码的hash函数为基础，设计了一种具有高密度可解校验子的数字签名算法，大大提高了基于编码的数字签名算法的运算效率，同时极大降低了公钥表示长度。3）在经典的基于编码的CFS数字签名算法的基础上设计了一种基于编码的盲签名算法，给出了算法的安全模型和详细的性能分析，该算法具有较高的盲化安全性，且签名长度较低。4）设计了一系列两方和三方的安全量子密钥协商协议，可以抵御已知的大部分攻击；设计了基于编码hash同态性的数据持有性证明方案，同时给出了一般性数据共享方案，进一步提出了无界的在线/离线多中心属性基加密，提高了云环境下的数据安全；设计了大规模环境下的群组认证与密钥协商协议，对现有的安全标准进行了增强和完善。.这些研究成果不仅在理论上对已有的公钥加密和数字签名算法进行了较为重要的改进，同时还丰富了基于编码的公钥密码算法的研究内容和研究领域，开拓了基于编码的公钥密码算法的应用场合，为后量子密码的科研与实践奠定了坚实的基础。