Cryptography based on number fields with large regulator
Johannes Buchmann ; Markus Maurer ; Bodo Möller
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},
     doi = {10.5802/jtnb.281},
     zbl = {0999.94029},
     mrnumber = {1823187},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.281/}
}
Johannes Buchmann; Markus Maurer; Bodo Möller. Cryptography based on number fields with large regulator. Journal de Théorie des Nombres de Bordeaux, Tome 12 (2000) no. 2, pp. 293-307. doi : 10.5802/jtnb.281. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.281/

[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 1314882 | Zbl 0839.11068

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

[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 1008.94545

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

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

[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 883530 | Zbl 0615.12001

[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 0888.94011

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

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

[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 1083958 | Zbl 0732.68034

[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 0647.94015

[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 756082 | Zbl 0558.12002

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

[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 1037430 | Zbl 0699.12016

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

[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 907087 | Zbl 0636.94012

[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 1864334 | Zbl 0974.94012

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

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

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

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

[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 0929.68061

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

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

[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 1850635 | Zbl 1032.11064

[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 866124 | Zbl 0617.10005