Browsing by Author "Hisil, Huseyin"

Now showing 1 - 11 of 11

Citation - Scopus: 86
A simple and compact algorithm for sidh with arbitrary degree isogenies
(Springer Verlag service@springer.de, 2017) Craig Costello; Hüseyin Hişil; Costello, Craig; Hisil, Huseyin; T. Takagi , T. Peyrin
We derive a new formula for computing arbitrary odd-degree isogenies between elliptic curves in Montgomery form. The formula lends itself to a simple and compact algorithm that can efficiently compute any low odd-degree isogenies inside the supersingular isogeny Diffie-Hellman (SIDH) key exchange protocol. Our implementation of this algorithm shows that beyond the commonly used 3-isogenies there is a moderate degradation in relative performance of (2d+ 1) -isogenies as d grows but that larger values of d can now be used in practical SIDH implementations. We further show that the proposed algorithm can be used to both compute isogenies of curves and evaluate isogenies at points unifying the two main types of functions needed for isogeny-based public-key cryptography. Together these results open the door for practical SIDH on a much wider class of curves and allow for simplified SIDH implementations that only need to call one general-purpose function inside the fundamental computation of the large degree secret isogenies. As an additional contribution we also give new explicit formulas for 3- and 4-isogenies and show that these give immediate speedups when substituted into pre-existing SIDH libraries. © 2017 Elsevier B.V. All rights reserved.
Complete group law for genus 2 Jacobians on Jacobian coordinates
(Springer Science and Business Media Deutschland GmbH, 2024) Elif Ozbay Gurler; Hüseyin Hişil; Ozbay Gurler, Elif; Hisil, Huseyin; Gurler, Elif Ozbay
This manuscript provides complete inversion-free and explicit group law formulas in Jacobian coordinates for the genus 2 hyperelliptic curves of the form y2=x5+a3x3+a2x2+a1x+a0 over a field K with char(K)≠2. The formulas do not require the use of polynomial arithmetic operations such as resultant mod or gcd computations but only operations in K. © 2024 Elsevier B.V. All rights reserved.
Citation - WoS: 2
Citation - Scopus: 3
d-MUL: Optimizing and Implementing a Multidimensional Scalar Multiplication Algorithm over Elliptic Curves
(SPRINGER INTERNATIONAL PUBLISHING AG, 2018) Huseyin Hisil; Aaron Hutchinson; Koray Karabina; Karabina, Koray; Hisil, Huseyin; Hutchinson, Aaron; A Chattopadhyay; C Rebeiro; Y Yarom
This paper aims to answer whether d-MUL the multidimensional scalar point multiplication algorithm can be implemented efficiently. d-MUL is known to access costly matrix operations and requires memory access frequently. In the first part of the paper we derive several theoretical results on the structure and the construction of the addition chains in d-MUL. These results are interesting on their own right. In the second part of the paper we exploit our theoretical results and propose an optimized variant of d-MUL. Our implementation results show that d-MUL can be very practical for small d and it remains as an interesting algorithm to further explore for parallel implementation and cryptographic applications.
Citation - WoS: 9
Citation - Scopus: 10
Fast Cryptography in Genus 2
(SPRINGER, 2016) Joppe W. Bos; Craig Costello; Huseyin Hisil; Kristin Lauter; Bos, Joppe W.; Lauter, Kristin; Costello, Craig; Hisil, Huseyin
In this paper we highlight the benefits of using genus 2 curves in public-key cryptography. Compared to the standardized genus 1 curves or elliptic curves arithmetic on genus 2 curves is typically more involved but allows us to work with moduli of half the size. We give a taxonomy of the best known techniques to realize genus 2-based cryptography which includes fast formulas on the Kummer surface and efficient four-dimensional GLV decompositions. By studying different modular arithmetic approaches on these curves we present a range of genus 2 implementations. On a single core of an Intel Core i7-3520M (Ivy Bridge) our implementation on the Kummer surface breaks the 125 thousand cycle barrier which sets a new software speed record at the 128-bit security level for constant-time scalar multiplications compared to all previous genus 1 and genus 2 implementations.
Citation - WoS: 51
Citation - Scopus: 57
Fast cryptography in genus 2
(Springer-Verlag Berlin, 2013) Joppe W. Bos; Craig Costello; Hüseyin Hişil; Kristin Estella Lauter; Bos, Joppe W.; Lauter, Kristin; Costello, Craig; Hisil, Huseyin
In this paper we highlight the benefits of using genus 2 curves in public-key cryptography. Compared to the standardized genus 1 curves or elliptic curves arithmetic on genus 2 curves is typically more involved but allows us to work with moduli of half the size. We give a taxonomy of the best known techniques to realize genus 2 based cryptography which includes fast formulas on the Kummer surface and efficient 4-dimensional GLV decompositions. By studying different modular arithmetic approaches on these curves we present a range of genus 2 implementations. On a single core of an Intel Core i7-3520M (Ivy Bridge) our implementation on the Kummer surface breaks the 120 thousand cycle barrier which sets a new software speed record at the 128-bit security level for constant-time scalar multiplications compared to all previous genus 1 and genus 2 implementations. © 2013 International Association for Cryptologic Research. © 2013 Elsevier B.V. All rights reserved.
Citation - WoS: 20
Citation - Scopus: 24
Faster Compact Diffie-Hellman: Endomorphisms on the x-line
(SPRINGER-VERLAG BERLIN, 2014) Craig Costello; Huseyin Hisil; Benjamin Smith; Costello, Craig; Hisil, Huseyin; Smith, Benjamin; PQ Nguyen; E Oswald
We describe an implementation of fast elliptic curve scalar multiplication optimized for Diffie-Hellman Key Exchange at the 128-bit security level. The algorithms are compact (using only x-coordinates) run in constant time with uniform execution patterns and do not distinguish between the curve and its quadratic twist, they thus have a built-in measure of side-channel resistance. (For comparison we also implement two faster but non-constant-time algorithms.) The core of our construction is a suite of two-dimensional differential addition chains driven by efficient endomorphism decompositions built on curves selected from a family of Q-curve reductions over F-p2 with p = 2(127) - 1. We include state-of-the-art experimental results for twist-secure constant-time x-coordinate-only scalar multiplication.
Citation - WoS: 22
Citation - Scopus: 29
High-Performance Scalar Multiplication Using 8-Dimensional GLV/GLS Decomposition
(SPRINGER-VERLAG BERLIN, 2013) Joppe W. Bos; Craig Costello; Huseyin Hisil; Kristin Lauter; Bos, Joppe W.; Lauter, Kristin; Costello, Craig; Hisil, Huseyin; G Bertoni; JS Coron
This paper explores the potential for using genus 2 curves over quadratic extension fields in cryptography motivated by the fact that they allow for an 8-dimensional scalar decomposition when using a combination of the GLV/GLS algorithms. Besides lowering the number of doublings required in a scalar multiplication this approach has the advantage of performing arithmetic operations in a 64-bit ground field making it an attractive candidate for embedded devices. We found cryptographically secure genus 2 curves which although susceptible to index calculus attacks aim for the standardized 112-bit security level. Our implementation results on both high-end architectures (Ivy Bridge) and low-end ARM platforms (Cortex-A8) highlight the practical benefits of this approach.
Citation - WoS: 10
Citation - Scopus: 10
Jacobian coordinates on genus 2 curves
(Springer Verlag, 2014) Hüseyin Hişil; Craig Costello; Hisil, Huseyin; Costello, Craig; P. Sarkar , T. Iwata
This paper presents a new projective coordinate system and new explicit algorithms which together boost the speed of arithmetic in the divisor class group of genus 2 curves. The proposed formulas generalise the use of Jacobian coordinates on elliptic curves and their application improves the speed of performing cryptographic scalar multiplications in Jacobians of genus 2 curves over prime fields by an approximate factor of 1.25x. For example on a single core of an Intel Core i7-3770M (Ivy Bridge) we show that replacing the previous best formulas with our new set improves the cost of generic scalar multiplications from 243000 to 195000 cycles and drops the cost of specialised GLV-style scalar multiplications from 166000 to 129000 cycles. © 2020 Elsevier B.V. All rights reserved.
Citation - WoS: 9
Citation - Scopus: 9
Jacobian Coordinates on Genus 2 Curves
(SPRINGER, 2017) Huseyin Hisil; Craig Costello; Hisil, Huseyin; Costello, Craig
This paper presents a new projective coordinate system and new explicit algorithms which together boost the speed of arithmetic in the divisor class group of genus 2 curves. The proposed formulas generalize the use of Jacobian coordinates on elliptic curves and their application improves the speed of performing cryptographic scalar multiplications in Jacobians of genus 2 curves over prime fields by an approximate factor of 1.25x. For example on a single core of an Intel Core i7-3770 (Ivy Bridge) we show that replacing the previous best formulas with our new set improves the cost of generic scalar multiplications from 239000 to 192000 cycles and drops the cost of specialized GLV-style scalar multiplications from 155000 to 123000 cycles.
Citation - WoS: 5
Citation - Scopus: 8
On Kummer Lines with Full Rational 2-torsion and Their Usage in Cryptography
(ASSOC COMPUTING MACHINERY, 2019) Huseyin Hisil; Joost Renes; Hisil, Huseyin; Renes, Joost
A paper by Karati and Sarkar at Asiacrypt'17 has pointed out the potential for Kummer lines in genus 1 by observing that their SIMD-friendly arithmetic is competitive with the status quo. A more recent preprint explores the connection with (twisted) Edwards curves. In this article we extend this work and significantly simplify the treatment of Karati and Sarkar. We show that their Kummer line is the x-line of a Montgomery curve translated by a point of order two and exhibit a natural isomorphism to the y-line of a twisted Edwards curve. Moreover we show that the Kummer line presented by Gaudry and Lubicz can be obtained via the action of a point of order two on the y-line of an Edwards curve. The maps connecting these curves and lines are all very simple. As a result a cryptographic implementation can use the arithmetic that is optimal for its instruction set at negligible cost.
Citation - WoS: 4
Citation - Scopus: 6
Speeding up Huff form of elliptic curves
(SPRINGER, 2018) Neriman Gamze Orhon; Huseyin Hisil; Orhon, Neriman Gamze; Hisil, Huseyin
This paper presents faster inversion-free point addition formulas for the curve y(1+ ax2) = cx(1+ dy2). The proposed formulas improve the point doubling operation count record (I M S D a are arithmetic operations over a field. I: inversion M: multiplication S: squaring D: multiplication by a curve constant a: addition/ subtraction) from 6M + 5S to 8M and mixed addition operation count record from 10M to 8M. Both sets of formulas are shown to be 4-way parallel leading to an effective cost of 2M per either of the group operations.