Protocols

Braid groups can be used in public key cryptography for the following protocols.

Key Exchange: Alice and Bob agree on a secret key over an insecure line. This can then be used in a symmetric key cryptosystem – this means that A and B use the same key to encrypt and decrypt messages.

Encryption and Decryption: A sends B a secret message using her secret key and his public key; B decrypts the message. In this protocol A and B do not have a common secret key – this type of encryption system is known as public key.

Authentication: B checks that the sender of the message is really A. This is for use in public key cryptosystems.

To define the protocols, we choose  and let be the subgroup of generated by  and   be the subgroup generated by  . These are the left and right subgroups of the braid group, where only the left k strings can cross in  (or right k strings  in ). Note that elements in and  commute (since one can just slide them past each other).

Key Exchange (Alice and Bob agree on a secret key over an insecure line)

·        A and B agree on a large even number n and a braid . This is public information – A and B agree on x via insecure channels.

·        A chooses a random braid  and sends B the braid .

·        B chooses a random braid and computes .

·        Now B sends A the braid 

·        A computes . Note that . Since a and b commute, we have

·        After the exchange A and B obtain the same key, K. This is the secret key that they will use in their communications.

·        A simple example using braids can be found on the Example of Key Exchange page.

Encryption and Decryption (A sends B a secret message using her secret key and his public key, B decrypts the message)

·        Parties agree on a large even number n and determine . This is public information – A and B agree on x via insecure channels.

·        Each party chooses a secret key from and publishes the conjugate of x with the secret key (e.g. A chooses  and publishes). The private key of A is a and the public key of A is (x,y).

·        Suppose B has private key b, and public key (x,z), where  .

·        If A wants to send a message m to B, she first chooses a random  and computes. Here note that everyone can see z since it is public information.

·        In order for anyone to send information to B, they use a “lock” to which only B has the “key” (the braid b is this key). Thus, A sends B the ciphertext (the locked message) which is the pair , where H is some hash function (this is a previously agreed upon one-way function from to , where k is a large number depending on n; basically this is a function that converts a braid to a sequence of 0’s and 1’s, is easy to compute, but it is difficult to recover the braid from the sequence of 0’s and 1’s.  denotes the XOR operation) .

·        To decrypt the message, B first conjugates the first part of A’s message with his own private key, b, which gives . Because , we have  and since , we have that . Hence B has actually obtained  without knowing what r was. Now B can compute  and XOR it with the second part of A’s message. Then B obtains the message m since

·         Note that since r is randomly chosen each time a message is sent, if A sends the same message to B more than once, the ciphertext will be different. This improves the security.

Authentication (B checks that the sender of the message is really A)

·        Parties agree on a large even number n and determine .

·        Now A and B have private keys  and  respectively.

·        They publish the pairs  and  respectively where  and .

·         A computes .

·        B computes , and we have that  since a’ and b’ commute .

·        Note that these are different keys to those used in the Encryption and Decryption protocol.

To incorporate the Encryption and Decryption protocol with the Authentication scheme, one can do the following:

·        A publishes the triple  and B publishes the triple , where x,y,z are as in the Encryption and Decryption protocol and  are as in the Authentication scheme.   The same x is used in both of the protocols.