An application of algebraic geometry to encryption: tame transformation method. (English) Zbl 1058.94012

Moh, Tzuong Tsieng

Rev. Mat. Iberoam. 19, No. 2, 667-685 (2003).

The author employs the notion of tame transformations to produce a public-key cryptosystem having algebraic geometric notions at its foundation. Unfortunately, the paper suffers for rather poor use of the English language.

Reviewer: Richard A. Mollin (Calgary)

MSC:

94A60	Cryptography
14R10	Affine spaces (automorphisms, embeddings, exotic structures, cancellation problem)
68P25	Data encryption (aspects in computer science)

Keywords:

tame ramification; public-key cipher; cryptology; error detection

References:

[1]	Abhyankar, S. S. and Moh, T.: Embeddings of the line in the plane. J. Reine Angew. Math. 276 (1975), 148-166. · Zbl 0332.14004
[2]	Bajaj, C., Garrity, T. and Warren, J.: On the Application of Multi- Equational Resultants. Purdue University, Dept of C. S. Technical Report CSD-TR-826, 1988.
[3]	Bass, H., Connell, E. H. and Wright, D.L.: The Jacobian conjecture: reduction of degree and formal expansion of the inverse. Bull. Amer. Math. Soc. 7 (1983), no. 2, 287-330. · Zbl 0539.13012 · doi:10.1090/S0273-0979-1982-15032-7
[4]	Berlekamp, E. R.: Factoring polynomials over finite fields. Bell System Tech. J. 46 (1967), 1853-1859. · Zbl 0166.04901
[5]	Brandstrom, H.: A public-key cryptosystem based upon equations over a finite field. Cryptologia 7 (1983), 347-358. · Zbl 0537.94014 · doi:10.1080/0161-118391858071
[6]	Brent, R. and Kung, H.: Fast Algorithms for Manipulating Formal Power Series. J. Assoc. Comput. Mach. 25 (1978), no. 4, 581-595. · Zbl 0388.68052 · doi:10.1145/322092.322099
[7]	Cohen, H.: A Course in Computational Algebraic Number Theory. Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[8]	Courtois, N., Shamir, A., Patarin, J. and Klimov, A.: Efficient al- gorithms for solving overdefined systems of multivariate polynomial equa- tions. In Advances in cryptology -EUROCRYPT 2000 (Bruges), 392-407. Lecture Notes in Comput. Sci. 1807, Springer, Berlin, 2000. T. Moh · Zbl 1082.94514
[9]	Canny, John F.: Complexity of Robot Motion Planning. The MIT Press, Cambridge, Massachusetts, 1988. · Zbl 0668.14016
[10]	Dickerson, M.: The inverse of an Automorphism in Polynomial Time. J. Symbolic Comput. 13 (1992), 209-220. · Zbl 0805.13006 · doi:10.1016/S0747-7171(08)80090-9
[11]	Von zur Gathen, J.: Functional decomposition of polynomials: the tame case. J. Symbolic Comput. 9 (1990), 281-299. · Zbl 0716.68053 · doi:10.1016/S0747-7171(08)80014-4
[12]	Von zur Gathen, J.: Functional decomposition of polynomials: the wild case. J. Symbolic Comput. 10 (1990), 437-452. · Zbl 0722.12003 · doi:10.1016/S0747-7171(08)80054-5
[13]	Goubin, L. and Courtois, N. T.: Cryptanalysis of the TTM cryptosys- tem. In Advances in cryptology -ASIACRYPT 2000 (Kyoto), 44-57. Lec- ture Notes in Comput. Sci. 1976, Springer, Berlin, 2000. · Zbl 0980.94017
[14]	Imai, H. and Matsumoto, T.: Algebraic methods for constructing asym- metric cryptosystems. In Algebraic algorithms and error correcting codes (Grenoble, 1985), 108-119. Lecture Notes in Comput. Sci. 229, Springer, Berlin, 1986.
[15]	Van der Kulk, W.: On polynomial rings in two variables, Nieuw Arch. Wiskunde (3) 1 (1953), 33-41. · Zbl 0050.26002
[16]	Lidl, R. and Niederreiter, H.: Finite fields. Encyclopedia of Mathe- matics and its Applications 20. Addison-Wesley Pub. Co., Reading, Mas- sachusetts, 1983.
[17]	Lidl, R.: On cryptosystems based on polynomials and finite fields. In Advances in cryptology (Paris, 1984), 10-15. Lecture Notes in Comput. Sci. 209, Springer, Berlin, 1985. · Zbl 0596.94017 · doi:10.1007/3-540-39757-4_2
[18]	Lucier, B.: Cryptography, Finite Fields, and AltiVec. www.simtech.org/ apps/group public/download.php/22/Cryptography.pdf
[19]	Moh, T.: On the Classification Problem of Embedded Lines in Character- istic p. In Algebraic Geometry and Commutative Algebra (in honor of M. Nagata), vol I, 267-280, Kinokuniya, Kyoto, Japan, 1988.
[20]	Moh, T.: A Public Key System with Signature and Master Key Functions. Comm. Algebra 27 (1999), no. 5, 2207-2222. · Zbl 0933.94022 · doi:10.1080/00927879908826559
[21]	Moh, T.: A Fast Public Key System With Signature And Master Key Functions. In Cryptographic Techniques and E-Commerce, Proceedings of the 1999 International Workshop on Cryptographic Techniques and E- Commerce (CrypTEC ’99). City University of Hong Kong Press, July, 1999. · Zbl 0933.94022 · doi:10.1080/00927879908826559
[22]	Moh, T.: On the Method of XL and its Inefficiency against TTM. http://www.usdsi.com/ttm.html.
[23]	Moh, T.: On the the Goubin-Courtois Attack on TTM. “Cryptology ePrint Archive”, http://eprint.iacr.org/2001/072 . A copy can also be ob- tained at http://www.usdsi.com/ttm.html. 685
[24]	Nagata, M: On the automorphism group of K[X, Y ]. Lectures in Mathe- matics 5. Kinokuniya, Tokyo, Japan, 1972. · Zbl 0306.14001
[25]	Niederreiter, H.: New deterministic factorization algorithms for polyno- mials over finite fields. In Finite fields: theory, applications, and algorithms (Las Vegas, NV, 1993), 251-268, Contemp. Math. 168, Amer. Math. Soc., Providence, RI, 1994. · Zbl 0822.11083
[26]	Patarin, J.: Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt ’88. In Advances in cryptology -CRYPTO ’95 (Santa Bar- bara, CA, 1995), 248-261. Lecture Notes in Comput. Sci. 963, Springer, Berlin, 1995. · Zbl 0868.94025
[27]	Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polyno- mials (IP): two new families of asymmetric algorithms. In Advances in cryp- tology -EUROCRYPT 1996 (Zaragoza), 33-48. Lecture Notes in Comput. Sci. 1070 Springer-Verlag, 1996. · Zbl 1301.94125 · doi:10.1007/3-540-68339-9_4
[28]	Rivest, R. L., Shamir, A. and Adleman, L. M.: A Method for Ob- taining Digital Signatures and Public Key Cryptosystems. Comm. ACM 21 (1978), no. 2, 120-126. · Zbl 0368.94005 · doi:10.1145/359340.359342