## CryptoDB

### Thorsten Kleinjung

#### Affiliation: Ecole Polytechnique FÃ©dÃ©rale de Lausanne

#### Publications

**Year**

**Venue**

**Title**

2019

ASIACRYPT

CSI-FiSh: Efficient Isogeny Based Signatures Through Class Group Computations
Abstract

In this paper we report on a new record class group computation of an imaginary quadratic field having 154-digit discriminant, surpassing the previous record of 130 digits. This class group is central to the CSIDH-512 isogeny based cryptosystem, and knowing the class group structure and relation lattice implies efficient uniform sampling and a canonical representation of its elements. Both operations were impossible before and allow us to instantiate an isogeny based signature scheme first sketched by Stolbunov. We further optimize the scheme using multiple public keys and Merkle trees, following an idea by De Feo and Galbraith. We also show that including quadratic twists allows to cut the public key size in half for free. Optimizing for signature size, our implementation takes 390 ms to sign/verify and results in signatures of 263 bytes, at the expense of a large public key. This is 300 times faster and over 3 times smaller than an optimized version of SeaSign for the same parameter set. Optimizing for public key and signature size combined, results in a total size of 1468 bytes, which is smaller than any other post-quantum signature scheme at the 128-bit security level.

2010

EPRINT

Factorization of a 768-bit RSA modulus
Abstract

This paper reports on the factorization of the 768-bit number RSA-768 by the number field sieve factoring method and discusses some
implications for RSA.

2010

EPRINT

ECC2K-130 on Cell CPUs
Abstract

This paper describes an implementation of Pollard's rho algorithm to
compute the elliptic curve discrete logarithm for the Synergistic
Processor Elements of the Cell Broadband Engine Architecture.
Our implementation targets
the elliptic curve discrete logarithm problem defined in the Certicom
ECC2K-130 challenge. We compare a bitsliced implementation to a
non-bitsliced implementation and describe several optimization
techniques for both approaches. In particular, we address the question whether normal-basis or polynomial-basis representation of field elements leads to better performance. Using our software, the ECC2K-130 challenge can be solved in one year using the
Synergistic Processor Units of less than 2700
Sony Playstation~3 gaming consoles.

2010

EPRINT

Pushing the Limits of ECM
Abstract

This paper describes our implementation of phase one of the elliptic curve method on the Cell processor and reports on actual record factors obtained. Our implementation uses a new and particularly efficient variable radix multiplication of independent interest.

2007

EPRINT

A kilobit special number field sieve factorization
Abstract

We describe how we reached a new factoring milestone by completing the
first special number field sieve factorization of a number having more
than 1024 bits, namely the Mersenne number $2^{1039}-1$.
Although this factorization is orders of magnitude `easier' than a
factorization of a 1024-bit RSA modulus is believed to be, the
methods we used to obtain our result shed new light on the feasibility
of the latter computation.

#### Coauthors

- Kazumaro Aoki (4)
- Maxime Augier (1)
- Razvan Barbulescu (2)
- Ward Beullens (1)
- Joppe W. Bos (9)
- Claus Diem (1)
- Jens Franke (5)
- Pierrick Gaudry (4)
- Robert Granger (4)
- James Hughes (1)
- Alexander Kruppa (2)
- Arjen K. Lenstra (10)
- Andrea Miele (2)
- Peter L. Montgomery (3)
- Ruben Niederhagen (1)
- Dag Arne Osvik (4)
- Christof Paar (1)
- Jan Pelzl (1)
- Christine Priplata (2)
- Herman J. J. te Riele (2)
- Peter Schwabe (1)
- Colin Stahlke (2)
- Emmanuel Thomé (2)
- Andrey Timofeev (2)
- Frederik Vercauteren (1)
- Christophe Wachter (1)
- Paul Zimmermann (2)
- Jens Zumbrägel (4)