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 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.