Normal Elliptic Bases and Torus-Based Cryptography

2009/09/01 by Dunand, Clement, Lercier, Reynald
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.0909.0236

Abstract

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 log q. 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.

Related

• On efficient normal bases over binary fields
• Toric Codes, Multiplicative Structure and Decoding
• Improvement Of Barreto-Voloch Algorithm For Computing rth Roots Over Finite Fields
• Secret Sharing Schemes with a large number of players from Toric\n Varieties
• Trilinear maps for cryptography