Anonymity-Preserving Public-Key Encryption: A Constructive Approach

Markulf Kohlweiss, Ueli Maurer, Cristina Onete, Björn Tackmann, Daniele Venturi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A receiver-anonymous channel allows a sender to send a message to a receiver without an adversary learning for whom the message is intended. Wireless broadcast channels naturally provide receiver anonymity, as does multi-casting one message to a receiver population containing the intended receiver. While anonymity and confidentiality appear to be orthogonal properties, making anonymous communication confidential is more involved than one might expect, since the ciphertext might reveal which public key has been used to encrypt. To address this problem, public-key cryptosystems with enhanced security properties have been proposed.

We investigate constructions as well as limitations for preserving receiver anonymity when using public-key encryption (PKE). We use the constructive cryptography approach by Maurer and Renner and interpret cryptographic schemes as constructions of a certain ideal resource (e.g. a confidential anonymous channel) from given real resources (e.g. a broadcast channel). We define appropriate anonymous communication resources and show that a very natural resource can be constructed by using a PKE scheme which fulfills three properties that appear in cryptographic literature (IND-CCA, key-privacy, weak robustness). We also show that a desirable stronger variant, preventing the adversary from selective ”trial-deliveries” of messages, is unfortunately unachievable by any PKE scheme, no matter how strong. The constructive approach makes the guarantees achieved by applying a cryptographic scheme explicit in the constructed (ideal) resource; this specifies the exact requirements for the applicability of a cryptographic scheme in a given context. It also allows to decide which of the existing security properties of such a cryptographic scheme are adequate for the considered scenario, and which are too weak or too strong. Here, we show that weak robustness is necessary but that so-called strong robustness is unnecessarily strong in that it does not construct a (natural) stronger resource.
Original languageEnglish
Title of host publicationPrivacy Enhancing Technologies - 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings
Number of pages21
ISBN (Electronic)978-3-642-39077-7
ISBN (Print)978-3-642-39076-0
Publication statusPublished - 2013
Event13th Privacy Enhancing Technologies Symposium - Bloomington, IN, United States
Duration: 10 Jul 201312 Jul 2013


Conference13th Privacy Enhancing Technologies Symposium
Abbreviated titlePETS 2013
CountryUnited States
CityBloomington, IN
Internet address


Dive into the research topics of 'Anonymity-Preserving Public-Key Encryption: A Constructive Approach'. Together they form a unique fingerprint.

Cite this