A Gentle Introduction to Attribute-Based Encryption
Attribute-based encryption is a promising new¹ technique in cryptography that has so far only been covered in graduate cryptography courses and academic papers. It has barely filtered into new cryptography textbooks², let alone the broader programming community.
This is a non-mathematical introduction to Attribute-Based Encryption. If you have some interest in cryptography, but don’t have a graduate degree in pure math, then this post is for you.
If you are already familiar with the basics of cryptography, skip ahead to fall into the rabbit hole directly.
What is Encryption?
Let’s start with the basics without getting too mathematical.
Imagine your friend Alice is running a back-alley poker game. Alice doesn’t want just anyone barging into her illegal gambling den, so she gives you a passphrase: “Follow the White Rabbit”. When you knock on the correct seedy door, the bouncer asks you, in a genre-savvy baritone, for the passphrase. If you say the right phrase, you get in. If not, you stay outside soaking in the metaphorical rain.
To stretch the analogy, Alice can change the passphrase each time she holds a poker game. Knowing the passphrase for the day, you can then share the passphrase with one of your other friends, or some of your pals in the FBI.
In cryptography, this passphrase is called a key. Cryptography provides a black box to transform plaintext (a document, a photo, a poker game of questionable legality, or anything else you might want to protect), when combined with a key, into ciphertext. Ciphertext is unreadable junk to anyone without the key. This process is called encryption. On the other hand, anyone with the key can decrypt the ciphertext back into the original plaintext.
Encryption and cryptography have existed in various forms for thousands of years, dating back to at least Ancient Egypt. Since then, there have been a wide variety of ciphers (that is — processes of turning plaintext and a key into ciphertext and back again) ranging from primitive to highly sophisticated. The formal study of cryptography probably began around World War 2³ with Polish cryptologists such as Rejewski trying to break German military ciphers. That research continued in UK’s Bletchley Park by Alan Turing and his team, famously breaking Enigma.
Since then, there have been many new “types” of cryptography. I will discuss a few, and roughly how they work.
Symmetric and Asymmetric Cryptography
Let’s say you want to send a secret message to your friend Alice, who has evaded capture by FBI agents and is now on the run. One way to do that using cryptography is to agree to a shared key beforehand. For example, you and Alice might agree to use the first sentence of the Harry Potter books as a pre-shared key, since it’s easy to remember.
Mr. and Mrs. Dursley, of number four, Privet Drive, were proud to say that they were perfectly normal, thank you very much.
Some problems with this approach are you may not be able to arrange a secret key ahead of time, or your secret key may be leaked after some period of use⁴. Completely hypothetically, some blogger may have included it in his piece on cryptography, and now you have no way of securely passing messages.
So what now? Enter asymmetric cryptography (also called public-key cryptography).
Imagine now that you have a specially designed mailbox. It has one door on the top (let’s say a green door with a green key) allowing someone to drop in letters, but not read them. It has another door on the side (let’s call this the red door with a red key) allowing the person who opens this door to read the letters. This is sometimes used in highly secure mail rooms, where the mailperson has the key to the top door, but not the side door. Each recipient has their own red key for their mailbox.
Basically, if a person gives you their green key, you can send them secure messages. However, having the green key doesn’t allow you to read those messages. Once the messages are deposited into the box, only someone with the red key can retrieve them.
In cryptographic terms, we call the green key a public key, and you can give it to anyone you want. The red key is called a private key, and you keep that one secret, since it allows anyone who has it to read messages. It is important not to get these two confused.
Not only does this system solve the problem of not having a pre-shared secret, but it now allows you to use a single (private) key to receive messages from multiple people, if you so choose. If you were to use classical (symmetric) encryption, you would need a different key for each communication channel, to keep people from reading each other’s messages.
Not going too much into technical details, the technology underpinning the little green lock in your browser’s address bar uses asymmetric cryptography in a system called Diffie-Hellman key exchange. It’s also used in more recent versions of the popular GPG software in a system called ElGamal encryption.
In practice, this means Alice can take out an ad in the New York Times and share her public key with the whole world. You can then use this public key to encrypt a message to her, and know that only she can read it, as long as her private key remains secret.
Identity-Based Encryption
Imagine you have an email system inside a company where everyone sends encrypted emails. Continuing with our example from above, our friend Alice has been rehabilitated and rapidly promoted to CFO, owing to an unexplained series of disappearances and unproven allegations of broken kneecaps. Established in her new role, she wants to send a quick email to her friend Bob the CTO, asking whose kneecaps she has to break to get a latte around here.
Alice finds Bob’s public key somewhere (recall that this key can be public and freely available, so it might be on an internal directory page), writes her email, encrypts it, and sends it to Bob. But Bob wrote his private key in his notebook, and he forgot that notebook in an airport. Or Bob’s private key was on his phone, and one of his kids accidentally knocked the phone into the bathtub. Now when Bob gets a new phone, he tries reading all of the emails from Alice, and realizes he can’t. No private key, no emails.
But the problems don’t end there. When you lose the only key to a lock, you have to change the whole lock. Digital cryptosystems are no different — public and private keys are generated together as a pair, and you can’t recreate one from the other any more than you can create a key if you only have a lock. Thus Bob has to create a brand new public-private key pair, upload the new public key onto the company directory, and let everyone else know that the old public key is no longer valid. If Alice doesn’t notice this change, she would continue sending Bob emails encrypted using his old public key, and he would continue not being able to read them.
It turns out this is a very common problem in cryptographic systems — people are terrible at managing keys. In 1984, a cryptographer named Adi Shamir had a great idea: what if the company itself could just manage the keys? He thought the whole idea of public keys was too cumbersome, and wanted people to use something more memorable: their identity (like a name or email). If you want to send an email to Bob, use bob@symantec.com as the public key and be done with it. He called this idea Identity-Based Encryption.
Why couldn’t we do that before? Well, when you have a lock, the key has to be key-shaped. It can’t be shaped like a ball bearing or a Pikachu. Digital asymmetric keys are the same — they’re usually unreadable nonsense of a pre-specified length.
Well, why can’t we design a lock that accepts any Pokemon-shaped object? That was Shamir’s big idea. Unfortunately, he didn’t have a very good solution, so left it as an open problem to the cryptographic community at large. When you’re a big-time famous academic, you get to ask questions instead of answering them; it’s a pretty sweet gig⁵.
In 2001, Dan Boneh came up with his version of a solution, which is still considered the practical implementation of identity-based encryption to this day. Identity-based encryption allows anyone within an organization to encrypt any text with another user’s identity. In theory, you can use any text for a user’s identity, but in practice it makes sense to use something easy to remember, such as their email. The decryption step is a bit more complicated, so let’s illustrate how it works with our example from before.
So back to Alice, our CFO of dubious morals. She wants to send an email to Bob, and she already knows Bob’s email. She uses that as a public key, and the email program she uses automatically encrypts the email with bob@symantec.com, and she sends the email.
Now, Bob needs to read the email. Recall that in our previous system of asymmetric cryptography, Bob would have a corresponding private key to decrypt the message. Now, instead of having a private key on his machine, he creates a key based on his identity. All he needs is a method of proving that he is in fact Bob to the email system he’s using. For example, the good old username-password combo will do. The email system then issues him the correct private key to decrypt that particular email.
The problem with this design is it requires trust in a central system, usually called the Private Key Generator or PKG. Any compromise of the PKG also compromises all the keys⁶. For this reason, it is not a good basis for a general-purpose cryptosystem, but works well in enterprise contexts.
Attribute-Based Encryption
Boneh’s original construction wasn’t limited to only using email addresses however. Decryption keys could depend on other small pieces of additional information embedded in the “identity” of the recipient by the sender. For example, if Alice wants Bob to read a message starting tomorrow, she can embed tomorrow’s date as part of Bob’s “identity”
(bob@symantec.com+jan-5–2019), and the email system would only give Bob the correct key on the specified date. This would mean Bob would be unable to read the email before Jan 5. Similarly, embedding a clearance level (say TOPSECRET) would allow only a person who has the correct clearance to read the message.
These ideas were very powerful, but ad-hoc attributes into an identity seemed awkward. It wasn’t long until a new cryptosystem was developed which generalized this approach, by Amit Sahai and Brent Waters in 2004. They called their system Fuzzy Identity-Based Encryption, but of course it is now known as Attribute-Based Encryption (or ABE).
The contributions were twofold. First, it allowed for multiple private keys to be used with a single public key (hence the “fuzzy” in the original title, for “fuzzy matching”, meaning approximate matching in computer science land). This idea is very surprising to many people familiar with classical cryptography, where only a single key can decrypt any given message. If you’re not a crypto expert, imagine multiple distinct keys opening the same lock. Weird, right?
Secondly, public keys are constructed from a list of attributes instead of an identity. Anyone who has all the attributes can read the message. One of the attributes can be an identity (such as an email), but it doesn’t have to be. So instead of artificially stuffing the “identity” full of keywords, the keywords are now explicitly part of the system.
This idea becomes much clearer if we consider documents.
Let’s say Alice wants to conduct research into a more efficient way to blackmail people, as part of her ultimate quest to get lattes faster. She asks Bob, the CTO, to prepare a proposal and budget. Bob creates the budget, and now has to share this very confidential document with multiple groups of people: the VPs of research, naturally, and every member of the finance department. How does Bob proceed?
Under identity-based cryptography, he would either have to create multiple encrypted versions of this document, or use the hack of adding keywords into the identity, as mentioned above. Under attribute-based encryption, however, Bob can encrypt the document with the attributes vp-research and finance, and specify a policy that at least one of these attributes is necessary to decrypt. Anyone having one of these attributes as part of their identity can now decrypt the document⁷.
The rest of the procedure works as before: the system will encrypt the document by constructing the appropriate public key using the attributes and the policy. When Alice (or another user) attempts to access the document, she requests the creation of a private decryption key from the PKG. The PKG verifies that Alice has finance as part of her identity (she is the CFO, after all), and creates the key. Alice then uses the key to decrypt and view the document.
As an exercise to the reader, think about how such a system could be implemented using classical cryptography⁸.
This is an amazing formulation that has a broad range of applications. But, as savvy engineers reading this know, there are always trade-offs.
Aside: Key Generation
While some math is unavoidable, I will try to explain this without getting into unnecessary technicalities.
Digital cryptography is based on constructing mathematical problems that are hard to solve but easy to verify once you have a solution. Think of a crossword as the problem, and all the answers as the solution. It might take you a few minutes to make sure that the answers are right, but much longer to actually solve the crossword. Algorithms that take advantage of this idea are called trapdoor functions.
Earlier, we talked about public-private keys and how they come in pairs. In practice, the public key sets up a mathematical problem, and the private key is the solution to that problem. Of course, since there are many ways to create hard math problems, there are also many ways to generate key pairs. We will focus on two: RSA and elliptic curve pairings.
RSA is the typical way to create a public-private key pair. The idea is based on picking two large primes and involves some modular arithmetic. Basically, doing modular arithmetic is easy, but prime factorization is hard⁹.
Elliptic curve pairings¹⁰, such as the Weil pairing used in ABE, work on a different principle. A pairing is a carefully constructed relationship over two points on an elliptic curve. For a more in-depth discussion on elliptic-curve pairings and their properties, see this excellent blogpost by Vitalik Buterin. Computing this function given two points is efficient, but reversing the function is hard.
However, what is “efficient” for a mathematician doesn’t necessarily mean fast on a computer. RSA uses very simple math, and modern processors have special instructions optimized for it. There are no special CPU instructions for bilinear maps over elliptic curves (hopefully), so RSA in practice is much faster.
Problems with Attribute-Based Encryption
Central Trust. Attribute-based encryption requires trust in a central authority — the Private Key Generator (similar to Identity-Based Encryption). This makes it most appropriate in enterprise settings. There has been some discussions in academic literature for a more distributed version called Decentralized ABE (DABE), but I believe these schemes do not truly decentralize ABE. Instead, they increase the number of possible roots of trust, similar to the CA infrastructure used on the web. In my personal opinion, this makes the system less secure, not more¹¹.
Speed. Attribute-based encryption (especially CP-ABE¹², which is the variant I introduced above) is slow, because it involves creating a “policy tree”. It’s most expensive on decryption, which is the worst place to be slow, because decryption is likely the operation you will be performing most often (most people read more emails than they write, for example). Both ABE constructions¹³ are slow relative to classical encryption, and are theoretically about 20x slower than classical symmetric encryption. This is due to the specific mathematical construct used in ABE — the Weil Pairing, mentioned above.
You can intuitively see why this is: ABE has to generate a new private key each time you want to decrypt a document. In other systems, you use the same key throughout. In practice, you can reuse¹⁴ many keys, so this problem may be overstated somewhat.
Additionally, both ABE constructions get progressively more expensive as the number of attributes increases on a given piece of data.
Unfortunately, a bit of math here is unavoidable.
ABE is not restricted to using the Weil pairing, and can work with any bilinear map of the form
over two groups such that the Computational Diffie-Hellman problem is hard on G₁.
Therefore, using a different bilinear map, for example the Tate pairing discussed above, can potentially help with performance. I am not a mathematician, but I don’t believe there is any fundamental reason that all bilinear maps of the type necessary for decryption in ABE have to be slow, so there is likely further room for improvement.
Labelling. Labelling data correctly (coming up with attributes) is hard. Coming up with a good labelling policy is non-trivial. I will discuss this problem in more detail below.
Labelling
If you ever had to study for a final, this may look familiar:
I use an elaborate system of multi-colored sticky tabs to organize the papers on my desk. In the photo above, pink means the topic involves computer security, blue means low-level systems work, and bright-yellow tabs indicate I know the author personally. In this kind of system, many sticky tabs can be attached to a single document, because I could know the author and the paper could be about computer security. Let’s call the sticky tabs attributes. The rules I follow to attach an attribute to a document is called a labelling policy.
Coming up with a good set of attributes and a good labelling policy is hard. First, I have a lot of documents, and I need a set of attributes that will help me find a document on a topic of interest quickly. I have to anticipate what I want to search for. Also, I will read more papers tomorrow, and next month, and next year. I need for this system to make sense in a few years, for new documents to be well-labelled¹⁵.
Second, there can’t be too many attributes, otherwise a paper may fit too many attributes and be made mostly of tabs. If the tabs were digital, then it would take a lot of storage space to store a lot of attributes per document.
Finally, the labelling policy has to be easy to apply. I don’t want to spend all my time labelling documents, I actually want to get some work done.
Now, this may sound like a big downside of attribute-based encryption. However:
All systems with a permission mechanism have implicit attributes
To see why this is the case, think about each document on your work computer, and who the intended audience for that document is. Then think about the consequences of the worst person outside that group having access to that document. Coming up with these groups for each document is the same problem as assigning attributes¹⁶.
In some ways, requiring explicit attributes is a positive feature of ABE, as it forces you to reason about data permissions when you create documents, rather than at some later point¹⁷.
Conclusion
In this post, I introduced attribute-based encryption, a recent advance in cryptography with practical applications to secure document storage and other modern problems. Please leave your questions feedback on Hacker News or @ me on Twitter.
A second installment will be released in a week or two detailing the practical uses of Attribute-Based Encryption, and how software design should be less like building the Notre-Dame de Paris, and more like building elevators.
—
Footnotes
¹ Relatively speaking; it was introduced in 2004
² Most textbooks only treat the outdated RSA implementation. Advances in Elliptic Curve Cryptography (2005) is the only book I’ve found which actually has a section on the Weil pairing. It’s extremely technical, and not far the faint of heart.
³ With the possible exception of the introduction of frequency analysis for breaking substitution ciphers by the 9th century Arab mathematician Al-Kindi
⁴ Forward secrecy is out of scope for this article, since it is covered in great depth by others
⁵ I’m skipping over the many valuable contributions of Shamir, who was one of the greatest cryptographers of his generation and a giant in the field. But if you have a resume like that, why do you care what some blogger writes?
⁶ It’s possible to decentralize this system somewhat with a thresholding scheme, but this discussion is out of scope
⁷ This technically describes CP-ABE, while KP-ABE works in exactly the opposite manner
⁸ As mentioned in the paper, you can use a different key for each attribute. However this only works for disjunctions in policies. Conjunctions allow users to collude and escalate access.
⁹ More correctly, the discrete log problem is thought to be hard
¹⁰ A very nice introduction to elliptic curve cryptography can be found here
¹¹ For a concrete example of how multiple equal-party roots of trust can weaken a cryptosystem, see the way Chinese telecoms performs MITM attacks on TLS
¹² Ciphertext-policy ABE
¹³ CP-ABE and KP-ABE
¹⁴ i.e. cache
¹⁵ Re-labelling documents is a nightmare under any system, and is out of scope for the sake of simplicity
¹⁶ Permissions and attributes are homomorphic systems with respect to each other
¹⁷ I will discuss this in more detail in part 2