Cryptography based on number fields with large regulator
Journal de théorie des nombres de Bordeaux, Tome 12 (2000) no. 2, pp. 293-307.

Nous introduisons une variante du protocole de signature et d'identification de Fiat-Shamir, basée sur la difficulté pratique qu'il y a à calculer des générateurs des idéaux principaux dans les corps de nombres. Nous montrons en outre comment utiliser les heuristiques de Cohen-Lenstra-Martinet pour les groupes de classes dans le but de construire des corps de nombres dans lesquels le calcul de générateurs des idéaux principaux est encore hors d'atteinte.

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.

@article{JTNB_2000__12_2_293_0,
     author = {Buchmann, Johannes and Maurer, Markus and M\"oller, Bodo},
     title = {Cryptography based on number fields with large regulator},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {293--307},
     publisher = {Universit\'e Bordeaux I},
     volume = {12},
     number = {2},
     year = {2000},
     mrnumber = {1823187},
     zbl = {0999.94029},
     language = {en},
     url = {http://archive.numdam.org/item/JTNB_2000__12_2_293_0/}
}
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
SP  - 293
EP  - 307
VL  - 12
IS  - 2
PB  - Université Bordeaux I
UR  - http://archive.numdam.org/item/JTNB_2000__12_2_293_0/
LA  - en
ID  - JTNB_2000__12_2_293_0
ER  - 
%0 Journal Article
%A Buchmann, Johannes
%A Maurer, Markus
%A Möller, Bodo
%T Cryptography based on number fields with large regulator
%J Journal de théorie des nombres de Bordeaux
%D 2000
%P 293-307
%V 12
%N 2
%I Université Bordeaux I
%U http://archive.numdam.org/item/JTNB_2000__12_2_293_0/
%G en
%F JTNB_2000__12_2_293_0
Buchmann, Johannes; Maurer, Markus; Möller, Bodo. Cryptography based on number fields with large regulator. Journal de théorie des nombres de Bordeaux, Tome 12 (2000) no. 2, pp. 293-307. http://archive.numdam.org/item/JTNB_2000__12_2_293_0/

[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. | MR | Zbl

[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/.

[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. | Zbl

[4] Z.I. Borevich, I.R. Shafarevich, Number theory. Academic Press, New York (1966). | MR | Zbl

[5] G. BRASSARD, Ed., Advances in Cryptology - CRYPTO '89, vol. 435 of Lecture Notes in Computer Science, Springer-Verlag (1990). | MR | Zbl

[6] J. Buchmann, On the computation of units and class numbers by a generalization of Lagrange's algorithm. Journal of Number Theory 26 (1987), 8-30. | MR | Zbl

[7] J. Buchmann, it Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper. Habilitationsschrift (1987).

[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. | Zbl

[9] J. Buchmann, H.C. Williams, A key exchange system based on real quadratic fields. In Brassard [5], pp. 335-343. | MR | Zbl

[10] D.A. Buell, Binary quadratic forms. Springer-Verlag, New York (1989). | MR | Zbl

[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. | MR | Zbl

[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. | Zbl

[13] H. Cohen, J.W. Lenstra, Jr., Heuristics on class groups of number fields. In: Number Theory, Noordwijkerhout 1983, H. Jager, Ed., vol. 1068 of Lecture Notes in Mathematics. Springer-Verlag (1984), pp. 33-62. | MR | Zbl

[14] H. Cohen, J. Martinet, Class groups of number fields: numerical heuristics. Mathematics of Computation 48 (1987), 123-137. | MR | Zbl

[15] H. Cohen, J. Martinet, Étude heuristique des groupes de classes des corps de nombres. Journal für die reine und angewandte Mathematik 404 (1990), 39-76. | MR | Zbl

[16] H. Cohen, J. Martinet, Heuristics on class groups: Some good primes are not too good. Mathematics of Computation 63 (1994), 329-334. | MR | Zbl

[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. | MR | Zbl

[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] 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. | MR | Zbl

[20] E. Hecke, Vorlesungen über die Theorie der Algebraischen Zahlen. Leipzig (1923). | JFM

[21] M.J. Jacobson, Jr., Subexponential Class Group Computation in Quadratic Orders. PhD thesis, Technische Universität Darmstadt, Fachbereich Informatik, Darmstadt, Germany, 1999.

[22] LiDIA - a C++ library for computational number theory. http://www.informatik. tu-darmstadt . de/TI/LiDIA/. The LiDIA Group.

[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. | JFM

[24] A.J. Menezes, P.C. Van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography. CRC Press (1997). | MR | Zbl

[25] R.A. Mollin, H.C. Williams, Computation of the class number of a real quadratic field. Utilitas Mathematica 41 (1992), 59-308. | MR | Zbl

[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. | Zbl

[27] R. Scheidler, J. Buchmann, H.C. Williams, A key-exchange protocol using real quadratic fields. Journal of Cryptology 7 (1994), 171-199. | MR | Zbl

[28] C.P. Schnorr, Efficient identification and signatures for smart cards. In: Brassard [5], pp. 239-252. | MR | Zbl

[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. | MR | Zbl

[30] H.C. Williams, M.C. Wunderlich, On the parallel generation of the residues for the continued fraction factoring algorithm. Mathematics of Computation 48 (1987), 405-423. | MR | Zbl