Generic Complexity

Each of the major public-key protocols used in e-commerce today depends on a procedure which is easy to do but difficult to undo. In RSA, the most widely used cryptosystem, the procedure is multiplying two large primes; and the inverse procedure is factoring a large integer into a product of primes. Factoring has long been thought to be hard, but this is not known for sure. If it turns out that there is an easy way to factor, then RSA will not be secure.

The same consideration applies to the new cryptosystems proposed as improvements on RSA. In each case there is a procedure is relatively easy and the inverse procedure is supposed to be very difficult. However, up till now there has been no suitable way to measure the difficulty.

For example public key cryptosystems [1,2,6] based on the so-called conjugacy search problem and its generalizations from combinatorial group theory have generated interest (see the surveys [4,8,9]). These ideas have been implemented in a cryptosystem which has been patented and is in commercial use. However, a recently discovered heuristic method for solving the inverse procedure shows that this cryptosystem is not secure [7].

It would be desirable to have a systematic way of testing the difficulty procedures before they are incorporated into cryptosystems. The usual approaches to evaluating the difficulty of a problem employ worst case complexity and average complexity. But a problem can have very high worst case complexity and yet be extremely easy almost all the time. The same consideration applied to average case complexity.

A suitable notion of complexity, generic complexity, emerged recently in combinatorial group theory. Generic complexity might be a better way of measuring the complexity of algebraic problems and hence the security of cryptosystems.

Click here for a more detailed discussion.

References:

1. M. Anshel, et.al., Method and apparatus for cryptographically secure algebraic key establishment protocols based on monoids (United States Patent 6,493,449, December 10, 2002).
2. I. Anshel, M. Anshel, D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett. 6 (1999), 287--291.
3. A.Borovik, A. G. Myasnikov, and V.Remeslennikov, Multiplicative measures on free groups, Internat. J. Algebra and Comput. 13 (2003), 705--732.
4. P. Dehornoy, Braid-based cryptography, Contemp. Math., Amer. Math. Soc., to appear.
5. I.Kapovich, A.Myasnikov, P.Schupp and V.Shpilrain, Generic-case complexity, decision problems in group theory and random walks, J. Algebra 264 (2003), 665--694.
6. K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang, C. Park, New public-key cryptosystem using braid groups, Advances in cryptology---CRYPTO 2000 (Santa Barbara, CA), 166--183, Lecture Notes in Comput. Sci. 1880, Springer, Berlin, 2000.
7. A. Myasnikov, V. Shpilrain, A. Ushakov, A practical attack on some braid group based cryptographic protocols, preprint.
8. V. Shpilrain, Assessing security of some group based cryptosystems, Contemp. Math., Amer. Math. Soc., to appear.
9. V. Shpilrain and G. Zapata, Combinatorial group theory and public key cryptography, preprint.