On Bilinear Structures on Divisor Class Groups
Annales mathématiques Blaise Pascal, Volume 16 (2009) no. 1, pp. 1-26.

It is well known that duality theorems are of utmost importance for the arithmetic of local and global fields and that Brauer groups appear in this context unavoidably. The key word here is class field theory.

In this paper we want to make evident that these topics play an important role in public key cryptopgraphy, too. Here the key words are Discrete Logarithm systems with bilinear structures.

Almost all public key crypto systems used today based on discrete logarithms use the ideal class groups of rings of holomorphic functions of affine curves over finite fields F q to generate the underlying groups. We explain in full generality how these groups can be mapped to Brauer groups of local fields via the Lichtenbaum-Tate pairing, and we give an explicit description.

Next we discuss under which conditions this pairing can be computed efficiently.

If so, the discrete logarithm is transferred to the discrete logarithm in local Brauer groups and hence to computing invariants of cyclic algebras. We shall explain how this leads us in a natural way to the computation of discrete logarithms in finite fields.

To end we give an outlook to a globalisation using the Hasse-Brauer-Noether sequence and the duality theorem ot Tate-Poitou which allows to apply index-calculus methods resulting in subexponential algorithms for the computation of discrete logarithms in finite fields as well as for the computation of the Euler totient function (so we have an immediate application to the RSA-problem), and, as application to number theory, a computational method to “describe” cyclic extensions of number fields with restricted ramification.

DOI: 10.5802/ambp.250
Classification: 11R65, 11R37, 11G20
Keywords: Discrete Logarithms, pairings, Brauer groups, Index-Calculus
Gerhard Frey 1

1 Institute for Experimental Mathematics University of Duisburg-Essen Ellernstrasse 29 45219 Essen Germany
@article{AMBP_2009__16_1_1_0,
     author = {Gerhard Frey},
     title = {On {Bilinear} {Structures} on {Divisor} {Class} {Groups}},
     journal = {Annales math\'ematiques Blaise Pascal},
     pages = {1--26},
     publisher = {Annales math\'ematiques Blaise Pascal},
     volume = {16},
     number = {1},
     year = {2009},
     doi = {10.5802/ambp.250},
     mrnumber = {2514524},
     zbl = {1187.11044},
     language = {en},
     url = {https://ambp.centre-mersenne.org/articles/10.5802/ambp.250/}
}
TY  - JOUR
AU  - Gerhard Frey
TI  - On Bilinear Structures on Divisor Class Groups
JO  - Annales mathématiques Blaise Pascal
PY  - 2009
SP  - 1
EP  - 26
VL  - 16
IS  - 1
PB  - Annales mathématiques Blaise Pascal
UR  - https://ambp.centre-mersenne.org/articles/10.5802/ambp.250/
DO  - 10.5802/ambp.250
LA  - en
ID  - AMBP_2009__16_1_1_0
ER  - 
%0 Journal Article
%A Gerhard Frey
%T On Bilinear Structures on Divisor Class Groups
%J Annales mathématiques Blaise Pascal
%D 2009
%P 1-26
%V 16
%N 1
%I Annales mathématiques Blaise Pascal
%U https://ambp.centre-mersenne.org/articles/10.5802/ambp.250/
%R 10.5802/ambp.250
%G en
%F AMBP_2009__16_1_1_0
Gerhard Frey. On Bilinear Structures on Divisor Class Groups. Annales mathématiques Blaise Pascal, Volume 16 (2009) no. 1, pp. 1-26. doi : 10.5802/ambp.250. https://ambp.centre-mersenne.org/articles/10.5802/ambp.250/

[1] R. Avanzi; H. Cohen; C. Doche; G. Frey; T. Lange; K. Nguyen; F. Vercauteren The Handbook of Elliptic and Hyperelliptic Curve Cryptography, CRC, Baton Rouge, 2005 | MR | Zbl

[2] P. S. L. M. Barreto; B. Lynn; M. Scott; S Cimato; C. Galdi; G. Persiano Constructing elliptic curves with prescribed embedding degrees, Security in Communication Networks – SCN 2002, volume 2576 of Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, 2003, pp. 257-267 | Zbl

[3] P. S. L. M. Barreto; M. Naehrig; B Preneel; St.Tavares Pairing-friendly elliptic curves of prime order, Selected Areas in Cryptography – SAC’2005, Lecture Notes in Comput. Sci. 3897, Springer Verlag, Berlin, 2006, pp. 319-331 | MR | Zbl

[4] D. Boneh; M. Franklin Identity based encryption from the Weil pairing, SIAM J. Comput., Volume 32(3) (2003), pp. 586-615 | DOI | MR | Zbl

[5] D. Boneh; B. Lynn; H. Shacham; C Boyd Short signatures from the Weil pairing, Advances in Cryptology – Asiacrypt 2001, Lecture Notes in Comput. Sci. 2248, Springer Verlag Berlin, 2002, pp. 514-532 | MR | Zbl

[6] G. Frey; D. Jungnickel; H. Niederreiter Applications of arithmetical geometry to cryptographic constructions, Finite fields and applications, Springer, Berlin, 2001, pp. 128-161 | MR | Zbl

[7] G. Frey On the relation between Brauer groups and discrete logarithms, Tatra Mt. Math. Publ., Volume 33 (2006), pp. 199-227 | MR

[8] G. Frey; T. Lange; Y. Aubry Mathematical background of public key cryptography, Séminaires et Congrès SMF: AGCT 2003, SMF, 2005, pp. 41-74 | MR

[9] G. Frey; M. Müller; H. G. Rück The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems, IEEE Trans. Inform. Theory, Volume 45(5) (1999), pp. 1717-1719 | DOI | MR | Zbl

[10] G. Frey; H. G. Rück A remark concerning m-divisibility and the discrete logarithm problem in the divisor class group of curves, Math. Comp., Volume 62 (1994), pp. 865-874 | MR | Zbl

[11] M.-D. Huang; W. Raskind; F Hess; S Pauli; M Pohst Signature calculus and discrete logarithm problems, Proc. ANTS VII, LNCS 4076, Springer, Berlin, 2006, pp. 558-572 | MR | Zbl

[12] J Neukirch Algebraic number theory, Springer, Heidelberg, 1999 | MR | Zbl

[13] A. Joux; W. Bosma A one round protocol for tripartite Diffie–Hellman, Proc. ANTS IV, LNCS 1838, Springer, 2000, pp. 385-394 | MR | Zbl

[14] S. Lichtenbaum Duality theorems for curves over p-adic fields, Invent. Math., Volume 7 (1969), pp. 120-136 | DOI | MR | Zbl

[15] B. Mazur Notes on étale cohomology of number fields, Ann. sci. ENS, Volume 6 (1973) no. 4, pp. 521-552 | Numdam | MR | Zbl

[16] V.C. Miller The Weil Pairing, and Its Efficient Calculation, J.Cryptology, Volume 17 (2004), pp. 235-261 | DOI | MR | Zbl

[17] D. Mumford Abelian Varieties, Oxford University Press, Oxford, 1970 | MR | Zbl

[18] K. Nguyen Explicit Arithmetic of Brauer Groups, Ray Class Fields and Index Calculus (2001) (Ph.D. thesis, University of Essen)

[19] J.P. Serre Groupes algébriques et corps de classes, Hermann, Paris, 1959 | MR | Zbl

[20] J.P. Serre Corps locaux, Hermann, Paris, 1962 | MR | Zbl

[21] H. Stichtenoth Algebraic Function Fields and Codes, Springer, Heidelberg, 1993 | MR | Zbl

[22] J. Tate W C -groups over 𝔭 -adic fields, Séminaire Bourbaki; 10e année: 1957/1958. Textes des conférences; Exposés 152 à 168; 2e éd. corrigée, Exposé 156, 13, Secrétariat mathématique, Paris, 1958 | Numdam | MR | Zbl

Cited by Sources: