Receiver Anonymity by Incomparable Public Keys

Abstract

Receiver anonymity means the ability to send one or more messages to a receiver in a way that nobody except the receiver can determine whom the message is intended for, or even if two given messages are intended for the same receiver.

The paper focuses on an approach that achieves this by using a mulitcast network, sending every message to all receivers in the system, and encrypting messages with an asymmetric cryptosystem that is designed in a way to allow for the creation of many different public keys (Incomparable Public Keys) corresponding to one single private key.

There is also a short overview of other methods that have been suggested.

Receiver Anonymity

We want to handle the following situation: One party (the sender) wants to send a message to another party (the receiver) in a way so that no further information about the receiver is leaked. Of course, it should be impossible for an eavesdropper to determine the real-world identity of the receiver, but it should also be impossible for anybody to build any kind of profile of a receiver, e.g. aggregate which other senders also have send messages to the receiver of a given message. Particularly, it should be impossible for different senders to determine whether they send messages to the same receiver, the idea being that senders usually have some kind of information about the receiver (e.g. because they are fulfilling some service for him) and should be unable to share this information.

The terms sender and receiver are a bit irritating because usually there will be some prior communication, in which the (later) "receiver" adresses the (later) "sender" (otherwise it's difficult to imagine why the sender should want so send a message to that specific receiver), but this beforehand-communication is out of scope of this approach.

Setting for Incomparable Public Keys

In the Incomparable Public Key setting, every participant has a private key, and as many corresponding public keys as he wants. He will give every sender he wants to get messages from a different public key (it is even possible to give the same sender different public keys for different "requests").

A sender encrypts a message with the public key he got from the receiver, and sends it to all participants.

Every receiver tries to decrypt every message with his (one) private key. He will only be successful, if the message has been encrypted with one of his public keys. All messages that he cannot decrypt will get thrown away.

Previous Research

Pfitzmann and Waidner introduced the idea of messages that are marked in a way that a receiver can determine it's for him in 1986. They call such a mark an implicit address, if only the receiver can determine that he is the receiver, and an invisible implicit address if furthermore nobody else can find out, whether two messages are intended for the same receiver. They show that an asymmetric cryptosystem can be used for invisible implicit addressing, but they only handle the anonymity from eavesdroppers, not from senders (which can easily collaborate and aggregate their respective information, because the use the same public key for encryption to the same receiver).

Bellare et al. in 2001 formally define a property Key Privacy: a cryptosystem offers Key Privacy if it is not possible for any two given private keys to gain any information from a ciphertext about which of the two keys has been used to encrypt it. They show that a cryptosystem that offers Key Privacy can be used for invisible implicit addresses.

In a different approach, Chaum in 1981 suggested the usage of so-called mix nets: Each message gets routed over several mixes. Every mix takes several incoming messages, changes their order and modifies them in a way so that it is impossible to find out what incoming message corresponds to what outgoing message, and sends them onward. For message modification an asymmetric cryptosystem can be used. As an address a list of layered routing and encryption instructions is used. Such an address is anonymous, but can only be used once. This approach has been improved by Goldschlag, Reed and Syverson in 1997 and 1999.

In 2003, Golle et al. suggested the usage of Universal Reencryption for mix nets. By Universal Reencryption, they can change a ciphertext in an unforeseeable but "compatible" way (i.e. the same private key can be used for decryption). They use this to build mix nets that do not need key infrastructure for the mixes. The technics they use for this are quite similar to those used for Incomparable Public Keys.

Other Methods

• Standard asymmetric key scheme: one public/private key pair for all senders:

This offers anonymity against eavesdroppers (provided they don't know the message plaintext. In hybrid methods, where the plaintext is just a one-time symmetric session key, this is the case). But it does not provide anonymity against senders.

• several asymmetric key pairs: one public/private key pair per sender

This does offer anonymity even against senders, but each receiver has to decrypt every message in the system with everyone of his private keys, so this doesn't perform well.

• Several symmetric keys: one key per sender:

This scales as badly as the previous method, but since symmetric decryption is faster it will work for smaller groups. But if a sender gets it's key compromised, all previous communication of that sender with the respective receiver can be decrypted by an eavesdropper.

• Several asymmetric key pairs, marked messages: one public/private key pair per sender, messages contain "mark" which key has to be used:

Each receiver only needs to decrypt his own messages, and only with one key. But a message mark can only be used once, otherwise it would leak information about the receiver.

Incomparable Public Keys

Incomparable Public Keys is a hybrid (asymmetrically encrypted symmetric message key, symmetrically encrypted message) cryptosystem that is based on the ElGamal cryptosystem. It offers the possibility to create arbitrary many public keys for any private key, while making it impossible to recognize public keys as belonging to the same private key.

Requirements

• Many public keys: the holder of a private key must be able to generate many different public keys in way that messages encrypted with one of them can be decrypted with the private key. These public keys must not be recognizable as "belonging together", i.e. it must be impossible for two public keys to determine whether they correspond to the same private key or not.

• Key-Privacy for public keys: It must be impossible to determine if tow encrypted messages are encrypted with the same key.

• Efficiency: Performance should be comparable to other asymmetric cryptosystems. Particularly, the work performed by a potential receiver should not grow much with the number of public keys he has used.

Key Generation

For the whole group of (possible) receivers: Choose a prime p with $q={\frac {p-1}{2}}$ also prime.

For generating a private key: Choose an $x<q$ at random. Remember x as private key.

For generating a public key (corresponding to a given private key x): Randomly choose a g that is a quadratic residue in $Z_{p}^{*}$. Publish (g, g^x) as public key. Remember (g, g^x) as used key in a private hashtable keys_x.

Encryption

You have a message message and the public key (g, g^x) you got from the receiver.

Randomly choose K as key for a symmetric cipher. Randomly choose r < q as ElGamal exponent.

Send

<math> ((g^r, \left ( g^x \right ) ^r \cdot K), H(r), E_K(r, (g, g^x), message) </math>

where

• E_K(m) is the result of encrypting m with the symmetric encryption algorithm using key K
• H is a secure random hash function.

Decryption

You have the received encrypted message ((d, e), h, M), your private key x and your table of used keys keys_x.

Calculate $K:={\frac {e}{d^{x}}}$ using your private key x. Decrypt M using the symmetric decryption algorithm with that K as key. If decryption fails, ignore the message. Otherwise determine the transmitted r, (g, g^x) and message from decrypted M.

Check:

• h = H(r)?
• g^r = d? (the transmitted public key in M is the one that has actually been used to encrypt K)
• $(g,g^{x})\in keys_{x}$? (the transmitted – and used – public key is one you actually gave away)

If any of the checks fails, ignore the message. Otherwise the result is message.

Security

A sender (or a group of conspiring senders) can aggregate information about a receiver as long as the receiver uses the same Incomparable Public Key. Their means of identification is, however, limited to a given public key: They cannot relate knowledge they have about a participant as long as it is spread over different Incomparable Public Keys of that participant. So the participant can choose the level of anonymity by choosing when to use a new Incomparable Public Key.

That is because nobody is able to determine whether two given public keys belong to the same private key or not. This holds even if the receiver can be tricked into responding to every correctly encrypted message (e.g. because it is an automatic system), thus indicating that the encryption has been correct. (This attack is the reason why the receiver has to make sure that only messages encrypted with a public key he has actually given away are accepted: If (and only if) two public keys correspond to the same private key, you can combine them to get a third (new!) public key corresponding to the very same private key. So without that precaution, given the receiver inadvertently acknowledges the correctness of keys, this would be a reliable test to find out whether two public keys are related.

An eavesdropper cannot determine if two messages are intended for the same receiver even if they are encrypted with the same Incomparable Public Key. He even cannot relate messages encrypted with the same public key if he knows the message's plain text (for instance, if the messages are automatically generated standard messages), because they will be encrypted using a different symmetric key K. Of course, he cannot relate messages for the same participant encrypted with different Incomparable Public Keys.

In the paper, the authors point out that Incomparable Public Keys meets Key-Privacy as defined by Bellare et al. (this is only a very small extension, since Bellare et al. already showed that ElGamal meets Key-Privacy). They also show in the Random Oracle model that determining whether two public keys correspond to the same private key is as hard as the Decisional Diffie-Hellman problem, which is assumed to be hard. Finally, they outline an Incomparable Public Key scheme using two key pairs, that can proven to be hard even without using the Random Oracle Model.

Performance

In this system, every receiver has to decrypt every message in the system with one (his) private key. The work per receiver scales linearly with the number of receivers and linearly with the number of messages per receiver and maximal answer time of a sender. While this doesn't work well for large systems, it is considerably better than most of the comparable methods of receiver anonymity that have been suggested, which scale quadratically with the number of messages per receiver and maximal answer time of sender.

More precisely, the authors point out that decryption takes about the same time as standard ElGamal decryption if the message is rejected (and not maliciously created), and roughly twice the time of standard ElGamal decryption if the message is indeed intended for the receiver. Encryption takes approximately the same time as standard ElGamal encryption.

Achievements & Shortcomings

Incomparable Public Keys meets the requirements stated above, which Waters, Felten and Sahai prove in their paper.

However, though this algorithm does scale better with the number of receivers than other methods do, the idea of sending all messages to all potential receivers doesn't work well for large groups of receivers. And if there are only few receivers, the level of anonymity granted by any procedure is not very high.

So there will be not many use-cases for which using Incomparable Public Keys on its own will be both useful and practicable. In most cases you will be better off by using a method that provides anonymity within a small group of receivers each time multiple times for each message. On the other hand, routing algorithms that does so are much more complex and difficult to implement.

Incomparable Public Keys (or similar methods) may be of use, however, in combination with or as part of other algorithms. For instance, it may be useful to use it for providing anonymity for each layer in multi-layer routing algorithms.

The very strong requirement of the sender being unable to relate messages to the same receiver will often be wasted because the sender in many cases will need sufficient information about the receiver for doing the matching based on this information in order to send something useful/provide a useful service.

References

• Waters, Felten, Sahai: Receiver Anonymity via Incomparable Public Keys. in Proceedings of the 10th ACM conference on Computer and communication security, ACM Press, 2003
• Danezis: Better Anonymous Communications. University of Cambridge, Computer Laboratory, 2004
• Menezes, Oorschot, Vanstone: Handbook of Applied Cryptography, 1996, CRC Press
• Wikipedia articles: ElGamal Encryption, Decisional Diffie-Hellman assumption, Semantic Security, Chosen-Ciphertext Attack, Malleability.