Security of algebraic curves in cryptography

点击翻译按钮获取中文摘要

Elliptic curve cryptography (ECC) and generalizations such as hyperelliptic curve cryptography represent the most efficiently implementable public key cryptosystems available today for a given level of security. All other public key cryptosystems, such as RSA (Rivest-Shamir-Adleman) either admit subexponential time attacks or have not been subjected to the same level of scrutiny for a sufficiently long period of time to warrant confidence in their security. For this reason, ECC has been widely adopted in international standards as the preferred cryptosystem for security sensitive or resource constrained environments. A notable application of ECC is in the area of security for mobile phones, where lower computational power often precludes the use of less efficient alternatives. Although ECC is widely believed to be secure, the exact level of security provided by elliptic curves remains an open question. Unlike traditional cryptosystems such as RSA, where all systems of a given parameter size are equally secure, it is not known whether elliptic curves of the same size provide equal security. The choice of curve is highly relevant in practice because different curves can lead to different performance profiles or feature sets. For example, Koblitz curves have faster implementations compared to other curves, and pairing-friendly curves enable the use of cryptographic protocols that require pairings. Uncertainty regarding the security of such curves has led to the development of conflicting recommendations within international standards documents. Some documents recommend the use of pairing-friendly curves based on their increased feature set, while others forbid the use of pairing-friendly curves, citing security concerns. My research aims to answer the question of whether elliptic curve security varies depending on the choice of curve, by computing explicit algebraic security reductions between the various possible choices of curves. In addition, this research is expected to produce (and has produced in the past) new elliptic-curve based cryptosystems, faster implementations, and new attacks and cryptanalysis of ECC-based protocols.