Reynald Lercier

C. Dunand and R. Lercier. Normal Elliptic Bases and Torus-Based Cryptography. In Daniel Panario Gary McGuire, Gary L. Mullen and Igor E. Shparlinski, editors, Finite Fields: Theory and Applications, Contemporary Mathematics, pages 137-153. American Mathematical Society, 2010. Ninth International Conference Finite Fields and Applications.

We consider representations of algebraic tori T_n(F_q) over finite fields. We make use of normal elliptic bases to show that, for infinitely many squarefree integers n and infinitely many values of q, we can encode m torus elements, to a small fixed overhead and to m φ(n)-tuples of F_q elements, in quasi-linear time in logq. This improves upon previously known algorithms, which all have a quasi-quadratic complexity. As a result, the cost of the encoding phase is now negligible in Diffie-Hellman cryptographic schemes.

[ bib | preprint | publication ] Back