FWF Logo National Research Network S9600
Analytic Combinatorics and Probabilistic Number Theory


Project S9606 - Analysis of Digital Expansions with Applications in Cryptography

Principal Investigator

Clemens Heuberger

Co-Investigator

Peter Grabner

Funded Researcher

Christiaan van de Woestijne

Description

The principle of many schemes in public key cryptography relies on the assumption that the discrete logarithm problem is intractable in large finite groups, such as the group $ (\mathbb{Z}/p_1p_2\mathbb{Z})^*$ ($ p_1$ and $ p_2$ are large primes) in the RSA-cryptosystem, the group $ E(\mathbb{F}_q)$ of $ \mathbb{F}_q$-rational points on an elliptic curve $ E$ or on Jacobian varieties of curves of higher genus ($ q$ is either a large power of $ 2$ or a large prime in this context).

All these cryptosystems need fast exponentiation or scalar multiplication by $ n$ in the underlying Abelian group. The double-and-add algorithm based on the binary expansion needs $ \frac12\log_2n$ group additions on average. In the case of elliptic and hyperelliptic cryptosystems further arithmetic structure is present and can be exploited to decrease the number of additions to $ \frac13\log_2n$ by using signed binary expansions. Another approach uses expansions with respect to the Frobenius endomorphism of $ \overline{\mathbb{F}}_q$. It is one aim of this project to use canonical number systems and generalisations in imaginary quadratic fields for speeding up multiplication on broader classes of elliptic curves. A further important requirement for practical implementations - not met by most earlier algorithms - is the computability of optimal or "almost" optimal expansions by an online algorithm (starting with the most significant digit).

We also want to perform a precise asymptotic study of the moments and - if possible - the distribution of the weight (= number of additions) for the various expansions arising in the context of cryptography. Occurrence of subblocks, carry propagation and various schemes for speeding up computations such as sliding window methods and the effect of precomputations shall be investigated.