Abstract
This paper, originally presented at CRYPTO 2000, marks a significant milestone in the field of non-commutative cryptography. By leveraging the mathematical difficulty of the Conjugacy Search Problem (CSP) in braid groups and the existence of efficient canonical form algorithms, the authors propose a faster alternative to traditional number-theoretic public-key systems like RSA and ECC.
Introduction
Most established Public-Key Cryptosystems (PKCs) rely on the difficulty of factoring large integers or computing discrete logarithms. However, the cryptographic community has long sought "Plan B" alternatives—systems based on entirely different mathematical foundations. This is important for diversity in security and as a hedge against potential breakthroughs in number theory or the eventual rise of quantum computing.
Previous attempts to use combinatorial group theory for cryptography often failed due to the "Word Problem"—the difficulty in determining if two different-looking sequences of operations represent the same group element—and poor computational efficiency. The authors address these gaps by showing that braid groups possess a "canonical form" that can be computed very quickly, making them ideal for practical computer implementation.
The Braid Group and Generators
The core of the paper revolves around the $n$-strand braid group ($B_n$). Imagine $n$ strings hanging from a bar; a braid is formed by twisting these strings around each other. The group is generated by elementary braids $\sigma_i$, where the $i$-th strand passes over the $(i+1)$-th strand.
The authors utilize a clever structural property of braid groups involving commuting subgroups. They define two subgroups:
- $LB_\ell$ (Left Braid): Braids involving only the leftmost $\ell$ strands.
- $RB_r$ (Right Braid): Braids involving only the rightmost $r$ strands.
If these two sets of strands do not overlap (i.e., $\ell + r \le n$), then any braid $a$ from the left group and any braid $b$ from the right group will commute ($ab = ba$). This commutativity within a larger non-commutative group is the engine of their key exchange.
Cryptographic Protocols
The system supports both key agreement and public-key encryption:
- Key Agreement: Similar to Diffie-Hellman, Alice and Bob pick a public braid $x$. Alice chooses a secret $a \in LB_\ell$ and sends $y_1 = axa^{-1}$. Bob chooses a secret $b \in RB_r$ and sends $y_2 = bxb^{-1}$. Because $a$ and $b$ commute, they can both arrive at the same shared secret: $K = ay_2a^{-1} = b y_1 b^{-1}$.
- Public-Key Encryption: The authors extend this logic into an ElGamal-like encryption scheme using a hash function to map braid elements to bitstrings.
Security and Performance
The security of the system rests on the Conjugacy Search Problem (CSP): given $x$ and $axa^{-1}$, it is computationally "hard" to find $a$. In the braid group, this problem is believed to be much harder than the discrete log problem in finite fields. The security parameter $n$ (number of strands) provides a massive search space. For modest parameters ($n=90, p=12$), the hardness of a brute force attack is estimated at $2^{1863}$, far beyond the reach of any current computer.
Performance is a major advantage of this system. The authors rely on the Birman-Ko-Lee algorithm to convert any "tangled" braid into a unique, simplified tuple of permutations. Experimental benchmarks on a Pentium III 450MHz processor showed that converting a braid with 50 strands to its canonical form took only 0.0112 seconds. Encryption and decryption are $O(p^2 n \log n)$, which is very competitive compared to the modular exponentiations required by RSA.
Conclusion
While the paper marks a milestone in non-commutative cryptography, some challenges remain. A digital signature scheme based on braid groups was noted as an open challenge at the time of publication. Additionally, the security relies on heuristic assumptions about the hardness of specific instances of the CSP. While braid-based systems generally fare better than RSA against quantum algorithms, their long-term resistance to all quantum attacks remains a subject of ongoing research.
Summary updated