Universal Composition with Responsive Environments

Authors

Jan Camenisch (IBM Research - Zurich) and Robert R. Enderlein (IBM Research - Zurich and ETH Zurich) and Stephan Krenn (AIT) and Ralf Küsters (University of Trier) and Daniel Rausch (University of Trier)

Abstract

A increasingly popular approach to proving the security of protocols is to define the desired security and functional properties by an ideal functionality and then to prove that a protocol realizes the functionality within a universal composability framework. When specifying such ideal functionalities, one often requires the adversary (or environment) to provide some meta-information, such as cryptographic values of signatures, ciphertexts, and keys. Similarly, when designing protocols, the adversary/environment needs to provide, for example, signaling information and corruption statuses of protocol participants. Intuitively, one would expect that such requests are answered immediately. However, in none of the existing models for universal composability this is guaranteed: adversaries and environments can freely activate protocols and ideal functionalities without answering such requests, resulting in dangling and interleaving requests. We call this issue the non-responsiveness problem. It is typically very cumbersome to properly deal with such intermediate activations and interleaved requests and there is no generally applicable method to handle such activations. If fact, protocol designers often do not even consider this issue and miss to specify the behavior of their protocols and ideal functionalities in these situations. This unfortunately results in undefined or even flawed specifications, making it impossible to use such protocols/ideal functionalities in higher level protocols and carrying out rigorous security proofs. What makes the non-responsiveness problem and its consequences particularly disturbing is that they are merely a modeling artifact: it would be very natural if the mentioned requests were answered immediately by adversaries/environments as they are used for modeling purposes only and allowing adversaries/environments to not answer them immediately does not model any real attack.

This paper solves the non-responsiveness problem and its negative consequences by proposing a framework for universal composability with responsive environments and adversaries. In a nutshell, when a protocol or functionality sends what we call a restricting message to the adversary/environment, the latter must provide a valid response before any other protocol/functionality is activated. Hence, protocol designers can declare requests for meta-information to be restricting in order to guarantee that such requests are answered immediately, and hence, they do not have to worry about modeling artefacts resulting from such requests not being answered immediately. Our concepts apply to all existing models for universal composability, we provide formal theorems for the IITM model and discuss it the UC and GNUC models.

Venue

22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2016)

Place and Date

Hanoi, Vietnam, December 4-8, 2016

Publication Reference

Jan Camenisch, Robert R. Enderlein, Stephan Krenn, Ralf Küsters, and Daniel Rausch, " Universal Composition with Responsive Environments", IACR Cryptology ePrint Archive , 2016:034, 2016.

Bibtex

@inproceedings{cekkr16, author    = {Jan Camenisch and Robert R. Enderlein and Stephan Krenn and Ralf K{\"{u}}sters and Daniel Rausch}, title     = {{Universal Composition with Responsive Environments}}, booktitle = {Advances in Cryptology - {ASIACRYPT} 2016, Part {II}}, pages     = {807--840}, year      = {2016}, editor    = {Jung Hee Cheon and Tsuyoshi Takagi}, series    = {Lecture Notes in Computer Science}, volume    = {10032}, }

[Download]

Stephan Krenn (AIT), Kai Samelin (IBM Research -- Zurich and Technical University of Darmstadt), and Dieter Sommer (IBM Research -- Zurich)

Abstract

Sanitizable signatures schemes ($\SSS$) allow to alter admissible blocks of a signed message by a designated party named the sanitizer. This primitive can be used to remove or alter sensitive data from already signed messages without involvement of the original signer.
Current state-of-the-art security definitions of $\SSS$s only define a "weak" form of security. Namely, the unforgeability, accountability and transparency definitions are not strong enough to be meaningful in certain use-cases. We identify some of these use-cases, close this gap by introducing stronger definitions and show how to alter an existing construction to meet our desired security level. Moreover, we clarify a small yet important detail in the state-of-the-art privacy definition. Our work allows to deploy this primitive in more and different scenarios.

Venue

10th DPM International Workshop on Data Privacy Management, DPM 2015 (http://deic.uab.cat/conferences/dpm/dpm2015/)

Place and Date

Vienna, Austria, September 21st – 22nd, 2015

Publication Reference

Stephan Krenn, Kai Samelin, and Dieter Sommer, "Stronger Security Definition for Sanitizable Signatures", Data Privacy Management - DPM 2015, Vienna, Austria, September 21–22, 2015.

Bibtex

@inproceedings{cklmnp15, Author    = {Stephan Krenn and Kai Samelin and Dieter Sommer}, Title     = {{Stronger Security Definition for Sanitizable Signatures}}, Booktitle = {Data Privacy Management -- {DPM} 2015, Vienna, Austria}, Year      = {2015}, Publisher = {Springer} }

[Download]

Jan Camenisch (IBM Research -- Zurich), Stephan Krenn (AIT), Anja Lehmann (IBM Research -- Zurich), Gert L. Mikkelsen (Alexandra Institute), Gregory Neven (IBM Research -- Zurich), and Michael Ø. Pedersen (Miracle A/S)

Abstract

Privacy-enhancing attribute-based credentials (PABCs) are the core ingredients to privacy-friendly authentication systems. They allow users to obtain credentials on attributes and prove possession of these credentials in an unlinkable fashion while revealing only a subset of the attributes. In practice, PABCs typically need additional features like revocation, pseudonyms as privacy-friendly user public keys, or advanced issuance where attributes can be ``blindly'' carried over into new credentials. For many such features, provably secure solutions exist in isolation, but it is unclear how to securely combined them into a full-fledged PABC system, or even which properties such a system should fulfill.
We provide a formal treatment of PABCs supporting a variety of  features by defining their syntax and security properties, resulting in the most comprehensive definitional framework for PABCs so far. Unlike previous efforts, our definitions are not targeted at one specific use-case; rather, we try to capture generic properties that can be useful in a variety of scenarios. We believe that our definitions can also be used as a starting point for diverse application-dependent extensions and variations of PABCs. We present and prove secure a generic and modular construction of a PABC system from simpler building blocks, allowing for a ``plug-and-play'' composition based on different instantiations of the building blocks. Finally, we give secure instantiations for each of the building blocks.

Venue

22nd International Conference on Selected Areas in Cryptography, SAC 2015 (http://sacconference.org/)

Place and Date

Mount Allison University, Sackville, New Brunswick, Canada, August 12th – 14th, 2015

Publication Reference

Jan Camenisch, Stephan Krenn, Anja Lehmann, Gert L. Mikkelsen, Gregory Neven, and Michael Ø. Pedersen, "Formal Treatment of Privacy-Enhancing Credential Systems", Selected Areas in Cryptography - SAC 2015, Sackville, New Brunswick, Canada, August 12–14, 2015.

[Download]

Bibtex

@inproceedings{cklmnp15,
   Author    = {Jan Camenisch and Stephan Krenn and Anja Lehmann and Gert L. Mikkelsen and Gregory Neven and Michael {\O}. Pedersen},
   Title     = {{Formal Treatment of Privacy-Enhancing Credential Systems}},
   Booktitle = {Selected Areas in Cryptography - {SAC} 2013, Sackville, New Brunswick, Canada},   
   Year      = {2015}, 
   Publisher = {Springer}
}