Proxy Re-Encryption

End-to-end encryption for groups

Why three keys are better than two.

The power of public key cryptography comes from the fact that two keys are better than one. With traditional symmetric key cryptography, the same key is used to encrypt and decrypt a message. This means that we need a secure channel to communicate the encryption key to each sender before we can send a message.

Traditional symmetric key cryptography is difficult to deploy and limited in what it can achieve because there must always be at least two parties with access to any given piece of information. This means we cannot have anything like a digital signature because the only parties that can verify a signature are the same ones that can create it.

The heart of public key cryptography is the understanding that different cryptographic functions require different cryptographic keys and it should not be possible to convert a key used for a public function into one that is used for private functions.

In public key encryption, we use the public key to encrypt and the separate private key to decrypt. Encryption and decryption are separate functions and so must have separate keys. The same goes for signing and verifying documents.

The power of proxy recryption 'recryption' comes from the fact that if an application has more than two cryptographic functions, we need more than two cryptographic keys to support them. In particular we split the private key to partition the decryption function.

Recryption is powerful because it allows us to support communications in which a message is being received by a group of users or a set of devices belonging to a single user. In the two party communication example, Alice sends a message to Bob. But how do we support the case in which Sally is sending a message to Alice, Bob and Carol?

The simplest way to address this problem is to simply treat a message sent to n recipients as a set of n bidirectional messages. This is the approach supported in OpenPGP and S/MIME and it does not actually add much to the message size because we only need to encrypt the message data once under a session key and then create n decryption blobs for each of the recipient's public keys.

This approach works fine for email in which the set of recipients is decided by the sender and fixed for all times when a message is sent. It works much less well for group communications such as mailing lists where the set of recipients is not fixed for all time as members join or leave the list. in many cases, we may not wish the sender to know who is on the distribution list, quite often they may only be allowed to send to the list but not read it.

The most commonly used approach to securing group communications today is to use two separate end-to-end secured communications. Messages are sent to a forwarding server that routes them to each of the recipients. Messages are encrypted 'end-to-end' between the sender and the forwarding server and between the forwarding server and each recipient. But this is not a true 'end-to-end' communication because there is a gap in the protection where the messages are decrypted and re-encrypted at the forwarding server.

This 'end-to-end' gap is where attackers target the enterprise. Almost every enterprise that was the subject of a major breach in recent years used encryption. The reason the attackers were able to bypass the encryption was that there was a gap. In a corporate breach, the first target an attacker usually goes for is the email system because in most enterprises, that is where they will find several years worth of internal correspondence.

Recryption allows the end-to-end gap to be closed. As with the Decrypt-Encrypt example above, the forwarding server receives messages from the sender and passes them to each receiver in turn. But this time the forwarding server does not have the ability to decrypt the message because it does not have the decryption key. The decryption key is held by an administrator who uses it to create a recryption/decryption keypair for each recipient. The recryption key is sent to the server and the decryption key to the intended recipient via a secure channel. The recrypt key for each of the recipients allows the forwarding server to modify the message encrypted under the group key so that it can be decrypted under the corresponding recipient decryption key. It does not allow the message to be decrypted on its own.

It is possible to build a recryption scheme using any of the popular public key algorithms. Implementing recryption in the Diffie-Hellman algorithm is straightforward as is shown here.

Recryption in practice

Just as the Diffie-Hellman scheme does not provide the full 'public key encryption' that is provided in the RSA scheme, recryption using Diffie-Hellman does not meet what cryptographers have decided are the 'ideal' properties of a recryption scheme. And just as with the lack of a full public key encryption scheme, the lack of an 'ideal' recryption capability does not matter in practice, it just means we have to work around them.

The fact that we can use a few work-around to use plain old Diffie-Hellman and its elliptic cousins is good because none of the 'ideal' recryption schemes I have read in the literature would be a practical choice in a standards based cryptographic protocol. They all seem to require a leap of faith into a new public key crypto-system or at the very least depend on some complex math that may or may not be correct and hasn't been seen by nearly enough people for me to be confident in.

Practical management of recryption keys.

In an ideal recryption scheme in which Alice is the administrator and Bob a recipient, they do the following:

  • Bob creates a public keypair for all his communications and give the public key to Alice.
  • Alice uses the group decryption key to generate the corresponding recryption key for Bob.
  • Alice encrypts the recryption key under the public key of the forwarding server
  • Alice sends the encrypted recryption key to the forwarding server with an indication it is to be used to recrypt messages sent to Bob.

The simple recryption scheme doesn't allow us to do that. Alice can only split the group decryption key into two parts and give one of them to each of the forwarding service and Bob. Fortunately, there is a simple workaround.

  • Bob creates a public keypair for all his communications and give the public key to Alice.
  • Alice would use the group decryption key to generate a recryption/decryption keypair for Bob's use.
  • Alice encrypts the recryption key under the public key of the forwarding server
  • Alice encrypts the decryption key under Bob's public key and sends
  • Alice sends the encrypted recryption and decryption keys to the forwarding server with an indication they are to be used to recrypt messages sent to Bob.

This approach isn't quite as smooth and elegant as we would like but it works fine for most purposes. The only times we start to run into problems are when we would like to apply recryption at multiple points in the process and meeting those requirements was one of the biggest challenges faced in the design of Mesh/Recrypt. The solution is not complete but it is adequate for most use scenarios.

Applications of Recryption

Most papers on proxy re-cryptography use the mailing list or 'holiday forwarding' as examples. I beleive that recryption is the tool of choice for any communication involving groups of users.

Corporations desperately need to end-to-end encrypt communications but the corporations don't generally develop security processes that run ahead of the technology to support them. This does happen in the government space where security can quite literally be a matter of life and death. The capabilities provided by recryption map surprisingly well to the system of label based security used to manage Sensitive Compartmented Information in the US federal government and its NATO allies.

Use case

In a government setting, a 'group of users' corresponds to a set of people who hold a clearance for a particular security label. Let us imagine a project with the codename and security label LEMONCAKE. The members of the project require the ability to access all common modes of Internet group communication including:

  • Mailing lists
  • Instant Messaging
  • Voice and video conferencing, screensharing
  • Source code repositories (e.g. Git)
  • File stores
  • Data sets

In each case we wish the data to be encrypted end-to-end. We will also want to make use of facilities such as transport and network level security and full disk encryption. But even with these controls in place, no data or document should ever exist in unencrypted form except on a device that generates it or presents it to a LEMONCAKE member. And even in those limited cases, we would want to tighten the window of vulnerability to make it as small as possible.

For simplicity, we will only consider protocols involving asynchronous protocols such as mailing lists and encrypted documents in the first instance and then expand the scope to consider synchronous protocols such as Instant messaging and voice.

Alice is the administrator responsible for granting and revoking clearances for LEMONCAKE. Alice and Bob are members of the project from the start. After a few months, they are joined by Carol and Doug. Unfortunately, Doug loses his clearance after it is discovered he made an ill advised stay at the Moscow Ritz-Carlton.


Communications within the LEMONCAKE project are supported by many different server hosts both inside and outside government. All recryption services are supported by a separate recryption server that is contacted by an end-user machine as required.

To create the encryption services to support LEMONCAKE, Alice creates an encryption/decryption keypair for the group. The encryption key is distributed to the parties that need it.

Alice then creates recryption/decryption keypairs for herself and Bob and sends them to the recryption server. When either of them need to access an information resource that is encrypted under the group recryption key, the application on their machine automatically connects to the recryption service which provides the information they need encrypted under their personal public key.

When Carol and Doug join the project, Alice creates recryption/decryption pairs for them as well. Both have immediate access to all the data in the project.

When Doug loses his LEMONCAKE clearance, Alice instructs the recryption service to refuse all further recryption requests from Doug. This does not prevent Doug from making use of any data he has decrypted previously and stored but does prevent him from decrypting any additional information.

Note that the only operation that we must trust the recryption service to perform is to withdraw Doug's access. Compromise of the recryption service does not result in disclosure of any data in itself unless at least one of the decryption keys is also compromised.

Synchronous protocols

In an asynchronous protocol such as email, the participants are never in direct communication. This limits our options as far as end-to-end encryption goes. The first party encrypts a message and forwards it to a server where it is stored until the recipient picks it up.

In a synchronous protocl such as chat, all the participants are in communication at the same time. This means that the initial key exchange used to initiate the communication can be more complex than a single message passed from sender to receiver. In particular, we can achieve a very useful protocol (misleadingly) called 'Perfect Forward Secrecy' by creating an additional ephemeral key pair wherte we use the private key once and immediately discard.

Enhancement: Multiple Administrators

The basic implementation described is functional but places a lot of trust in Alice as the sole administrator of the group decryption key. While this would normally be stored in a suitably hardened 'Hardware Security Module' and protected by the usual audit and accountability schemes, we would ideally like to introduce some form of separation of duties.

The Diffie-Hellman algorithm supports this need in a straightforward manner. Instead of giving Alice the whole encryption key, we divide it into two in the same way that we divide it for the recryption step. Each half of the key is then given to a separate administrator who must both provision a recryption keypair for each LEMONCAKE member to grant access.

Enhancement: Metered use.

Perhaps the most surprising feature in recent US government breaches has been the sheer volume of data that rather junior members of staff were allowed access to. While none of the known perpetrators had clearances that gave them access to the very most sensitive classified material, the sheer volume of less sensitive material was as damaging as if they had.

Introducing the recryption service provides us with a control point at which it is possible to monitor and limit use. If a user attempts to decrypt a hundred LEMONCAKE documents in a day, their supervisor is informed, if they attempt to perform a mass document dump, the FBI is called.

Recryption with multiple devices.

Patent Status

The technique itself was proposed by Blaze et. al. in 1998. It does not appear in list of his patents which should in the normal course of business have expired in any case.

There are many improvements and applications that are patented. Until quite recently, the USPTO and the courts were willing to issue and enforce patents of the 'do it on the radio' variety which merely combined a recently discovered technique to longstanding application that was obvious to pretty much anyone with an understanding of the application.

While the application patents might be a concern, most of the 'improvements' are unimportant as they attempt to address an issue that was of real concern to the cryptographers but utterly uninteresting to anyone building an actual protocol. Specifically, they had this peculiar idea that it was important to be able to re-encrypt a document to a public key chosen by Alice rather than enable Alice to decrypt the document. As with the similar distinction between RSA encryption and Diffie-Hellman key agreement, there is no real disadvantage to using the weaker scheme when designing a protocol and hence no reason to use the 'improvements'.