## CryptoDB

### David Kohel

#### Publications

**Year**

**Venue**

**Title**

2020

ASIACRYPT

SQISign: Compact Post-Quantum signatures from Quaternions and Isogenies
📺 ★
Abstract

We introduce a new signature scheme, \emph{SQISign}, (for \emph{Short Quaternion and Isogeny Signature}) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round, high soundness, interactive identification protocol. Targeting the post-quantum NIST-1 level of security, our implementation results in signatures of $204$ bytes, secret keys of $16$ bytes and public keys of $64$ bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification.
While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper.
We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings.
A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.

2008

EPRINT

Double-Base Number System for Multi-Scalar Multiplications
Abstract

The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form $[n]P+m[Q]$. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously $n$ and $m$. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can
find a chain of reasonable length that uses exactly the same terms to compute both $n$ and $m$. Furthermore, we discuss an algorithm to produce such a Joint Double-Base Chain. Because of its simplicity, this algorithm is straightforward to implement, efficient, and also quite easy to analyze. Namely, in our main result we show that the average number of terms in the expansion is less than $0.3945\log_2 n$. With respect to the Joint Sparse Form, this induces a reduction by more than $20\%$ of the number of additions. As a consequence, the total number of multiplications required for a scalar multiplications is minimal for our method, across all the methods using two precomputations, $P+Q$ and $P-Q$. This is the case even with coordinate systems offering very cheap doublings, in contrast with recent results on scalar multiplications.
Several variants are discussed, including methods using more precomputed points and a generalization relevant for Koblitz curves.
Our second contribution is a new way to evaluate $\overline\phi$, the dual endomorphism of the Frobenius. Namely, we propose formulae to compute $\pm\overline\phi(P)$ with at most 2 multiplications and 2 squarings in $\F_{2^d}$. This represents a speed-up of about $50\%$ with respect to the fastest techniques known. This has very concrete consequences on scalar and multi-scalar multiplications on
Koblitz curves.

2005

EPRINT

Efficient Scalar Multiplication by Isogeny Decompositions
Abstract

On an elliptic curve, the degree of an isogeny corresponds essentially to
the degrees of the polynomial expressions involved in its application.
The multiplication--by--$\ell$ map $[\ell]$ has degree~$\ell^2$, therefore
the complexity to directly evaluate $[\ell](P)$ is $O(\ell^2)$.
For a small prime $\ell\, (= 2, 3)$ such that the additive binary
representation provides no better performance, this represents the true
cost of application of scalar multiplication.
If an elliptic curves admits an isogeny $\varphi$ of degree $\ell$ then
the costs of computing $\varphi(P)$ should in contrast be $O(\ell)$ field
operations. Since we then have a product expression $[\ell] =
\hat{\varphi}\varphi$, the existence of an $\ell$-isogeny $\varphi$ on
an elliptic curve yields a theoretical improvement from $O(\ell^2)$ to
$O(\ell)$ field operations for the evaluation of $[\ell](P)$ by na\"ive
application of the defining polynomials. In this work we investigate
actual improvements for small $\ell$ of this asymptotic complexity.
For this purpose, we describe the general construction of families of
curves with a suitable decomposition $[\ell] = \hat{\varphi}\varphi$,
and provide explicit examples of such a family of curves with simple
decomposition for~$[3]$. Finally we derive a new tripling algorithm
to find complexity improvements to triplication on a curve in certain
projective coordinate systems, then combine this new operation to non-adjacent forms
for $\ell$-adic expansions in order to obtain an improved
strategy for scalar multiplication on elliptic curves.

2003

ASIACRYPT

#### Coauthors

- Daniel J. Bernstein (1)
- Chitchanok Chuengsatiansup (1)
- Luca De Feo (1)
- Christophe Doche (4)
- Pierrick Gaudry (2)
- T. Houtmann (1)
- Thomas Icart (2)
- Tanja Lange (1)
- Kristin E. Lauter (1)
- Antonin Leroux (1)
- Christophe Petit (2)
- Christophe Ritzenthaler (1)
- Francesco Sica (2)
- Benjamin Smith (1)
- Jean-Pierre Tignol (1)
- A. Weng (1)
- Benjamin Wesolowski (1)