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
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.
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).
I. Anshel, M. Anshel, D. Goldfeld, An algebraic method for
public-key cryptography, Math. Res. Lett. 6 (1999), 287--291.
A.Borovik, A. G. Myasnikov, and V.Remeslennikov,
Multiplicative measures on free groups, Internat. J. Algebra
and Comput. 13 (2003), 705--732.
P. Dehornoy, Braid-based cryptography, Contemp. Math., Amer.
Math. Soc., to appear.
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.
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.
A. Myasnikov, V. Shpilrain, A. Ushakov, A practical attack on some
braid group based cryptographic protocols, preprint.
V. Shpilrain, Assessing security of some
group based cryptosystems, Contemp. Math., Amer. Math. Soc., to
V. Shpilrain and G. Zapata, Combinatorial
group theory and public key cryptography, preprint.