Friday, November 18, 2011

Advances in Public Key Cryptography


Public key encryption (also known as asymmetric key encryption) has been around for decades (since mid 1970s to be exact) and it has revolutionized secure communication without need for pre-shared keys. Much of the web (if not all) relies on public key encryption. For example, TLS uses public key encryption to establish a session key between a client and a server for securing internet traffic.


Let's take the traditional example of Alice and Bob who want to communicate securely and they haven't spoken to each other before. Alice generates a public and private key pair. She gives Bob the public key (and the world for that matter) and anyone that wants to securely transmit data to her uses the public key to encrypt messages. The encryption is said to be hard to invert (in a reasonable amount of time for modern computers) without the private key, which only Alice possesses. Thus, Bob can reliably send confidential messages by encrypting to Alice using her public key and guarantee that only she can read the message. Note that public key encryption in itself relies on an infrastructure (or PKI) to authenticate public keys so that someone malicious (let's call her Eve :-) cannot impersonate Alice to Bob. The earliest use cases of public key encryption was to securing email communication and the most widely used algorithms even to this day are RSA and El Gamal. For large enough public/private keys (at least 1024 bits), these algorithms have been deemed secure for general use and you can find their implementation in pretty much every cryptographic library.


Now, is there a problem with traditional public key encryption? Yes. There's an easier attack that does not involve guessing keys, but rather of an active adversary that can inject herself between Alice and Bob's conversation. Eve could impersonate Alice to Bob and Bob to Alice such that she establishes secure communication with both parties without them suspecting. Therefore, authentication of the public keys needs to happen in order for Alice and Bob to verify that they are really talking to each other. To rectify this problem, an idea was to try to remove the "public" from public key encryption and reduce managing this key to an easy to remember string for the intended recipient (think email address). It is known an as identity-based encryption or IBE.


In IBE, instead of creating public and private keys, the private key is derived from a string that represents a user's identity. The public key essentially is the string (and also used in conjunction with some other public information to extract the public key). So, Bob's identity is all Alice has to remember in order to encrypt messages to him (e.g., "bob@gmail.com"). There is one caveat. Although there isn't a single public key, there is a set of public parameters that are typically a part of the IBE system. The difference is that everyone has access to this information, even the adversary but they do not have the ability to impersonate a particular individual by forging a public key that belongs to that individual's identity. There is a trusted key authority that is responsible for generating private keys for Alice and Bob. It is responsible for authenticating their true identity which makes this type of encryption work in practice. This is nice and is probably still considered a new encryption technique that is still an active area of research to make efficient enough for everyday use. There are tons of applications for IBE including use with biometrics, secure email and many more.


Next post, on improvements in IBE...