International Association for Cryptologic Research

# Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

## Details

Waldyr Dias Benits Junior (#365)
Name Waldyr Dias Benits Junior
Topic of his/her doctorate. Applications of Fobenius Expansions in Elliptic Curve Cryptography
Category applications
Keywords Frobenius expansions, Elliptic curves
Ph.D. Supervisor(s) Steven D. Galbraith
Year of completion 2008
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 can be twice as fast as the standard double-and-add scalar multiplication. Any efficient implementation of elliptic curve cryptosystems can use a Koblitz curve and convert integers into Frobenius expansions to perform fast scalar multiplications. However, this would lead to extra code on the device (i.e., silicon area) and extra computational cost to convert an integer to a Frobenius expansion. Jerome Solinas 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.