On application of class groups of ideals of quadratic fields to the construction of public key cryptosystems

M. M. Glukhov

Matematičeskie voprosy kriptografii, Tome 1 (2010) no. 1, pp. 23-54

Résumé

The paper contains a brief survey on cryptosystems based on imaginary and real quadratic fields.

Bibliographie

[1] Borevich Z. I., Shafarevich I. R., Teoriya chisel, Nauka, M., 1964 | MR | Zbl

[2] Gekke E., Lektsii po teorii algebraicheskikh chisel, GITTL, M., 1940

[3] Glukhov M. M., Pichkur A. B., Metody algebraicheskoi teorii chisel v kriptografii, M., 1998 | Zbl

[4] Ankeny N. C., Artin E., Chowla S., “The class-number of real quadratic number fields”, Ann. Math., 56:3 (1952), 479–493 | DOI | MR | Zbl

[5] Cohen H., A course in computational algebraic number theory, Springer, Berlin, 1993 | MR

[6] Cohen H., Diaz F., Olivier M., “Computing ray class groups, conductors and discriminants”, ANTS-II, Lect. Notes Comp. Sci., 1122, 1996, 49–57 | MR | Zbl

[7] Kuroda S., “Uber die klassenzahlen algebraischer zahlkorper”, Nagoya Math. J., 1 (1950), 1–10 | MR | Zbl

[8] Lagarias J. C., “Worst-case complexity bounds for algorithms in theory of integral quadratic forms”, J. Algorithms, 1 (1980), 142–186 | DOI | MR | Zbl

[9] Pohst M., Zassenhaus H., Algorithmic algebraic number theory, Cambridge Univ. Press, Cambridge, 1989 | MR | Zbl

[10] Pohst M., Computational algebraic number theory, Birkhäuser, 1993 | MR | Zbl

[11] Stefenhagen P., “The arithmetic of number rings”, MSRI Publ., 44 (2008), 209–266 | MR

[12] van der Poorten A. J., “A note on NUCOMP”, Math. Comp., 72 (2003), 1935–1946 ; Atkin A. O. L., “Letter to Shanks on the programs NUDUPL and NUCOMP” (1998) | DOI | MR | Zbl

[13] Biehl J., Buchmann J. A., “Algorithms for quadratic orders”, Proc. Symp. Appl. Math., 48 (1994), 425–449 | MR | Zbl

[14] Biehl J., Buchmann J. A., Thiel Ch., “Cryptographic protocols based on discrete logarithms in real-quadratic orders”, CRYPTO'94, Lect. Notes Comp. Sci., 839, 1994, 56–60 | Zbl

[15] Biehl J., Buchmann J. A., “An analysis of the reduction algorithms for binary quadratic forms”: P. Engel and H. Syta, Voronois̀ Impact on Modern Science, v. 1, Kyiv Institute of Math., National Acad. Sci., Kyiv, 1998 | Zbl

[16] Biehl J., Buchmann J. A., Hamdy S., Meyer A., Cryptographic protocols based on the intractability of extracting roots and computing discrete logarithms, Tech. Rep., Technology Univ., Darmstadt, 1999

[17] Biehl J., Buchmann J. A., Hamdy S., Meyer A., “A signature scheme based on the intractability of computing roots”, Des., Codes and Cryptography, 25 (2002), 223–236 | DOI | MR | Zbl

[18] Biehl J., Meyer B., Thiel Ch., “Cryptology protocol based on real-quadratic Afields”, ASIACRYPT'96, Lect. Notes Comp. Sci., 1163, 1996, 15–25 | Zbl

[19] Biehl J., Paulus S., Takagi T., An efficient undeniable signature scheme based on non-maximal imaginary quadratic orders, Tech. Rep., Univ. Technology, Darmstadt, 1999

[20] Buchmann J., “On the computation of units and class numbers by a generalization of Lagrange algorithms”, J. Number Theory, 26 (1987), 8–30 | DOI | MR | Zbl

[21] Buchmann J., “Number theoretic algorithms and cryptology”, Proc. FCT'91, Lect. Notes Comp. Sci., 529, 1991, 16–21 | MR | Zbl

[22] Buchmann J., Dullmann S., “On the computation of discrete logarithms in class groups”, CRYPTO 90, Lect. Notes Comp. Sci., 537, 1991, 134–139 | Zbl

[23] Buchmann J., Dullmann S., “A probabilistic class group and regulator algorithm and its implementation”, Computational number theory, Springer, Berlin, New York, 1991, 53–72 | MR

[24] Buchmann J., Dullman H., Williams H. C., “On the complexity and efficiency a new key exchange system”, EUROCRYPT 89, Lect. Notes Comp. Sci., 434, 1990, 597–616 | MR

[25] Buchmann J., Maurer M., Möller B., Cryptography based on number fields with large regulator, Tech. Rep. No TI-5, 2000, 1–12 | MR

[26] Buchmann J., Paulus S., “A one way function based on ideal arithmetic in number fields”, CRYPTO 97, 1997, 385–394 | Zbl

[27] Buchmann J., Scheidler R., Williams H. C., “A key exchange system based on real quadratic fields”, CRYPTO 89, Lect. Notes Comp. Sci., 435, 1990, 335–343 | MR | Zbl

[28] Buchmann J., Williams H. C., “A key exchange protocol using real quadratic fields”, J. Cryptology, 7:3 (1994), 171–199 | DOI | MR | Zbl

[29] Buchmann J., Williams H. C., “A key exchange system based on imaginary quadratic fields”, J. Cryptology, 1 (1988), 107–118 | DOI | MR | Zbl

[30] Dullman S., Ein neues Verfahren zum offentlichen Schusselaustausch, Master thesis, Dusseldorf Univ. Press, Dusseldorf, 1988

[31] Estes D., Adleman L. M., Kompella K., McCurley K. S., Miller G. L., “Breaking the Ong–Schnorr–Shamir signature scheme for quadratic number fields”, CRYPTO'1985, Lect. Notes Comp. Sci., 218, 1986, 3–13 | MR | Zbl

[32] Hafner J. L., McCurley K. S., “A rigorous subexponential algorithm for computation of class groups”, J. Amer. Math. Soc., 2 (1989), 837–850 | MR | Zbl

[33] Hamdy S., The key-length of DL-based cryptosystems in class group, Manuscript, 1999 | Zbl

[34] Hamdy S., Maurer M., Feige–Fiat–Shamir identification based on real quadratic fields, Technischer Bericht TU-Darmstadt, 2000

[35] Hamdy S., Moller B., “Security of cryptosystems based on class groups of imaginary quadratic orders”, ASIACRYPT'2000, Lect. Notes Comput. Sci., 1976, 2000, 234–247 | MR | Zbl

[36] Hamdy S., Performance and security of cryptosystems based on class groups of imaginary quadratic orders, Manuscript, 2000

[37] Hartmann M., Paulus S., Takagi T., “NICE – New Ideal Coset Encryption”, CHES'99, Lect. Note. Comp. Sci., 1717, 1999, 341–352

[38] Hühnlein D., A survey of cryptosystems based on imaginary quadratic orders, , 2000, 15 pp. http://citeseerx.ist.psu.edu/

[39] Hühnlein D., Quadratic orders for NESSIE – overview and parameter sizes of three public key families, , 2001, 19 pp. http://citeseerx.ist.psu.edu/

[40] Hühnlein D., “Efficient implementation of cryptosystems based on non-maximal imaginary quadratic orders”, Lect. Notes Comp. Sci., 1758, 2000, 147–162 | MR | Zbl

[41] Hühnlein D., Jacobson M. J., Paulus S., Takagi T., “A cryptosystem based on non-maximal quadratic orders with fast decryption”, EUROCRYPT'98, Lect. Notes Comp. Sci., 1403, 1998, 294–307 | MR | Zbl

[42] Hühnlein D., Merkle J., “An efficient NICE-Schnorr-type cryptosystem”, Lect. Notes Comp. Sci., 1751, 2000, 328–339

[43] Hühnlein D., Meyer A., Takagi T., “Rabin and RSA analogues based on nonmaximal imaginary quadratic orders”, Proc. CICS'98, 1998, 221–240

[44] Hühnlein D., Paulus S., “On the implementation of cryptosystems based on real quadratic number fields”, 7th Ann. Workshop Select. Areas Cryptography, Lect. Notes Comp. Sci., 2012, 2001, 288–302 | MR | Zbl

[45] Hühnlein D., Takagi T., “Reduction logarithms in totally non-maximal quadratic orders to logarithms in finite fields”, ASIACRYPT'99, Lect. Notes Comp. Sci., 1716, 1999, 220–231

[46] Jacobson M. J.(Jr.), “Computing of discrete logarithms in quadratic orders”, J. Cryptology, 13:4 (2000), 437–492 | DOI | MR

[47] Jacobson M. J. (Jr.), Scheidler R., Williams H. C., “Efficient and security of a real quadratic field based-key exchange protocol”, Public-Key Cryptography and Comput. Number Theory, Berlin, 2001, 89–112 | MR | Zbl

[48] Jacobson M. J. (Jr.), Scheidler R., Williams H. C., “An improved real quadratic field based key exchange procedure”, J. Cryptology, 19:2 (2006), 211–239 | DOI | MR | Zbl

[49] Jacobson M. J. (Jr.), Sawilla R. E., Williams H. C., “Efficient ideal reduction in quadratic field based-key exchange protocol”, J. Comp. Sci., 1 (2006), 83–116 | MR | Zbl

[50] Jacobson M. J. (Jr.), Subexponential class group computations in quadratic orders, Ph.D. thesis, Darmstadt, 1999

[51] Kaplan P., Williams K. S., “The distance between ideals in the orders of a real quadratic field”, Enzeign. Math., 36:3–4, 321–358 | MR | Zbl

[52] McCurley K., “A key distribution system equivalent to factoring”, J. Cryptology, 1 (1988), 95–105 | DOI | MR | Zbl

[53] McCurley K., “Cryptology key distribution and computation in class groups”, Number Theory Appl., ser. C, 265 (1989), 459–479 | MR | Zbl

[54] Meyer A., Ein neues Identifications- und Signaturverfahren uber imaginarquadratischen Zahlkorpern, Master Thesis, University of Saarbrucken, Saarbrucken, 1997

[55] Mollin R. A., Williams H. C., “Computation of the class number of a real quadratic field”, Util. Math., 41 (1992), 59–308 | MR

[56] Oesterle J., “Nombre de classes des corps quadraticues imaginarires”, Soc. Math. De France, 1985, 309–323 | MR | Zbl

[57] Ong H., Schnorr C. P., Shamir A., “An efficient signature scheme based on quadratic forms”, Proc. 16th ACM Symp. Theory of Computing, 1984, 208–216

[58] Paulus S., “An algorithm of subexponential type computing the class group of quadratic orders over principal ideal domains”, Lect. Notes Comp. Sci., 1122, 1996, 243–257 | MR | Zbl

[59] Paulus S., Takagi T., “A new public-key cryptosystem over the quadratic order with quadratic decryption time”, J. Cryptology, 13 (2000), 263–272 | DOI | MR | Zbl

[60] Rickert N. W., “Efficient reduction of quadratic forms”, Computers and Math., Springer, N.Y., 1989, 135–139 | MR

[61] Sawilla R. E., Fast ideal arithmetic in quadratic fields, Master Thesis, Calgary Univ. Press, Calgary, 2004

[62] Scheidler R., Buchmann J., Williams H. C., “Implementation of a key exchange protocol using some real quadratic fields”, EUROCRYPT'90, Lect. Notes Comp. Sci., 473, 1991, 98–109 | MR | Zbl

[63] Scheidler R., Buchmann J., Williams H. C., “A key-exchange protocol using real quadratic fields”, J. Cryptology, 7 (1994), 171–199 | DOI | MR | Zbl

[64] Schielzeth D., Pohst M. E., “On real quadratic number fields suitable for cryptography”, J. Exper. Math., 14:2 (2005), 189–197 | MR | Zbl

[65] Schönhage A., “Fast reduction and composition of binary quadratic forms”, On Symbolic and Algebraic Computation, ACM, 1991, 128–133 | Zbl

[66] Schoof R. J., “Quadratic fields and factorization”, Computational Methods in Number Theory, Part II, Math. Centrum Tracts, Amsterdam, 1983, 235–286 | MR

[67] Seysen M., “A probabilistic factoring algorithm with quadratic forms of negative discriminant”, Math. Comp., 48 (1987), 737–780 | DOI | MR

[68] Shanks D., “Class number, a theory of factorization and genera”, Proc. Symp. Pure Math., 20, AMS, 1971, 415–440 | MR

[69] Shanks D., “The infrastructure of real quadratic fields and its application”, Proc. 1972 Number Theory Conf., Colorado, Boulder, 1973, 217–224 | MR

[70] Vollmer U., “Asymptotically fast discrete logarithms in quadratic fields”, ANTS'2000, Lect. Notes Comp. Sci., 1838, 2000, 581–594 | MR | Zbl

[71] Weber D., “Computing discrete logarithms with quadratic number rings”, EUROCRYPT'97, Lect. Notes Comp. Sci., 1233, 1997, 171–183 | MR

[72] Williams H., “A modification of the RSA public-key encryption procedure”, IEEE Trans. Inf. Theory, 26 (1980), 726–729 | DOI | MR | Zbl

[73] Williams H., “Some public-key crypto-functions as intractable as factorization”, Cryptologia, 9:3 (1985), 223–237 | DOI | MR | Zbl