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

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.

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.

@article{JTNB_2000__12_2_293_0,
     author = {Johannes Buchmann and Markus Maurer and Bodo M\"oller},
     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/}
}
TY  - JOUR
TI  - Cryptography based on number fields with large regulator
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2000
DA  - 2000///
SP  - 293
EP  - 307
VL  - 12
IS  - 2
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.281/
UR  - https://zbmath.org/?q=an%3A0999.94029
UR  - https://www.ams.org/mathscinet-getitem?mr=1823187
UR  - https://doi.org/10.5802/jtnb.281
DO  - 10.5802/jtnb.281
LA  - en
ID  - JTNB_2000__12_2_293_0
ER  - 
%0 Journal Article
%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 https://doi.org/10.5802/jtnb.281
%R 10.5802/jtnb.281
%G en
%F JTNB_2000__12_2_293_0
Johannes Buchmann; Markus Maurer; Bodo Möller. Cryptography based on number fields with large regulator. Journal de Théorie des Nombres de Bordeaux, Volume 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

Cited by Sources: