Introduction to Cryptography

We wish to discuss methods for securely passing messages between people -- Alice wants to communicate with Bob in private, and Eve wants to eavesdrop on their communications. We give a very brief introduction to the two basic systems of encryption: symmetric key and public key. More details can be found in any standard text.

Symmetric Key

A and B have the same secret key K, known to only A and B. A uses K to encrypt the message which is sent to B, and then B decrypts the message also using K. This key must be agreed upon in advance in private.

A simple example of symmetric key encryption: Suppose that K=0110 and A wants to send the message m=1010 to B. Then A encrypts the message as  (where  is the XOR function) and sends the ciphertext, c, to B.  B deciphers this by computing . Here the encryption (and decryption) algorithm is XOR-ing with the secret key. Note that this example of an encryption algorithm is very insecure, but it demonstrates the idea of symmetric key encryption.

Public Key

A and B have two keys each – a public key and a private key. The public keys are published (via the internet for example) and are available to anyone. The private keys are known only to the owner of the key.  So unlike the symmetric key system, A and B do not have to agree on a key privately in advance. A uses B’s public key to encrypt any message to be sent to B. B uses his private key to decrypt this ciphertext.

The cryptosystems using braid groups are examples of public key cryptosystems. 

Motivation for Braid Group Cryptography

Most existing cryptosystems are based on solving problems in finite fields. For example, exponentiation in  is easy, but the inverse process is very difficult. Take  and the exponent e=3. It is easy to compute (mod 7) for any , but given say 6 (mod 7), find a such that (mod 7) is hard (in the same sense that there aren’t any quick algorithms to solve the problem). Of course, 7 is a very small prime number, and a brute force solution is actually easy, but for large primes attacking this problem by brute force on a computer is not feasible.  The Diffie-Hellman key exchange protocol is based on a sophisticated version of this problem. Since there are many people trying to devise clever ways of attacking such systems, one idea is to devise cryptosystems based on solving problems in non-abelian groups (such as the braid group).