A quick dive into identity- and attribute-based encryption

Identity-based encryption

Wouldn’t it be great if we could just encrypt emails directly with a key derived from the email of the recipient? This question was first formalized by Adi Shamir, the co-inventor of the Rivest-Shamir-Adleman algorithm, or RSA, in 1984. The resulting cryptographic concept was called “identity-based encryption.” It took another 17 years until this concept was proven to be secure by Dan Boneh and Matt Franklin using the Weil Pairing.

Identity-based encryption (IBE) solves the problem of trusted public key distribution by letting users calculate the public key of recipients based on their identifier. An identifier can be any kind of string — the email address of the recipient, for example. The concept introduces a central authority whose job it is to generate respective private keys for identifiers.

Since the sender (let’s call her Alice) can calculate the recipient’s (Bob’s) public key offline based on his email address, Bob doesn’t even have to exist in the system yet. When Bob registers in the system, he just requests his private key from the central identity authority and then decrypts the data.

This design also solves the problem of key expiration — a complicated procedure in classic trusted web applications usually requiring expiring certificates. By making the identifier user+currentYear()@example.com, Alice forces Bob to request a new private key from the central authority every year.

Bob could also act as his own central authority, allowing Alice to send emails that could only be decrypted by certain departments. Imagine a scenario in which Bob is a company administrator and he needs to be able to view all company emails. However, he also wants to make sure that no department can decrypt emails from any other departments. The solution? Bob can set up a central authority and Alice can send emails to security@company.com, press@company.com, and info@company.com (all hypothetical email addresses invented for this example), each encrypted under their own identity public key. Best of all, these emails could all go to the same inbox without compromising confidentiality.

So why is identity-based encryption not used widely for email encryption? The biggest hurdle to this system is setting up the central identity authority to manage the generation of private keys. That might be practical in a company where it’s not unusual for administrators to have a master key to access employee data, but what about other non-corporate contexts?

Imagine that you have an image that you would like to show to your doctor — an X-ray from a previous appointment, for example. Maybe the doctor needs to consult another specialist, like a radiographer. You would like to encrypt your X-ray image in such a way that it could be shared among doctors and specialists.

Identity-based encryption wouldn’t allow the first recipient (your doctor) to safely share the data with someone else. For that, we would need something more flexible that would allow us to embed access policies within a message’s ciphertext. We need attribute-based encryption.

Attribute-based encryption

Attribute-based encryption (ABE) is the next generation of identity-based encryption. Instead of binding public keys to identity strings, they are instead bound to attributes.

Relying on attributes allows the sender to craft a ciphertext over a chosen access policy, combining different attributes with “and”/“or” gates to formalize access conditions. This approach is called ciphertext-policy attribute-based encryption (CP-ABE).

You can also do it the other way around — associate the user’s key with an access policy. Doing so is known as key-policy attribute-based encryption (KP-ABE). Similar to identity-based encryption, an attribute authority is responsible for managing attributes and their private and public key pairs. The owner of the attribute authority has global decryption power over all its attributes.

It is simple to make and own an attribute-based encryption scheme. Let’s introduce a central attribute authority, which stores a map of attribute identifiers to (normal, RSA) public keys. For example, imagine the following mappings:

If Alice would like to craft a ciphertext that can only be decrypted by general doctors who have her as a client, she would encrypt her secret text like this:

Note that Alice herself doesn’t need to have access to the attributes. Only people who have access to both private keys of the attribute “has Alice as a client” and “general doctor” can decrypt the ciphertext. First Bob removes the outer layer of encryption by providing the “has Alice as a client” private key and then additionally applying the “general doctor” private key to retrieve the plain text.

Additionally, Alice would like to give all radiographers (Charlie) access to her photo scan. She creates the following ciphertext:

She can now combine both ciphertexts into one message and send it to her doctor:

As we can see, the ciphertext can be decrypted by radiographers (who will decrypt the first part of the ciphertext) or by any general doctor who has Alice as a client (decrypting the second part of the ciphertext).

As with most simple cryptography schemes, this system has some issues. In this case, our simple ABE schema is not collusion resistant. That means that if Eve is a general doctor and Dave is a psychologist who has Alice as a client, nothing stops Dave from just providing Eve with the private key for the attribute “has Alice as a client,” allowing Eve to escalate access.

Attribute-based encryption schemas must be collusion resistant. In practice, collusion resistant means that even if users exchange private attribute keys, they cannot gain additional knowledge about plaintexts beyond their access level.

This could be done, for example, by creating an individual user-bound attribute private key for each attribute, essentially combining the identity element from identity-based encryption with attributes. Additionally, ciphertext should not grow in size the more policies are added to them. Contradictorily, in our self-made schema, a ciphertext would grow larger and larger if we had multiple “or” conditions in our access policy.

Nevertheless, one problem remains. The central attribute authority can globally decrypt ciphertexts, allowing it to impersonate any user and issue any attribute to itself. Having this trusted central authority in the medical context is a bad idea, since medical information is highly sensitive and should only be decryptable and accessible by authorized parties. For the corporate context, attribute-based encryption makes more sense because an administrator could issue attributes to users and is allowed to decrypt and access any file in the company. But what if we have multiple companies, each with its own attribute authority?

Multi-authority attribute-based encryption

Multi-authority attribute-based encryption (MA-ABE) is an attribute-based encryption variation where multiple attribute authorities are responsible for managing distinct attributes. Why don’t we set up multiple individual attribute authorities? Well, we still want to be able to combine attributes from other companies with attributes from our own company to enable cross-company sharing.

In such a system, it becomes a problem to establish globally known parameters for each attribute authority. MA-ABE introduces a new central server that is responsible for setting up new attribute authorities and bootstrapping the system overall.

Early MA-ABE schemes required this central server to have global decryption power over all attribute authorities. On the other hand, modern MA-ABE schemes such as DAC-MACS (effective data access control for multi-authority cloud storage systems) are close to what we need to implement for MA-ABE in real-world scenarios because they don’t require the central server to have global decryption power.

MA-ABE offers some useful new approaches to data encryption:

1. 1.ABE schemes are group centric, meaning that a single group can be described with a single attribute. This makes encrypting and decrypting for groups easier. On the other hand, encrypting information for single individuals becomes more computationally intensive compared to traditional encryption schemes because these individuals usually don’t share common attributes.
2. 2.When an attribute gets revoked from a user, the attribute key and all ciphertexts using this attribute need to be rotated and re-keyed. This can be done by the attribute authority or a proxy-reencryption service.
3. 3.Proxy-decryption is a technique where a server helps the user during decryption. It does so by using the user’s private attribute keys. As the ciphertext is additionally protected with the user’s identifier (IBE), confidentiality is not compromised. Proxy-decryption can be used to help mobile clients with the computationally intensive decryption process.

Is MA-ABE ready to be deployed in modern secure cloud storage solutions such as NordLocker Business or NordPass Business? Personally, I would say no.

Even though the modern MA-ABE schemes fulfill most of the security requirements for end-to-end encrypted cloud storage systems, their system implementation is complex, and the underlying cryptographic principles like pairings are not yet widely adopted in cryptographic libraries. In addition, pairing operations are computationally intensive and not suitable for mobile devices, which require low power consumption for a good user experience.

With the world shifting increasingly further to the mobile side, proxy-decryption might help to decrease the computational overhead on the mobile device, but it requires the user to be always online to access their encrypted files. Finally, MA-ABE can only be cryptographically beneficial if users change their attitudes around encrypting files — away from sharing data with individuals, and towards attributing access policies over their data. It is yet to be seen if users and companies are willing to adopt this mindset change.

The existence and proven security of attribute-based and identity-based encryption schemes show that we are just scratching the surface of what is cryptographically possible with elliptic curves. However, the practical applicability of schemes in real-world scenarios is yet to be seen.