Design & Cryptanalysis of Isogeny-Based Post-Quantum Cryptosystems

后量子密码学关注的是保护信息免受拥有足够大的量子计算机的对手的攻击，这是许多目前广泛使用的协议无法做到的。这种计算机目前只存在于理论中，然而量子计算的发展趋势，加上现代社会对安全通信的依赖，推动了创建量子抵抗的密码系统的动力。在这个领域，基于同源性的密码学是一种在过去十年中引起广泛研究兴趣的方法，提出的方案似乎可以抵抗量子计算攻击，以及需要相对较小的带宽。基于同源性的方案通常依赖于在给定其终点的情况下找到未知功能（同源性）与评估已知功能的比较困难。最近，在前效率问题上取得了进展，增加了这些协议的吸引力。后一个安全问题仍然被认为是困难的，尽管这仍然是高度推测性的。一般来说，后量子协议不太可能得到广泛的使用，而它们的安全性还没有被完全理解。对于基于同源性的方案来说，这当然是一种情况，因为它们相对新奇。事实上，最著名的协议SIDH/SIKE只有大约十年的历史，在过去的3年中提出了新的方案。相比之下，NIST后量子标准化过程中的一些算法可以追溯到70年代。该项目旨在提高对同源密码系统安全性的理解，从而提高那些希望实现这些协议的人的信心。事实上，只有通过更好地理解安全性，标准化才能开始，因为这一过程需要具体的参数。广义上说，目前最好的攻击iscrystal计划利用一般的组合结构，很少依赖于丰富的代数和几何性质的实际基础椭圆曲线。这在表面上看起来很了不起，可能会对这些协议的安全性产生信心。另一方面，这可能又是这个研究领域相对年轻的一个症状，再加上无法获得可能打破这些计划所需的数论工具。像四元数代数这样的对象在研究生水平的数学之外几乎没有研究，但在描述基于同源性的协议中是基本的。从密码学和计算的角度重新解释这些经典对象将是更好地评估安全论点的关键。进一步的不确定性围绕着量子安全目标的定义缺乏清晰度。目前的NIST定义依赖于与经典安全概念的模糊比较，几乎没有理由。这在一定程度上还没有得到解决，因为后量子密码学的许多替代方法都具有优于量子密码学的经典攻击。这是不是一些同源性为基础的计划的情况下，因此，这些定义的有效性已受到质疑。需要进一步开展工作，就适当的量子成本指标达成共识，并确定适当的工具，将这些指标与传统成本进行比较。评估计划，就这些新的指标，然后将需要在具体的安全索赔可以作出。这个项目属于福尔斯的EPSRC数学科学研究领域。

Post-quantum cryptography is concerned with securing information against adversaries in the possession of a sufficiently large quantum computer, something which many current protocols in widespread use fail to do. Such computers currently only exist in theory, however promising trends in quantum computing, combined with modern society's dependence on secure communication, have fuelled the drive to create cryptographic systems which are quantum resistant.Within this area, isogeny-based cryptography is an approach that has garnered much research interest in the past decade, proposed schemes appear to resist quantum computing attacks, as well as requiring comparatively little bandwidth. Isogeny based protocols typically rely on the comparative difficulty of finding an unknown function (an isogeny) given its endpoints, vs evaluating a known function. Recently, advances have been made in the former efficiency problem, increasing the appeal of these protocols. The latter security problem is still believed to be difficult, though this is still highly speculative.Post-quantum protocols in general are unlikely to gain widespread use whilst their security is not fully understood. This is certainly the case for isogeny-based schemes, given their relative novelty. Indeed, the most prominent protocol SIDH/SIKE is only around a decade old, with an explosion of newer schemes proposed in the past 3 years. As a comparison, some algorithms in NIST's post-quantum standardisation process date back to the 70's. This project aims to improve understanding of the security of isogeny-based cryptosystems and thus improve confidence in those wishing to implement these protocols. Indeed, it is only through a better understanding of security that standardisation can begin, as this process requires concrete parameters.Broadly, the best current attacks on isogeny schemes exploit general combinatorial structures, relying very little on the rich algebraic and geometric properties of the actual underlying elliptic curves. This seems remarkable on the surface and may install confidence in the security of these protocols. On the other hand, this may again be a symptom of the relative youth of this field of research, combined with the inaccessibility of the number theoretic tools required to possibly break these schemes. Objects such as quaternion algebras see little study outside of graduate level mathematics yet are fundamental in describing isogeny-based protocols. Reinterpreting these classical objects from a cryptographic and computational perspective will be key in better evaluating security arguments.Further uncertainties revolve around the lack of clarity around the definition of quantum security goals. Current NIST definitions rely on a somewhat vague comparison with classical security notions, with little justification. This partly has not been addressed as many alternative approaches to post quantum cryptography have classical attacks that outperform their quantum counterparts. This is not the case for some isogeny-based schemes and as such, the validity of these definitions has been brought into question. Further work is required to build consensus on appropriate quantum cost metrics and define appropriate tools to compare these to classical costs. Assessing schemes with respect to these new metrics will then be required before concrete security claims can be made.This project falls within the EPSRC Mathematical Sciences research area.