zbMATH — the first resource for mathematics

Normal elliptic bases and torus-based cryptography. (English) Zbl 1227.11122
McGuire, Gary (ed.) et al., Finite fields. Theory and applications. Proceedings of the 9th international conference on finite fields and applications, Dublin, Ireland, July 13–17, 2009. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4786-2/pbk). Contemporary Mathematics 518, 137-153 (2010).
For an extension of finite fields of degree 6, \(\mathbb F_{q^6}/\mathbb F_q\), the XTR subgroups of A. K. Lenstra and E. R. Verheul [“The XTR public key system”, Lect. Notes Comput. Sci. 1880, 1–19 (2000; Zbl 0995.94538)] can be encoded to two elements of \(\mathbb F_q\) with \(\log^{1+o(1)} q\) bit operations. Here the authors consider extensions of arbitrary degree \(n\) and encoding algebraic tori (which include XTR subgroups) to \(\varphi (n)\) elements of \(\mathbb F_q\). In the best case, their algorithm also only uses \(\log^{1+o(1)} q\) bit operations. This best case occurs when \(\Phi_e(q)\) and \(\Phi_f(q)\), \(\Phi_k\) the \(k\)th cyclotomic polynomial, are relatively prime for all distinct divisors \(e\) and \(f\) of \(n\). They show that for infinitely many squarefree \(n\), there exist infinitely many such \(q\).
Their algorithm is a variation of one by van Dijk and Woodruff, improved with the use of normal elliptic bases. A consequence is that the cost of the encoding phase is now negligible in Diffie-Hellman cryptographic schemes.
For the entire collection see [Zbl 1193.11003].
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
14G50 Applications to coding theory and cryptography of arithmetic geometry
94A60 Cryptography