超奇异同源密码的计算理论研究

由于量子计算机的潜在威力，研究抗量子计算的密码算法成为当前的一个研究关注点。目前能抗量子计算的密码主要来源于代数和数论中的问题，典型的代表是那些来源于格、超奇异椭圆曲线同源、一般线性码译码以及多变量方程组等方面的问题。因超奇异同源密码算法在空间开销、通信开销都较比较小，它们得到越来越多的重视。然而，这类密码算法目前还存在计算时间开销较大的缺点，限制了它的应用。本项目研究与此相关的超奇异椭圆曲线的自同态环、四元数代数的极大序、以及超奇异曲线构成的Ramanujan图之间的对应关系计算，这些计算问题既与超奇异同源密码的强度紧密相关，又对同源密码的实现效率产生重要影响。我们进而分析相关问题求解的传统算法实现及量子计算复杂性，并设计一批安全、高效的密码算法和协议。本项目源于世界科技前沿的热点、难点和新兴领域，具有引领性和开创性。

Due to the potential power of the quantum computers, the research of anti-quantum computing cryptosystem has become a research focus. At present, the cryptosystems that can resist quantum computation mainly come from algebra and number theory,and the typical representatives are the problems from lattice, isogeny of supersingular elliptic curve, general linear code decoding and multivariable equations. Because the space and communication cost of supersigular isogeny based cryptography are relatively small, they get more and more attention. However, at present, this kind of cryptosystem has the disadvantage of large computation time cost, which limits its application. In this project, we study the correspondence calculations among the endmomorphim rings of supersingular elliptic curves, the maximum orders of the quaternion algebra, and the Ramanujan graphs composed of supersingular elliptic curves. These computation problems are closely related to the strength of supersingular isogeny based crypsystems and also have an important impact on the efficiency of these ciphers. Then we analyze the complexities for these problems both for electronic computing and quantum computing, and design a batch of secure and efficient cryptographic algorithms and protocols. This project is originated from the hot, hard spots and emerging fields of the global science and technology frontier, and it is leading and pioneering.