Browsing by Author "Costello, Craig"

Now showing 1 - 7 of 7

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.
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.