Security and Attacks

Since the first braid cryptosystems were introduced, numerous attacks have been investigated. It seems that currently there is some doubt as to the realistic security of such systems (since for instance the conjugacy problem may not be as difficult as once thought). This is an extremely brief overview of the base problem security, the computational time required and possible attacks on the cyptosystems.

Security:

The security of these protocols is based on the hardness of the following problems:

· The Conjugacy Problem: Given two braids determine whether they are conjugate or not (that is whether there is an such that ).

· Conjugacy Search Problem: Given , find , such that .

Complexity:

The following table (from Ko et al.) gives the computational time required. Here n is the number of braid stands and p is the canonical length of the relevant braid.

Plaintext block	bits
Ciphertext block	bits
Encryption speed	operations
Decryption speed	operations
Private key length	bits
Public key length	bits
Hardness of brute force attack

Attacks:

The summit set and the conjugacy problem (finding good solutions to the conjugacy problem)
Linear representations (of the braid group as matrix groups)
Randomness (choice of random braids must not make the key trivial to find)
Contradictory security requirements.
Length attacks on the Commutator protocol (based on the length of the braid - we haven't discussed the Commutator protocol here yet- its part of the Anshel et al's braid group cryptosystem).