Faster point addition formulas for Huff form of elliptic curves

Abstract

Onceden yalnızca matematiksel amaclar icin kullanılan eliptik e˘griler, 1985yılında Miller ve Koblitz'in yayınladıgı ayrı calısmalar sayesinde kripto dunyasınagiris yaptı. Bu gelisme ile birlikte eliptik egriler kriptografinin en onemliaraclarından biri haline geldi. 1990'lardan sonra eliptik e˘gri tabanlı kriptografiticari amaclar icin kullanılmaya ba¸sladı. Eliptik egri tabanlı kripto-sistemler,RSA gibi sıkca kullanılan asimetrik kripto sistemlerin sagladıgı guvenlikseviyesini, daha kısa anahtarlar ile saglayabildigi icin, bu denli hızlı bir gelisimgosterdi. Fakat, sagladıgı yuksek seviyeli guvenlige karsın, verimlilik konusundayol kat etmesi gerekmektedir. Bu nedenle, eliptik egri tabanlı kripto-sistemlerinverimliligini arttırmak uzere bir cok calı¸sma yapılıyor.Hız ama¸clı kullanılan e˘gri modelleri, eliptik egri tabanlı kriptografinin temeli¸slemi olan, skalar ¸carpım i¸slemi i¸cin kullanılacak, daha d¨u¸s¨uk dereceli form¨ullerelde edilmesi konusunda b¨uy¨uk yol kat etti. Fakat, bu egri modellerindensayılan Huff egrisi bu vakte kadar yapılan bir cok calısmaya ragmen, twistedEdwards, Jacobi Quartic gibi egrilerle rekabet icinde olmadı. Bu tezinamacı, matemtaiksel ve bilgisayımsal temelleri kullanarak Huff e˘gri modelininverimliligini arttırmaktır.Bu amac cercevesinde,y(1 + ax2 ) = cx(1 + dy2).olarak ifade edilen Huff egrisi uzerinde, bolmesiz nokta toplama ve nokta ciftlemeislemleri onerildi. Bu amaca ulasmak icin kullanılan ilk yontem, bolmesiz noktatoplama ve nokta ¸ciftleme i¸slemleri elde edebilmek i¸cin, bu egri modelinde dahaonceki calısmalarda tercih edilenden baska bir projektif uzay kullanılmasıdır.Ikinci yontem ise, alternatif bir nokta ciftleme formulu elde etmek icinisogenilerden faydalanmaktır. Bu iki y¨ontem sayesinde, dikkate de˘ger bir geli¸simkaydedilmistir.Huff egrisi ¨uzerinde, bilinen en hızlı nokta ciftleme formulu ile, islem 6M +5S'de 2 hesaplanabiliyordu. Bu tezde sunulan alternatif nokta ciftleme formulusayesinde 8M'de hesaplanabiliyor. Nokta toplama formulunun i¸slem sayısı da10M'den 8M'ye dusuruldu. Bu iki formulde de 2M'lik hızlanma sa˘glanmı¸stır.Ayrıca sunulan her iki formul de 4-yonlu paralel olarak islenebilmektedir.Anahtar Kelimeler: Eliptik e˘griler, 2-isogeny, verimli, skalar çarpım, Huffeğrisi, ters almasız nokta toplama işlemi, paralel hesaplama.

Elliptic curves were being used only for mathematical studies until Miller andKoblitz introduced elliptic curves to crypto-community in 1985 with independentworks. Since then, elliptic curves became one of the most significant toolsin cryptography. Elliptic curve cryptography (ECC) started to be used forcommercial purposes after 1990's. It provides a better level of security withthe same key size than the widely used public key crypto-systems such as RSA.Nevertheless, time complexity is not at the desired stage. Hence, there have beenseveral studies so far that aims to increase the time efficiency.The curve forms that are being used for speed oriented operations came along way in terms of gathering lower degree formulas for scalar multiplicationwhich is the core operation of ECC. However, one of the curve forms which iscalled Huff curve could not get competitive with the other forms such as TwistedEdwards, Jacobi Quartic, despite the studies have been made so far. This thesisfocuses on increasing the efficiency of Huff form of elliptic curve by making useof mathematical and computational primitives.Inversion-free point addition and doubling formulas which are being used inscalar multiplication algorithms, are proposed for the Huff curve which is defined y(1 + ax2 ) = cx(1 + dy2 ) First idea is rather to embed the curve into a different projective space thanthe preferred for Huff curve previously. Thus, P 1×P 1 embedding is used instead of P 2embedding. The second idea is to make the use of isogenies in order to obtainan alternative doubling formula. Thanks to these two ideas, an improvement isachieved.The best algorithm for point doubling on Huff curve was computed with 6M+5S.1 The proposed doubling formula in this thesis can be computed with 8M.Also, operation count of mixed addition is decreased from 10M to 8M. Both setsof formulas are leading to an effective cost of 2M. Furthermore, they are shownto be 4-way parallel.Key Words: Elliptic curves, 2-isogeny, efficient, scalar multiplication, Huffcurves, inversion-free point addition, parallel computation.