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 -
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] 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] A signature scheme based on the intractability of extracting roots. Tech. Rep. TI-1/00, Technische Universität Darmstadt, Fachbereich Informatik, 2000. .
, , , ,[3] 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] 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] 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] it Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper. Habilitationsschrift (1987).
,[8] 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] A key exchange system based on real quadratic fields. In Brassard [5], pp. 335-343. | MR: 1062244 | Zbl: 0722.68043
, ,[10] Binary quadratic forms. Springer-Verlag, New York (1989). | MR: 1012948 | Zbl: 0698.10013
,[11] 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] 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] 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] Class groups of number fields: numerical heuristics. Mathematics of Computation 48 (1987), 123-137. | MR: 866103 | Zbl: 0627.12006
, ,[15] É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] Heuristics on class groups: Some good primes are not too good. Mathematics of Computation 63 (1994), 329-334. | MR: 1226813 | Zbl: 0827.11067
, ,[17] 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] 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] 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] Vorlesungen über die Theorie der Algebraischen Zahlen. Leipzig (1923). | JFM: 49.0106.10
,[21] 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] 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] Handbook of Applied Cryptography. CRC Press (1997). | MR: 1412797 | Zbl: 0868.94001
, , ,[25] Computation of the class number of a real quadratic field. Utilitas Mathematica 41 (1992), 59-308. | MR: 1162532 | Zbl: 0757.11036
, ,[26] 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] A key-exchange protocol using real quadratic fields. Journal of Cryptology 7 (1994), 171-199. | MR: 1286662 | Zbl: 0816.94018
, , ,[28] Efficient identification and signatures for smart cards. In: Brassard [5], pp. 239-252. | MR: 1062237 | Zbl: 0722.68050
,[29] 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] 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: