IBE and Charm : Part 1

In my last post, I mentioned that Identity-based encryption (IBE) fixed the main drawback with respect to key distribution for public key cryptography (e.g., no need for public keys, just an easy to remember ASCII string). One of the biggest issues with IBE is that there is inherent key escrow. That is, the private key generator (PKG) which generates secret keys for users must be highly trusted because the PKG has the capability to generate any key and can thereby decrypt all messages. For centralized models (e.g., found in organizations), this is not necessarily a big deal in that there is likely a trusted infrastructure the PKG can plug into. Another issue is revocation. If public identities are represented by email addresses, then that poses problems when an individual in an organization is fired and coincidentally another employee is hired and given the same email address. Does the new guy automatically inherit the secret keys of the previous employee and thus access their old emails? To fix this, email addresses might be appended with a unique numbering system for each employee to avoid collisions, but that hardly seems like a novel solution. Although this approach would work, there are various ways of managing identities that do not involve cryptography per se, so it isn’t the focus of this post. If interested, refer to the wikipedia article for more details on IBE.

So, I’d like to discuss my experience implementing an IBE scheme in Charm. Charm is a Python framework for rapid development of advanced and complex cryptographic algorithms. It is a project I have been working on for the last few years and I’ve used it as an opportunity to understand how cryptographic schemes are designed and their proof of security with respect to chosen-plaintext and chosen-ciphertext attacks. If you’re familiar with Python, you will probably agree that it’s an easy to learn language and write readable code. Since it’s an interpreted language, you get the benefit of not having to worry about compilation errors. For developing crypto code, this is a great advantage and one that allows developers (like me) a neat way of learning modern cryptography without being bogged down with implementation details. Charm allows developers to focus on the high-level cryptographic algorithm and provides the necessary infrastructure for developers to implement a variety of cryptographic algorithms and protocols easily.

The IBE scheme I implemented in Charm can be found in “Revocation Systems with Very Small Private Keys” by Lewko et al (ePrint article) on page 8 in section 4 (published in IEEE S&P in 2010) has very useful revocation features. Fortunately, you do not have to understand the details of the scheme to use the implementation. Note that this scheme implementation isn't present in the previous release of Charm, but will be made available in the next release slated for early next month. So, I’m going to focus on the high-level API in this post and how you could easily incorporate the scheme in Python into your application.

As a recap, IBE consists of four algorithms: setup, keygen, encrypt and decrypt. The first step is to declare a group object in which the scheme will be instantiated. Historically, IBE has been implemented in pairing-based settings (subject for another post) due to efficiency reaosns. Non-pairing (or integer) based versions have been known to be quite inefficient for practical applications. Instantiating groups for implementing schemes is easy in Charm, so I'll leave that out of this post. So, once the group has been instantiated, we can create the new IBE instance as follows: 

IBE = IBE_LSW(groupObject)

Next, run the setup algorithm with the number of users in the system.

(mpk, msk) = IBE.setup(n)

mpk and msk represent python dictionaries for the global public and master secret parameters. Now, to generate user keys based on a specified identity, the private key generator executes the following on the user's behalf:

sk = IBE.keygen(mpk, msk, "user2@email.com") 

To encrypt a message with a revocation list of identities and the global public parameters:

ct = IBE.encrypt(mpk, M, ["user1@email.com", "user3@email.com",...])

In this case, the message, M, is a group element which means that this scheme by default cannot encrypt ASCII strings. For other settings such as standard elliptic curve and integers, we have the ability to encode strings as group elements. In practice, either the string is encoded as a group element OR we take the hash of a random group element and use that hash as a symmetric key to protect the actual ASCII message. In Charm, we have not implemented conversion routines for pairing groups given the complexity of the algorithm. 


To decrypt the ciphertext, a user has to specify the revocation list (denoted as S), the ciphertext, ct, and the user's secret key, sk:

m = IBE.decrypt(S, ct, sk)

If the user's identity is in the revocation list, S, then the decrypt routine will fail, otherwise, the user will be able to recover the message. Since the recovered message is a group element, we could either decode back to a string OR take a hash and decrypt the second ciphertext as a result of using symmetric encryption. Fortunately, there are tools in Charm that do this automatically, thus making it very easy to use this scheme in a real application. In the next post, we will look under the hood for a better understanding of how close the implementation is to the original scheme description in the paper. Comments and questions are welcome on any of the above. Thanks for reading.