Design & Cryptanalysis of Isogeny-Based Post-Quantum Cryptosystems

后量子密码学关注的是在拥有足够大的量子计算机的情况下保护信息不受攻击者的攻击，这是目前许多广泛使用的协议无法做到的。这类计算机目前只存在于理论上，然而量子计算的前景趋势，加上现代社会对安全通信的依赖，推动了创造量子抵抗的密码系统的动力。在这一领域，基于同源的密码学是一种在过去十年中引起许多研究兴趣的方法，所提出的方案似乎能够抵抗量子计算攻击，并且需要相对较少的带宽。基于同源的协议通常依赖于在给定其端点的情况下找到未知函数(同源)的相对困难，而不是评估已知函数。最近，在前一个效率问题上取得了进展，增加了这些协议的吸引力。后一种安全问题被认为仍然是困难的，尽管这仍然是高度投机性的。一般情况下，后量子协议不太可能得到广泛使用，因为它们的安全性还没有完全被理解。考虑到它们的相对新颖性，基于同源的方案当然就是这种情况。事实上，最著名的SIDH/SIKE协议只有十年左右的历史，在过去的三年里提出了大量新的方案。相比之下，NIST后量子标准化过程中的一些算法可以追溯到70年代的S。该项目旨在提高对基于同源的密码系统的安全性的理解，从而提高希望实现这些协议的人的信心。事实上，只有通过更好地理解安全性，标准化才能开始，因为这个过程需要具体的参数。广泛地说，当前对同源方案的最佳攻击利用了一般的组合结构，几乎不依赖于实际底层椭圆曲线的丰富的代数和几何性质。这从表面上看似乎很了不起，可能会增强人们对这些协议的安全性的信心。另一方面，这可能再次是这一研究领域相对年轻的一个症状，再加上无法获得可能打破这些计划所需的数论工具。除了研究生水平的数学之外，像四元数代数这样的对象很少被研究，但它是描述基于同源的协议的基础。从密码学和计算的角度重新解释这些经典对象将是更好地评估安全论证的关键。此外，不确定性围绕着量子安全目标的定义缺乏清晰度。当前的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.