On Bilinear Structures on Divisor Class Groups

Gerhard Frey[1]

  • [1] Institute for Experimental Mathematics University of Duisburg-Essen Ellernstrasse 29 45219 Essen Germany

Annales mathématiques Blaise Pascal (2009)

  • Volume: 16, Issue: 1, page 1-26
  • ISSN: 1259-1734

Abstract

top
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.

How to cite

top

Frey, Gerhard. "On Bilinear Structures on Divisor Class Groups." Annales mathématiques Blaise Pascal 16.1 (2009): 1-26. <http://eudml.org/doc/10569>.

@article{Frey2009,
abstract = {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 $\mathbf\{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.},
affiliation = {Institute for Experimental Mathematics University of Duisburg-Essen Ellernstrasse 29 45219 Essen Germany},
author = {Frey, Gerhard},
journal = {Annales mathématiques Blaise Pascal},
keywords = {Discrete Logarithms; pairings; Brauer groups; Index-Calculus; discrete logarithms; index-calculus},
language = {eng},
month = {1},
number = {1},
pages = {1-26},
publisher = {Annales mathématiques Blaise Pascal},
title = {On Bilinear Structures on Divisor Class Groups},
url = {http://eudml.org/doc/10569},
volume = {16},
year = {2009},
}

TY - JOUR
AU - Frey, Gerhard
TI - On Bilinear Structures on Divisor Class Groups
JO - Annales mathématiques Blaise Pascal
DA - 2009/1//
PB - Annales mathématiques Blaise Pascal
VL - 16
IS - 1
SP - 1
EP - 26
AB - 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 $\mathbf{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.
LA - eng
KW - Discrete Logarithms; pairings; Brauer groups; Index-Calculus; discrete logarithms; index-calculus
UR - http://eudml.org/doc/10569
ER -

References

top
  1. R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, F. Vercauteren, The Handbook of Elliptic and Hyperelliptic Curve Cryptography, (2005), CRC, Baton Rouge Zbl1082.94001MR2162716
  2. P. S. L. M. Barreto, B. Lynn, M. Scott, Constructing elliptic curves with prescribed embedding degrees, Security in Communication Networks – SCN 2002, volume 2576 of Lecture Notes in Comput. Sci. (2003), 257-267, CimatoSS. Zbl1022.94008
  3. P. S. L. M. Barreto, M. Naehrig, Pairing-friendly elliptic curves of prime order, Selected Areas in Cryptography – SAC’2005, Lecture Notes in Comput. Sci. 3897 (2006), 319-331, PreneelBB. Zbl1151.94479MR2241646
  4. D. Boneh, M. Franklin, Identity based encryption from the Weil pairing, SIAM J. Comput. 32(3) (2003), 586-615 Zbl1046.94008MR2001745
  5. D. Boneh, B. Lynn, H. Shacham, Short signatures from the Weil pairing, Advances in Cryptology – Asiacrypt 2001, Lecture Notes in Comput. Sci. 2248 (2002), 514-532, BoydCC. Zbl1064.94554MR1934861
  6. G. Frey, Applications of arithmetical geometry to cryptographic constructions, Finite fields and applications (2001), 128-161, JungnickelD.D. Zbl1015.94545MR1849086
  7. G. Frey, On the relation between Brauer groups and discrete logarithms, Tatra Mt. Math. Publ. 33 (2006), 199-227 Zbl1187.11043MR2271447
  8. G. Frey, T. Lange, Mathematical background of public key cryptography, Séminaires et Congrès SMF: AGCT 2003 (2005), 41-74, AubryY.Y. Zbl1155.11361MR2182837
  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 45(5) (1999), 1717-1719 Zbl0957.94025MR1699906
  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. 62 (1994), 865-874 Zbl0813.14045MR1218343
  11. M.-D. Huang, W. Raskind, Signature calculus and discrete logarithm problems, Proc. ANTS VII, LNCS 4076 (2006), 558-572, HessFF. Zbl1143.11363MR2282949
  12. J Neukirch, Algebraic number theory, (1999), Springer, Heidelberg Zbl0956.11021MR1697859
  13. A. Joux, A one round protocol for tripartite Diffie–Hellman, Proc. ANTS IV, LNCS 1838 (2000), 385-394, BosmaW.W. Zbl1029.94026MR1850619
  14. S. Lichtenbaum, Duality theorems for curves over p -adic fields, Invent. Math. 7 (1969), 120-136 Zbl0186.26402MR242831
  15. B. Mazur, Notes on étale cohomology of number fields, Ann. sci. ENS 6 (1973), 521-552 Zbl0282.14004MR344254
  16. V.C. Miller, The Weil Pairing, and Its Efficient Calculation, J.Cryptology 17 (2004), 235-261 Zbl1078.14043MR2090556
  17. D. Mumford, Abelian Varieties, (1970), Oxford University Press, Oxford Zbl0223.14022MR282985
  18. K. Nguyen, Explicit Arithmetic of Brauer Groups, Ray Class Fields and Index Calculus, (2001) 
  19. J.P. Serre, Groupes algébriques et corps de classes, (1959), Hermann, Paris Zbl0097.35604MR103191
  20. J.P. Serre, Corps locaux, (1962), Hermann, Paris Zbl0137.02601MR354618
  21. H. Stichtenoth, Algebraic Function Fields and Codes, (1993), Springer, Heidelberg Zbl0816.14011MR1251961
  22. J. Tate, W C -groups over 𝔭 -adic fields, 13 (1958), Secrétariat mathématique, Paris Zbl0091.33701MR105420

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.