后量子公钥密码中关键数学问题研讨

The rapid development of quantum computing technology has seriously threatened the public key cryptography based on integer factoring and elliptic curve discrete logarithm, which is widely used at present. It is generally accepted in the industry that public key cryptography based on lattice, coding, multivariable and elliptic curve isogeny can resist quantum attack, also known as post quantum public key cryptography.. This project mainly studies the design and analysis of a new public key cryptosystem based on lattice and coding theory. With the help of algebraic number theory and coding theory, we put forward the difficult problems on modular lattices, and gives the new LWE-like and SIS-like difficult problems which can be reduced to hard problem on modular lattices, so as to design a new post quantum public key scheme and give the cryptanalysis of NIST candidates entering the second round. Scholars at home and abroad will be invited to attend our workshops so as to discuss problems, learn from each other and solve these difficult problems.

量子计算技术的快速发展严重威胁了目前广泛在用的基于大整数分解、椭圆曲线离散对数的公钥密码，业界普遍认同基于格、纠错码、多变量和椭圆曲线同源等的公钥密码能抵抗量子攻击，因此这类公钥密码也称为后量子公钥密码。. 本课题主要研究基于格和纠错码的后量子公钥密码的设计和分析，借助代数数论和编码理论，提出模格上的困难问题，给出与之归约的新的推广的Learning With Errors (简称LWE-like)和推广的Short Integer Solution(简称SIS-like)困难问题，从而设计出新的后量子公钥方案，对进入第二轮的NIST征集方案给出密码分析。主要形式是邀请国内外的后量子密码和代数数论、编码理论等科研方向的学者共同讨论问题，互相学习，攻克科研难关。

量子计算机的快速发展严重威胁了目前广泛在用的经典公钥密码，本项目围绕目前热点的基于格和纠错码的后量子公钥密码中的关键数学问题展开研究。我们2021年1月成立了两个以优秀中青年为骨干的研究小组集中开展定期的科研活动，其中一个小组基于纠错码的抗量子公钥密码，由于疫情，我们在11月27日-28日还组织了线上高级研讨班，邀请了国内十几名优秀的编码密码方向的专家进行研讨；另一个小组以基于格理论的密码问题组织了讨论， 由于疫情原因，原本想组织线下的高级研讨班一直推迟，打算放在2022年开展。. 本项目的一个研究内容是基于纠错码构造了一个新的可追踪的环签名方案。环签名允许群组中的用户代表群组对消息进行签名，可追踪的环签名方案在电子投票、数字加密货币中某些应用场景中，它可以追踪到在同一个群体中对消息进行多次签名的不诚实的用户，同时保护诚实用户的隐私。然而目前并没有基于编码的可证安全的TRS方案，. 我们构造的基于编码的新的可跟踪的环签名方案是对2019年Branco和Mateus方案的改进，我们的方案依赖的是校验子译码困难问题和2-正则零校验子译码困难问题，我们的方案在随机预言机模型下是安全的，即满足标签链接性、匿名性和防陷害性。. 本项目的另一个研究内容是构造了基于可证明安全NTRU的门限同态加密方案。据我们所知，该方案是首个NTRU型的ThHE方案。在享有NTRU方案简单、快速的优点的同时，还具有没有昂贵的重线性化过程、抵抗子域格攻击、分布式门限解密的优点。. 该研究工作在多参与方的隐私计算方面具有良好的学术价值和应用价值。例如在多方安全计算的场景中，一组互不信任的参与者各自利用上述门限同态加密方案生成的公钥对私有数据进行加密。对密文的同态运算可以由任意一位参与方执行，或者直接将计算委托给云服务器。由于任何一方无法接触到公钥所对应的私钥，保障了整个计算过程中的私有数据机密性。