Paper 2006/422

Long-term Security and Universal Composability

Joern Mueller-Quade and Dominique Unruh

Abstract

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.

Note: Original version 2006-11-19. Revised 2007-01-27: Incorporated TCC referee comments. Revised 2009-08-10: Strongly extended and (hopefully) improved version. (Thanks to Oded Goldreich for many comments.) Revised 2010-04-28: Many corrections and improvements. Also contains an additional section on generalising the notion of long-term revealing functionalities. (Thanks to the reviewers of the Journal of Cryptology for comments.)