Applications of Frobenius Expansions in Elliptic
Curve Cryptography

by Waldyr Dias Benits Junior

RHUL-MA-2009-12

Abstract:

Recent developments in elliptic curve cryptography have
heightened the need for fast scalar point multiplication,
specially when working on environments with limited
computational power. It is well known that point multiplication
on elliptic curves over F_{q^m} (with m > 1) can be accelerated
using Frobenius expansions. In practice, the computation is
much faster than the standard double-and-add scalar
multiplication.

An efficient implementation of elliptic curve cryptosystems can
use a Koblitz curve and convert integers into Frobenius
expansions to perform fast scalar multiplications. However,
this conversion of integers to Frobenius expansions would lead
to extra code on the device (i.e., silicon area) and extra
computational cost.

According to N. Koblitz, H. Lenstra suggested that rather than
choosing a random integer n and then converting to a Frobenius
expansion n(\tau), in certain cryptosystems it might be more
efficient to generate a random Frobenius expansion directly.
The temptation then is to choose a relatively short and/or
sparse value for n(\tau). If this is done then we must
re-evaluate the difficulty of the discrete logarithm problem
(and other computational problems). A further issue is that the
existing security proofs may not directly apply. For some
systems it may be necessary to develop bespoke security proofs
for the Frobenius expansion case.

In this thesis, we analyse the Frobenius expansion DLP and
present algorithms to solve it. Furthermore, we propose a
variant of a well known identification scheme designed for
public key cryptography on very restricted devices. More
precisely, we construct the Girault-Poupard-Stern (GPS)
identification scheme for Koblitz elliptic curves using
Frobenius expansions. The idea is to use Frobenius expansions
throughout the protocol, so there is no need to convert between
integers and Frobenius expansions. We also give a security
analysis of the proposed scheme.