Comparing Two Notions of Simulatability

Comparing Two Notions of SimulatabilityD. Hofheinz and D. Unruh (TCC 2005).  [publisher's version | eprint]

Abstract: In this work, relations between the security notions standard simulatability and universal simulatability for cryptographic protocols are investigated.

A simulatability-based notion of security considers a protocol π as secure as an idealization τ of the protocol task, if and only if every attack on π can be simulated by an attack on τ.

Two formalizations, which both provide secure composition of protocols, are common: standard simulatability means that for every π-attack and protocol user H, there is a τ-attack, such that H cannot distinguish π from τ. Universal simulatability means that for every π-attack, there is a τ-attack, such that no protocol user H can distinguish π from τ.

Trivially, universal simulatability implies standard simulatability. We show: the converse is true with respect to perfect security, but not with respect to computational or statistical security.

Besides, we give a formal definition of a time-lock puzzle, which may be of independent interest. Although the described results do not depend on any computational assumption, we show that the existence of a time-lock puzzle gives an even stronger separation of standard and universal simulatability with respect to computational security.