Universally Composable Zero-Knowledge Arguments and Commitments from Signature Cards

Universally Composable Zero-Knowledge Arguments and Commitments from Signature CardsD. Hofheinz, D. Unruh, and J. Müller-Quade (Moraviacrypt '05, Tatra Mt. Math. Pub., 2007).  [publisher's version | eprint]

Abstract: The framework of universal composability (UC) allows the modular design of cryptographic protocols. However universal composability is a very strict notion of security and the cryptographic tasks of zero-knowledge arguments as well as bit commitment schemes cannot be built from scratch in such a framework. To implement these tasks, additional "helping" functionalities are needed as set-up assumptions. Examples for sufficient set-up assumptions are the common reference string, the random oracle, or a public key infrastructure.

However, in all constructions so far, all these helping functionalities have to be used exclusively as a "helping" functionality, and cannot directly serve any other purpose without endangering the universal composability. E.g., a public key infrastructure used as set-up assumptions in a bit commitment scheme usually may not be used for e.g., encrypting other communication.

In this work, we introduce the concept of catalysts. Informally, a catalyst for some protocol task is a functionality that allows for universally composable implementation of that task, and may nevertheless still be used by arbitrary other applications.

We show that catalysts exist for zero-knowledge and bit commitment and thus, using a result of Canetti et al., for all well formed functionalities. And, what is more, we show that a signature card, which is in accordance with the requirements posed by the German law can be used as such a catalyst. This is of practical importance, as an infrastructure of signature cards is about to be set up in several nations of the EU. Our work proves that this infrastructure can be used to securely implement additional applications without negative side effects (with a non-catalytic approach, one would have to disallow any other use of the signature-cards if using them for composable bit commitment).