International Association
for Cryptologic Research

This paper introduces a new key space for CSIDH and a new algorithm for constant-time evaluation of the CSIDH group action. The key space is not useful with previous algorithms, and the algorithm is not useful with previous key spaces, but combining the new key space with the new algorithm produces speed records for constant-time CSIDH. For example, for CSIDH-512 with a 256-bit key space, the best previous constant-time results used 789000 multiplications and more than 200 million Skylake cycles; this paper uses 438006 multiplications and 125.53 million cycles.

This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.

Choosing safe post-quantum parameters for the new CSIDH isogeny-based key-exchange system requires concrete analysis of the cost of quantum attacks. The two main contributions to attack cost are the number of queries in hidden-shift algorithms and the cost of each query. This paper analyzes algorithms for each query, introducing several new speedups while showing that some previous claims were too optimistic for the attacker. This paper includes a full computer-verified simulation of its main algorithm down to the bit-operation level.

This paper suggests to use rounded Gaussians in place of discrete Gaussians in rejection-sampling-based lattice signature schemes like BLISS or Lyubashevsky’s signature scheme. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures.We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present an implementation that runs in constant time. Our implementation needs no precomputed tables and is twice as fast as the variable-time CDT sampler posted by the BLISS authors with precomputed tables.

We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field $$\mathbb F_p$$, rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST’s post-quantum security category I.

It is well known that constant-time implementations of modular exponentiation cannot use sliding windows. However, software libraries such as Libgcrypt, used by GnuPG, continue to use sliding windows. It is widely believed that, even if the complete pattern of squarings and multiplications is observed through a side-channel attack, the number of exponent bits leaked is not sufficient to carry out a full key-recovery attack against RSA. Specifically, 4-bit sliding windows leak only 40% of the bits, and 5-bit sliding windows leak only 33% of the bits.In this paper we demonstrate a complete break of RSA-1024 as implemented in Libgcrypt. Our attack makes essential use of the fact that Libgcrypt uses the left-to-right method for computing the sliding-window expansion. We show for the first time that the direction of the encoding matters: the pattern of squarings and multiplications in left-to-right sliding windows leaks significantly more information about the exponent than right-to-left. We show how to extend the Heninger-Shacham algorithm for partial key reconstruction to make use of this information and obtain a very efficient full key recovery for RSA-1024. For RSA-2048 our attack is efficient for 13% of keys.

This paper improves the price-performance ratio of ECM, the elliptic-curve method of integer factorization. In particular, this paper constructs "a = -1" twisted Edwards curves having Q-torsion group Z/2 x Z/4, Z/8, or Z/6 and having a known non-torsion point; demonstrates that, compared to the curves used in previous ECM implementations, some of the new curves are more effective at finding small primes despite being faster; and precomputes particularly effective curves for several specific sizes of primes.

The original McEliece cryptosystem uses length-n codes over F_2 with dimension >=n-mt efficiently correcting t errors where 2^m>=n. This paper presents a generalized cryptosystem that uses length-n codes over small finite fields F_q with dimension >=n-m(q-1)t efficiently correcting floor(qt/2) errors where q^m>=n. Previously proposed cryptosystems with the same length and dimension corrected only floor((q-1)t/2) errors for q>=3. This paper also presents list-decoding algorithms that efficiently correct even more errors for the same codes over F_q. Finally, this paper shows that the increase from floor((q-1)t/2) errors to more than floor(qt/2) errors allows considerably smaller keys to achieve the same security level against all known attacks.

In the 1990s and early 2000s several papers investigated the relative merits of polynomial-basis and normal-basis computations for $\F_{2^n}$. Even for particularly squaring-friendly applications, such as implementations of Koblitz curves, normal bases fell behind in performance unless a type-I normal basis existed for $\F_{2^n}$. In 2007 Shokrollahi proposed a new method of multiplying in a type-II normal basis. Shokrollahi's method efficiently transforms the normal-basis multiplication into a single multiplication of two size-$(n+1)$ polynomials. This paper speeds up Shokrollahi's method in several ways. It first presents a simpler algorithm that uses only size-$n$ polynomials. It then explains how to reduce the transformation cost by dynamically switching to a `type-II optimal polynomial basis' and by using a new reduction strategy for multiplications that produce output in type-II polynomial basis. As an illustration of its improvements, this paper explains in detail how the multiplication overhead in Shokrollahi's original method has been reduced by a factor of $1.4$ in a major cryptanalytic computation, the ongoing attack on the ECC2K-130 Certicom challenge. The resulting overhead is also considerably smaller than the overhead in a traditional low-weight-polynomial-basis approach. This is the first state-of-the-art binary-elliptic-curve computation in which type-II bases have been shown to outperform traditional low-weight polynomial bases.

This paper introduces ``twisted Edwards curves,'' a generalization of the recently introduced Edwards curves; shows that twisted Edwards curves include more curves over finite fields, and in particular every elliptic curve in Montgomery form; shows how to cover even more curves via isogenies; presents fast explicit formulas for twisted Edwards curves in projective and inverted coordinates; and shows that twisted Edwards curves save time for many curves that were already expressible as Edwards curves.

This paper introduces GMP-EECM, a fast implementation of the elliptic-curve method of factoring integers. GMP-EECM is based on, but faster than, the well-known GMP-ECM software. The main changes are as follows: (1) use Edwards curves instead of Montgomery curves; (2) use twisted inverted Edwards coordinates; (3) use signed-sliding-window addition chains; (4) batch primes to increase the window size; (5) choose curves with small parameters $a,d,X_1,Y_1,Z_1$; (6) choose curves with larger torsion.

This paper presents a new shape for ordinary elliptic curves over fields of characteristic 2. Using the new shape, this paper presents the first complete addition formulas for binary elliptic curves, i.e., addition formulas that work for all pairs of input points, with no exceptional cases. If n >= 3 then the complete curves cover all isomorphism classes of ordinary elliptic curves over F_2^n. This paper also presents dedicated doubling formulas for these curves using 2M + 6S + 3D, where M is the cost of a field multiplication, S is the cost of a field squaring, and D is the cost of multiplying by a curve parameter. These doubling formulas are also the first complete doubling formulas in the literature, with no exceptions for the neutral element, points of order 2, etc. Finally, this paper presents complete formulas for differential addition, i.e., addition of points with known difference. A differential addition and doubling, the basic step in a Montgomery ladder, uses 5M + 4S + 2D when the known difference is given in affine form.

This paper presents several improvements to Stern's attack on the McEliece cryptosystem and achieves results considerably better than Canteaut et al. This paper shows that the system with the originally proposed parameters can be broken in just 1400 days by a single 2.4GHz Core 2 Quad CPU,or 7 days by a cluster of 200 CPUs. This attack has been implemented and is now in progress. This paper proposes new parameters for the McEliece and Niederreiter cryptosystems achieving standard levels of security against all known attacks. The new parameters take account of the improved attack; the recent introduction of list decoding for binary Goppa codes; and the possibility of choosing code lengths that are not a power of 2. The resulting public-key sizes are considerably smaller than previous parameter choices for the same level of security.

This paper reports record-setting performance for the elliptic-curve method of integer factorization: for example, 926.11 curves/second for ECM stage 1 with B1=8192 for 280-bit integers on a single PC.The state-of-the-art GMP-ECM software handles 124.71 curves/second for ECM stage 1 with B1=8192 for 280-bit integers using all four cores of a 2.4 GHz Core 2 Quad Q6600. The extra speed takes advantage of extra hardware,specifically two NVIDIA GTX 295 graphics cards,using a new ECM implementation introduced in this paper.Our implementation uses Edwards curves, relies on new parallel addition formulas, and is carefully tuned for the highly parallel GPU architecture.On a single GTX 295 the implementation performs 41.88 million modular multiplications per second for a general 280-bit modulus.GMP-ECM, using all four cores of a Q6600, performs 13.03 million modular multiplications per second. This paper also reports speeds on other graphics processors: for example, 2414 280-bit elliptic-curve scalar multiplications per second on an older NVIDIA 8800 GTS (G80), again for a general 280-bit modulus.For comparison, the CHES 2008 paper ``Exploiting the Power of GPUs for Asymmetric Cryptography'' reported 1412 elliptic-curve scalar multiplications per second on the same graphics processor despite having fewer bits in the scalar (224 instead of 280), fewer bits in the modulus (224 instead of 280), and a special modulus (2^{224}-2^{96}+1).

Edwards curves have attracted great interest for several reasons. When curve parameters are chosen properly, the addition formulas use only $10M+1S$. The formulas are {\it strongly unified}, i.e., work without change for doublings; even better, they are {\it complete}, i.e., work without change for all inputs. Dedicated doubling formulas use only $3M+4S$, and dedicated tripling formulas use only $9M+4S$. This paper introduces {\it inverted Edwards coordinates}. Inverted Edwards coordinates $(X_1:Y_1:Z_1)$ represent the affine point $(Z_1/X_1,Z_1/Y_1)$ on an Edwards curve; for comparison, standard Edwards coordinates $(X_1:Y_1:Z_1)$ represent the affine point $(X_1/Z_1,Y_1/Z_1)$. This paper presents addition formulas for inverted Edwards coordinates using only $9M+1S$. The formulas are not complete but still are strongly unified. Dedicated doubling formulas use only $3M+4S$, and dedicated tripling formulas use only $9M+4S$. Inverted Edwards coordinates thus save $1M$ for each addition, without slowing down doubling or tripling.

This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: ? many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; ? double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; ? many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S-M tradeoffs and includes recent advances such as inverted Edwards coordinates. The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader.

Let $P$ be a point on an elliptic curve over a finite field of large characteristic. Exactly how many points $2P,3P,5P,7P,9P,\ldots,mP$ should be precomputed in a sliding-window computation of $nP$? Should some or all of the points be converted to affine form, and at which moments during the precomputation should these conversions take place? Exactly how many field multiplications are required for the resulting computation of $nP$? The answers depend on the size of $n$, the $\inversions/\mults$ ratio, the choice of curve shape, the choice of coordinate system, and the choice of addition formulas. This paper presents answers that, compared to previous analyses, are more carefully optimized and cover a much wider range of situations.

Task-specific groups are often formed in an ad-hoc manner within big structures, like companies. Take the following typical scenario: A high rank manager decides that a task force group for some project needs to be built. This order is passed down the hierarchy where it finally reaches a manager who calls some employees to form a group. The members should communicate in a secure way and for efficiency reasons symmetric systems are the common choice. To establish joint secret keys for groups, group key exchange (GKE) protocols were developed. If the users are part of e.g. a Public Key Infrastructure (PKI), which is usually the case within a company or a small network, it is possible to achieve authenticated GKE by modifying the protocol and particularly by including signatures. In this paper we recall a GKE due to Burmester and Desmedt which needs only $O(\log n)$ communication and computation complexity per user, rather than $O(n)$ as in the more well-known Burmester-Desmedt protocol, and runs in a constant number of rounds. To achieve authenticated GKE one can apply compilers, however, the existing ones would need $O(n)$ computation and communication thereby mitigating the advantages of the faster protocol. Our contribution is to extend an existing compiler so that it preserves the computation and communication complexity of the non-authenticated protocol. This is particularly important for tree based protocols.

We identify and fill some gaps with regard to consistency (the extent to which false positives are produced) for public-key encryption with keyword search (PEKS). We define computational and statistical relaxations of the existing notion of perfect consistency, show that the scheme of Boneh et al. in Eurocrypt 2004 is computationally consistent, and provide a new scheme that is statistically consistent. We also provide a transform of an anonymous IBE scheme to a secure PEKS scheme that, unlike the previous one, guarantees consistency. Finally, we suggest three extensions of the basic notions considered here, namely anonymous HIBE, public-key encryption with temporary keyword search, and identity-based encryption with keyword search.

L\'opez-Dahab coordinates are usually the system of choice for implementations of elliptic curves over binary fields. We give new formulas for doubling which need one squaring less and one more addition. This leads to a speed-up for binary fields in polynomial basis representation.

We present a kind of group suitable for cryptographic applications: the trace zero subvariety. The construction is based on Weil descent from curves of genus two over extension fields $\F_{p^n}$, $n=3$. On the Jacobian of the curve the group can be seen as a prime order subgroup, however, considering the construction as Weil descent we can argue that the security is equivalent to that of groups based on low-genus hyperelliptic curves over prime fields. The advantage is that the complexity to compute scalar multiples is lower, as one can make use of the Frobenius endomorphism of the initial curve. Thus the trace zero subvariety can be used efficiently in protocols based on the discrete logarithm problem.

Using the Frobenius endomorphism the operation of computing scalar-mulitples in the Jacobian of a hyperelliptic curve is sped-up considerably. The kind of curves considered are Kobiltz i.e. subfield curves, defined over a small finite field which are then considered over a large extension field. We deal with computation of the group order over various extension fields, algorithms to obtain the mentioned speed-up, and experimental results concerning both issues. Additionally an alternative set-up is treated which uses arihtmetic in the finite field only and allows shorter code for similar security. Furthermore explicit formulae to perform the arithmetic in the ideal class group explicitely are derived and can thus be used for implementation in hardware; in software they are also faster than the generic Cantor algorithm. As a second group suitable for cryptographic applications the trace-zero-variety is considered. Here we investigate the group operation and deal with security issues.

We extend the explicit formulae for arithmetic on genus two curves of Takahashi and Miyamoto,Doi,Matsuo,Chao,and Tsuji to fields of even characteristic and to arbitrary equation of the curve and slightly improve them. These formulae can be evaluated faster than the more general Cantor algorithm and allow to obtain faster arithmetic on a hyperelliptic genus 2 curve than on elliptic curves. We give timings for implementations using various libraries for the field arithmetic.

We investigate formulae to double and add in the ideal class group of a hyperelliptic genus 2 curve avoiding inversions. To that aim we introduce a further coordinate in the representation of a class in which we collect the common denominator of the usual 4 coordinates. The analysis shows that this is practical and advantageous whenever inversions are expensive compared to multiplications like for example on smart cards.

This paper is the third in a line considering the arithmetic in the ideal class group of hyperelliptic genus two curves. The previous two papers deal with generalizations of affine and projective coordinates. Now we investigate how one can obtain inversion free formulae that are faster than projective by considering weighted coordinates. To that end we make an extensive case study to deal with different characteristic, equation of the curve, space requirement and situation of appliance.