PKC-Sec: Security Analysis of Classical and Post-Quantum Public Key Cryptography Assumptions

公钥密码学(PKC)依赖于计算问题的存在，这些问题非常难以解决，但并非不可能解决。20世纪70年代PKC起源的基础(实际上在几个世纪前就很突出)的经典例子是整数因式分解问题和离散对数问题(DLP)。由于Shor在1994年提出的惊人的突破性想法，目前还没有已知的高效算法，即在经典计算机上运行的多项式时间算法来解决这些问题，但这两种算法都可以在足够大的量子计算机上高效地解决。随后在量子计算、量子信息理论和量子算法领域进行了密集的研究，在过去大约15年的时间里，人们认真地研究了替代的后量子(PQ)密码系统，NIST和ETSI都在进行标准化努力。PQ密码系统必须对经典计算机和量子计算机都是安全的，因此在完全信任它们来取代我们现有的PKC硬度假设之前，必须仔细研究它们潜在的硬度假设。在这些标准建立和密码学实践完全迁移到PQ密码学之前，继续研究经典硬度假设也是至关重要的，特别是零星的，有时甚至是惊人的进展：例如，对于一个特殊但很大的有限域族，由于Granger博士和他的合作者以及Joux和他的合作者的一系列结果，DLP可以在经典计算机上以准多项式时间高效地求解。在这个项目中，我们将研究和开发算法来解决对PKC现在和未来的安全至关重要的计算问题。特别是，我们将研究：前述特殊有限域族中的DLP，对于该族，一个有效的经典算法即将出现；Legendre伪随机函数的安全性，它非常适合多方计算，已被建议用于下一代以太-事实上的标准区块链平台-但还没有得到很好的研究；最后，基于超奇异同源的PQ密码的安全性，它虽然是一个相对年轻的领域，但提供了许多非常有希望的应用。由于它们的性质，任何基于数学构造的密码学假设都可能比目前认为的更弱，我们将加深我们的理解并评估这些自然和基本问题的难度，从而为密码学社区以及更广泛地说所有密码学用户提供安全保证。

Public key cryptography (PKC) depends on the existence of computational problems that are incredibly hard - but not impossible - to solve. Classical examples that were fundamental to the origins of PKC in the 1970s (and indeed were prominent centuries earlier) are the integer factorisation problem and the discrete logarithm problem (DLP). While there are no known efficient, i.e., polynomial-time algorithms for solving these problems that run on classical computers, thanks to Shor's astounding breakthrough ideas in 1994, both can be solved efficiently on a quantum computer of sufficient size. Intense research in the areas of quantum computation, quantum information theory and quantum algorithms ensued, and replacement post-quantum (PQ) cryptosystems have been studied in earnest for the past 15 years or so, with standardisation efforts in process by both NIST and ETSI. PQ cryptosystems must be secure against both classical and quantum computers and therefore their underlying hardness assumptions must be studied intensely before they can be fully trusted to replace our existing PKC hardness assumptions. Until these standards have been established and cryptographic practice migrates entirely to PQ cryptography, it is also essential that the study of classical hardness assumptions persists, particularly as sporadic and sometimes spectacular progress can occur: for instance, for a special but large family of finite fields the DLP can be solved on a classical computer in quasi-polynomial time, i.e., `very nearly' efficiently, thanks to a series of results due to Dr. Granger and his collaborators, and Joux and his collaborators.In this project we will research and develop algorithms for solving computational problems that are foundational to the security of PKC, both now and in the future. In particular, we will study: the DLP in the aforementioned special family of finite fields, for which an efficient classical algorithm is potentially on the horizon; the security of the Legendre pseudo-random function, which is extremely well suited for multi-party computation and has been proposed for use in the next iteration of Ethereum - the de facto standard blockchain platform - but is not so well-studied; and finally the security of supersingular isogeny-based PQ cryptography, which although a relatively young field offers many very promising applications. Due to their nature, any cryptographic assumptions based on mathematical constructions are potentially weaker than currently believed, and we will deepen our understanding and assess the hardness of these natural and fundamental problems, thus providing security assurances to the cryptography community and more generally all users of cryptography.