Fail-Stop Signature Scheme with TTP and Its UC-Security

Aggelos Kiayias, Hong-Sheng Zhou

Nikita Snetkov, Jelizaveta Vakarjuk, Peeter Laud

Ryan Amiri

Olivier Blazy, Céline Chevalier

Kaoru Kurosawa, Jun Furukawa

Abstract. How to define the security of undeniable signature schemes is a challenging task. This paper presents two security definitions of undeniable signature schemes which are more useful or natural than the existing definition. It then proves their equivalence. We first define the UC-security, where UC means universal composability. We next show that there exists a UC-secure undeniable signature scheme which does not satisfy the standard definition of security that has been believed to be adequate so far. More precisely, it does not satisfy the invisibility defined by [10]. We then show a more adequate definition of invisibility which captures a wider class of (naturally secure) undeniable signature schemes. We finally prove that the UC-security against non-adaptive adversaries is equivalent to this definition of invisibility and the strong unforgeability in FZK-hybrid model, where FZK is the ideal ZK functionality. Our result of equivalence implies that all the known proven secure undeniable signature schemes (including Chaum’s scheme) are UC-secure if the confirmation/disavowal protocols are both UC zero-knowledge.

Jonathan I. Katz, Aggelos Kiayias, Hong-Sheng Zhou +1 more

Universally composable (UC) protocols retain their security properties even when run concurrently alongside arbitrary other protocols. Unfortunately, it is known that UC multiparty computation (for general functionalities, and without assuming honest majority) is impossible without some form of setup. To circumvent this impossibility, various complete setup assumptions have been proposed. With only a few exceptions, past work has viewed these setup assumptions as being implemented by some ideal, incorruptible entity. Any such entity is thus a single point of failure, and security fails catastrophically in case the setup entity is subverted by an adversary. We propose here a clean, general, and generic approach for distributing trust among m arbitrary setups, by modeling potential corruption of setups within the UC framework, where such corruption might be fail-stop, passive, or arbitrary and is in addition to possible corruption of the parties themselves. We show several feasibility and impossibility results in this model, for different specifications of the corruptible sets. For example, we show that given m complete setups, up to t of which might be actively corrupted in an adaptive manner, general multiparty computation with no honest majority is possible if and only if t < m/2.