Elliptic curves and use of their endomorphism rings in cryptography

Abstract

Eliptik eğriler yüzlerce yıldır çalışılıyor olmasına rağmen eliptik eğri şifrelemesinin(ECC) doğuşu Koblitz'in ve Miller'ın sonlu cisimler üzerinde tanımladıkları eliptik eğrilerde ayrık probleme dayanan çalışmasıyla 1985 de gerçekleşmiştir. Bu tarihten sonra, diğer açık anahtarlı kripto sistemlere göre daha güvenilir bir sistemi daha hızlı ve daha küçük boyutlu anahtarlarla bize sunan ECC ile ilgili birçok çalışma ve ilerleme yaşanmıştır. Örneğin, 160-bit eliptik eğri anahtarıyla sağlanan güvenlik ancak 1024-bit RSA anahtarıyla sağlanabilmektedir. Bu süre zarfında, daha etkili ve çok daha hızlı hesaplamalar yapabilen kuantum bilgisayarları geliştirilmiştir. Eliptik eğri kriptosistemleri dahil yaygın olarak kullanılan açık anahtarlı kriptosistemler kuantum bilgisayarlar ile savunmasız hale gelmişlerdir ve bu da açık anahtarlı kriptosistemlerin yakın gelecekte kırılmasına ya da ciddi bir şekilde zarar görmesi anlamına gelmektedir. Bu nedenle kuantum sonrası dünya için kuantum algoritmalarına dayanıklı açık anahtarlı sistemler tasarlanmalıdır. Bu dünyada bazı özellikleri ile birlikte eliptik eğriler popülerliğini kaybetmezler. Bu çalışmada, biz eliptik eğrilerin matematiksel temellerini ve PQC için temel kavram olan eliptik eğrilerdeki izojenileri çalışacağız.

Although elliptic curves have been studied for hundreds of years, the inception of elliptic curve cryptography is 1985 by Koblitz's and Miller's independent proposals that is based on the discrete logarithm problem on an elliptic curve defined over a finite field. After that date, there are a lot of advances and studies in elliptic curve cryptography(ECC) which provide high security with relatively small block sizes and high speed compared to the other public key cryptosystems. For instance, 160-bit elliptic curve key provides the same level of security as a 1024-bit RSA key. Meantime, quantum computers, which provide efficient and very fast parallel computation, are developed. In the near feature, widely used public key cryptosystems, including ECC, are vulnerable to quantum algorithms which means not only ECC but also almost all public key cryptosystems will be dead or seriously wounded in the near future. Therefore, efficient public key systems should be designed for post-quantum world. In this world, elliptic curves with some properties do not lose their popularity. In this work, we shall study the mathematical backgrounds of elliptic curves and isogenies on elliptic curves which are the essential concept in post-quantum cryptography(PQC).