Cryptography based on number fields with large regulator

Johannes Buchmann; Markus Maurer; Bodo Möller

Journal de théorie des nombres de Bordeaux (2000)

  • Volume: 12, Issue: 2, page 293-307
  • ISSN: 1246-7405

Abstract

top
We explain a variant of the Fiat-Shamir identification and signature protocol that is based on the intractability of computing generators of principal ideals in algebraic number fields. We also show how to use the Cohen-Lenstra-Martinet heuristics for class groups to construct number fields in which computing generators of principal ideals is intractable.

How to cite

top

Buchmann, Johannes, Maurer, Markus, and Möller, Bodo. "Cryptography based on number fields with large regulator." Journal de théorie des nombres de Bordeaux 12.2 (2000): 293-307. <http://eudml.org/doc/248488>.

@article{Buchmann2000,
abstract = {We explain a variant of the Fiat-Shamir identification and signature protocol that is based on the intractability of computing generators of principal ideals in algebraic number fields. We also show how to use the Cohen-Lenstra-Martinet heuristics for class groups to construct number fields in which computing generators of principal ideals is intractable.},
author = {Buchmann, Johannes, Maurer, Markus, Möller, Bodo},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {class groups; public key cryptosystem; quadratic order; PIP-FS; Fiat-Shamir identification; principal ideals},
language = {eng},
number = {2},
pages = {293-307},
publisher = {Université Bordeaux I},
title = {Cryptography based on number fields with large regulator},
url = {http://eudml.org/doc/248488},
volume = {12},
year = {2000},
}

TY - JOUR
AU - Buchmann, Johannes
AU - Maurer, Markus
AU - Möller, Bodo
TI - Cryptography based on number fields with large regulator
JO - Journal de théorie des nombres de Bordeaux
PY - 2000
PB - Université Bordeaux I
VL - 12
IS - 2
SP - 293
EP - 307
AB - We explain a variant of the Fiat-Shamir identification and signature protocol that is based on the intractability of computing generators of principal ideals in algebraic number fields. We also show how to use the Cohen-Lenstra-Martinet heuristics for class groups to construct number fields in which computing generators of principal ideals is intractable.
LA - eng
KW - class groups; public key cryptosystem; quadratic order; PIP-FS; Fiat-Shamir identification; principal ideals
UR - http://eudml.org/doc/248488
ER -

References

top
  1. [1] I. Biehl, J. Buchmann, Algorithms for quadratic orders. In: Mathematics of Computation 1943-1993: a half-century of computational mathematics, Vancouver 1993, W. Gautschi, Ed., vol. 48 of Proceedings of Symposia in Applied Mathematics, American Mathematical Society (1995), pp. 425-449. Zbl0839.11068MR1314882
  2. [2] I. Biehl, J. Buchmann, S. Hamdy, A. Meyer, A signature scheme based on the intractability of extracting roots. Tech. Rep. TI-1/00, Technische Universität Darmstadt, Fachbereich Informatik, 2000. http://www.informatik.tu-darmstadt.de/TI/Veroeffentlichung/TR/. Zbl1024.94009
  3. [3] I. Biehl, B. Meyer, C. Thiel, Cryptographic protocols based on real-quadratic A-fields (extended abstract). In Advances in Cryptology - ASIACRYPT '96, K. Kim and T. Matsumoto, Eds., vol. 1163 of Lecture Notes in Computer Science, Springer-Verlag (1996), pp. 15-25. Zbl1008.94545
  4. [4] Z.I. Borevich, I.R. Shafarevich, Number theory. Academic Press, New York (1966). Zbl0145.04902MR195803
  5. [5] G. BRASSARD, Ed., Advances in Cryptology - CRYPTO '89, vol. 435 of Lecture Notes in Computer Science, Springer-Verlag (1990). Zbl0719.00029MR1062221
  6. [6] J. Buchmann, On the computation of units and class numbers by a generalization of Lagrange's algorithm. Journal of Number Theory26 (1987), 8-30. Zbl0615.12001MR883530
  7. [7] J. Buchmann, it Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper. Habilitationsschrift (1987). 
  8. [8] J. Buchmann, S. Paulus, A one way function based on ideal arithmetic in number fields. In: Advances in Cryptology - CRYPTO '97, B. S. Kaliski, Ed., vol. 1294 of Lecture Notes in Computer Science, Springer-Verlag (1997), pp. 385-394. Zbl0888.94011
  9. [9] J. Buchmann, H.C. Williams, A key exchange system based on real quadratic fields. In Brassard [5], pp. 335-343. Zbl0722.68043MR1062244
  10. [10] D.A. Buell, Binary quadratic forms. Springer-Verlag, New York (1989). Zbl0698.10013MR1012948
  11. [11] M.V.D. Burmester, Y. Desmedt, F. Piper, M. Walker, A general zero-knowledge scheme. In: Advances in Cryptology - EUROCRYPT '89, J.-J. Quisquater and J. Vandewalle, Eds., vol. 434 of Lecture Notes in Computer Science, Springer-Verlag (1990), pp. 122-133. Zbl0732.68034MR1083958
  12. [12] D. Chaum, J.-H. Evertse, J. Van De Graaf, An improved protocol for demonstrating posession of discrete logarithms and some generalizations. In: Advances in Cryptology- EUROCRYPT '87, D. Chaum and W. L. Price, Eds., vol. 304 of Lecture Notes in Computer Science, Springer-Verlag (1988), pp. 127-142. Zbl0647.94015
  13. [13] H. Cohen, J.W. Lenstra, JR., Heuristics on class groups of number fields. In: Number Theory, Noordwijkerhout1983, H. Jager, Ed., vol. 1068 of Lecture Notes in Mathematics.Springer-Verlag (1984), pp. 33-62. Zbl0558.12002MR756082
  14. [14] H. Cohen, J. Martinet, Class groups of number fields: numerical heuristics. Mathematics of Computation48 (1987), 123-137. Zbl0627.12006MR866103
  15. [15] H. Cohen, J. Martinet, Étude heuristique des groupes de classes des corps de nombres. Journal für die reine und angewandte Mathematik404 (1990), 39-76. Zbl0699.12016MR1037430
  16. [16] H. Cohen, J. Martinet, Heuristics on class groups: Some good primes are not too good. Mathematics of Computation63 (1994), 329-334. Zbl0827.11067MR1226813
  17. [17] A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems. In: Advances in Cryptology - CRYPTO '86 (1987), A. M. Odlyzko, Ed., vol. 263 of Lecture Notes in Computer Science, Springer-Verlag, pp. 186-194. Zbl0636.94012MR907087
  18. [18] L.C. Guillou, J.-J. Quisquater, A practical zero-knowledge protocol fitted to security microprocessors minimizing both transmission and memory. In: Advances in Cryptology - EUROCRYPT '88 (1988), C. G. Günther, Ed., vol. 330 of Lecture Notes in Computer Science, Springer-Verlag, pp. 123-128. 
  19. [19] S. Hamdy, B. Möller, Security of cryptosystems based on class groups of imaginary quadratic orders. In: Advances in Cryptology - ASIACRYPT 2000 (2000), T. Matsumoto, Ed., Lecture Notes in Computer Science, Springer-Verlag. To appear. Zbl0974.94012MR1864334
  20. [20] E. Hecke, Vorlesungen über die Theorie der Algebraischen Zahlen. Leipzig (1923). Zbl49.0106.10JFM49.0106.10
  21. [21] M.J. Jacobson, JR., Subexponential Class Group Computation in Quadratic Orders. PhD thesis, Technische UniversitätDarmstadt, Fachbereich Informatik, Darmstadt, Germany, 1999. 
  22. [22] LiDIA - a C++ library for computational number theory. http://www.informatik.tu-darmstadt.de/TI/LiDIA/. The LiDIA Group. Zbl0828.11076
  23. [23] J.E. Littlewood, On the class number of the corpus P(√-k). Proceedings of the London Mathematical Society 2nd series 27 (1928), 358-372. Zbl54.0206.02JFM54.0206.02
  24. [24] A.J. Menezes, P.C. Van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography. CRC Press (1997). Zbl0868.94001MR1412797
  25. [25] R.A. Mollin, H.C. Williams, Computation of the class number of a real quadratic field. Utilitas Mathematica41 (1992), 59-308. Zbl0757.11036MR1162532
  26. [26] G. Poupard, J. Stern, Security analysis of a practical "on the fly" authentication and siganture generation. In: Advances in Cryptology - EUROCRYPT '98 (1998), K. Nyberg, Ed., vol. 1403 of Lecture Notes in Computer Science, Springer-Verlag, pp. 422-436. Zbl0929.68061
  27. [27] R. Scheidler, J. Buchmann, H.C. Williams, A key-exchange protocol using real quadratic fields. Journal of Cryptology7 (1994), 171-199. Zbl0816.94018MR1286662
  28. [28] C.P. Schnorr, Efficient identification and signatures for smart cards. In: Brassard [5], pp. 239-252. Zbl0722.68050MR1062237
  29. [29] U. Vollmer, Asymptotically fast discrete logarithms in quadratic number fields. In: Algorithmic Number Theory, ANTS-IV (2000), W. Bosma, Ed., vol. 1838 of Lecture Notes in Computer Science, Springer-Verlag, pp. 581-594. Zbl1032.11064MR1850635
  30. [30] H.C. Williams, M.C. Wunderlich, On the parallel generation of the residues for the continued fraction factoring algorithm. Mathematics of Computation48 (1987), 405-423. Zbl0617.10005MR866124

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.