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

PKC-Sec：经典和后量子公钥密码学假设的安全性分析

• 批准号: EP/W021633/1
• 负责人: Robert Granger
• 金额: $ 37.96万
• 依托单位: University of Surrey
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FW021633%2F1
• 关键词: PKC; Sec; Security; Analysis; Classical

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.

公共密钥密码学（PKC）取决于是否存在难以解决的计算问题，但难以解决。对1970年代PKC起源至关重要的经典示例（实际上是较重要的几个世纪）是整数分解问题和离散对数问题（DLP）。尽管没有已知的有效效率，即用于解决这些在古典计算机上运行的问题的多项式时间算法，这要归功于Shor在1994年的惊人突破性想法，但两者都可以在足够大小的量子计算机上有效地解决。在过去的15年左右的时间里，认真研究了在量子计算，量子信息理论和量子算法领域进行的激烈研究，并认真研究了量子后（PQ）加密系统的替代研究，NIST和ETSI都在进行了标准化的工作。 PQ密码系统必须确保与经典计算机和量子计算机相抵触，因此必须对其基本硬度假设进行深入研究，然后才能完全信任它们以取代我们现有的PKC硬度假设。在建立这些标准并完全迁移到PQ密码学之前，对经典硬度假设的研究仍然至关重要，尤其是随着零星且有时壮观的进展，可能会发生：例如，对于一个特殊但大型有限领域的家庭， DLP可以在准多项式时间的古典计算机上解决，即，由于Granger博士及其合作者以及Joux及其合作者的一系列结果，我们将研究有效地“非常”。并开发算法来解决现在和将来的PKC安全基础的计算问题。特别是，我们将研究：上述特殊领域的DLP，为此，有效的经典算法有可能即将到来； Legendre Pseudo-random功能的安全性非常适合多方计算，并已被提议用于以太坊的下一次迭代 - 事实上的标准区块链平台 - 但并不是那么经过深入研究；最后，基于超级同学的PQ密码学的安全性，尽管一个相对年轻的领域提供了许多非常有前途的应用。由于其性质，基于数学结构的任何加密假设可能比目前所相信的要弱，我们将加深我们的理解和评估这些自然和基本问题的硬度，从而为密码学社区以及更普遍的所有用户提供安全保证密码学。

项目成果

Three proofs of an observation on irreducible polynomials over GF(2)

GF(2) 上不可约多项式观测值的三个证明

• DOI: 10.1016/j.ffa.2023.102192
• 发表时间: 2023
• 期刊: Finite Fields and Their Applications
• 影响因子: 1
• 作者: Granger R