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 = {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://www.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://www.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://www.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, Volume 12 (2000) no. 2, pp. 293-307. http://www.numdam.org/item/JTNB_2000__12_2_293_0/
[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 | Zbl
, ,[2] 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] 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] 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] 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] 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
, ,[9] A key exchange system based on real quadratic fields. In Brassard [5], pp. 335-343. | MR | Zbl
, ,[10] Binary quadratic forms. Springer-Verlag, New York (1989). | MR | Zbl
,[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 | Zbl
, , , ,[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
, , ,[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 | Zbl
, ,[14] Class groups of number fields: numerical heuristics. Mathematics of Computation 48 (1987), 123-137. | MR | Zbl
, ,[15] É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] Heuristics on class groups: Some good primes are not too good. Mathematics of Computation 63 (1994), 329-334. | MR | Zbl
, ,[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 | Zbl
, ,[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 | Zbl
, ,[20] Vorlesungen über die Theorie der Algebraischen Zahlen. Leipzig (1923). | JFM
,[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. http://www.informatik. tu-darmstadt . de/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
,[24] Handbook of Applied Cryptography. CRC Press (1997). | MR | Zbl
, , ,[25] Computation of the class number of a real quadratic field. Utilitas Mathematica 41 (1992), 59-308. | MR | Zbl
, ,[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
, ,[27] A key-exchange protocol using real quadratic fields. Journal of Cryptology 7 (1994), 171-199. | MR | Zbl
, , ,[28] Efficient identification and signatures for smart cards. In: Brassard [5], pp. 239-252. | MR | Zbl
,[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 | Zbl
,[30] On the parallel generation of the residues for the continued fraction factoring algorithm. Mathematics of Computation 48 (1987), 405-423. | MR | Zbl
, ,