Linearity of Arithmetica’s Algorithm

(work in progress by Goeffrey B. Milord of UPenn, and Mike Brenner of MITRE mikeb@mitre.org)

Bibliography

1. Anshel, I., Anshel, M., and Goldfeld, D., “A Linear Time Matrix Key Agreement Protocol Over Small Finite Fields” (proprietary: available from Arithmetica, Inc.).

2. Anshel, I., Anshel, M., Fischer, B., and Goldfeld, D., “New Key Agreement Protocols in Braid Group Cryptography” publicly available at http://link.springer.de/link/service/series/0558/papers/2020/20200013.pdf.

3. Anshel, I., Anshel, M., and Goldberg, G., “A Linear Time Matrix Key Agreement Protocol”, publicly available at http://www.ipam.ucla.edu/publications/cry2002/cry2002_dgoldfeld.pdf, and an earlier version was given out at the GT-1 Consortium Meeting.

Patent

> ------------------------------------------------------------------------

> United States Patent 6,493,449

> Anshel , et al. December 10, 2002

> ------------------------------------------------------------------------

> Method and apparatus for cryptographically secure algebraic key establishment

> protocols based on monoids

> Abstract

>

> The present invention is a method and apparatus for providing

> cryptographically secure algebraic key establishment protocols that use

> monoids and groups possessing certain algorithmic properties. Special fast

> algorithms associated with certain monoids and groups are used to optimize

> both key agreement and key transport protocols. The cryptographic security of

> the algorithms is based on the difficulty of solving the conjugacy problem in

> groups and other known hard algebraic problems. Braid groups and their

> associated algorithms are the basis for highly rapid key agreement and key

> transport protocols which employ modest computational resources.

> ------------------------------------------------------------------------

> Inventors: Anshel; Iris (Tenafly, NJ); Anshel; Michael M. (New York, NY);

> Goldfeld; Dorian (Tenafly, NJ)

> Assignee: Arithmetica, Inc. (Wilmington, DE)

> Appl. No.: 030935

> Filed: February 26, 1998

>

> Current U.S. Class: 380/30; 380/28; 380/285

> Intern'l Class: H04L 009/30

> Field of Search: 380/21,25,28,30,285

> ------------------------------------------------------------------------

Summary

Arithmetica, Inc. owns Patent 6,493,449 for braid group public key cryptography. That patent does not include a symmetric cryptographic algorithm for encryption or decryption.

Being based on braid groups, Arithmetica’s algorithm might assist the Community in seeking:

- Possible immunity from quantum computer attacks (because the Abelian stabilizer problem has been solved for quantum computers, but significant new math may be needed to develop a similar speed for the nonabelian stabilizer).

- Possible protection from some side-channel attacks (because braids use many small numbers instead of a small number of giant integers).

- Possible faster speed in generating and transmitting keys (Arithmetica’s algorithm is linear under the assumptions given in the papers above, and assuming that key generation does not have to be done on-line as in securing Chains of Commitment, and assuming that weak keys can be recognized and filtered out in linear time, and assuming that the authors make some improvements in the expression of the algorithm pointed out to them).