Long-term Security and Universal Composability (Journal of Cryptology, 2010)
Jörn Müller-Quade, Dominique Unruh
[ eprint | official ]

Algorithmic progress and future technological advances threaten today’s cryptographic protocols. This may allow adversaries to break a protocol retrospectively by breaking the underlying complexity assumptions long after the execution of the protocol. Long-term secure protocols, protocols that after the end of the execution do not reveal any information to a then possibly unlimited adversary, could meet this threat. On the other hand, in many applications, it is necessary that a protocol is secure not only when executed alone, but within arbitrary contexts. The established notion of universal composability (UC) captures this requirement.

This is the first paper to study protocols which are simultaneously long-term secure and universally composable. We show that the usual set-up assumptions used for UC protocols (e.g., a common reference string) are not sufficient to achieve long-term secure and composable protocols for commitments or zero-knowledge protocols.

We give practical alternatives (e.g., signature cards) to these usual setup-assumptions and show that these enable the implementation of the important primitives commitment and zero-knowledge protocols.