Tightly-Secure Signatures from Chameleon Hash Functions

par M. Jiaxin Pan (Ruhr University Bochum)

mardi 25 nov. 2014, 08:00 → 09:00 Europe/Paris

XR203 (Université de Limoges)

In this talk, we give a new framework for obtaining signatures with a tight security reduction from standard hardness assumptions. Concretely, - We show that any Chameleon Hash function can be transformed into a (binary) tree-based signature scheme with tight security. The transformation is in the standard model, i.e., it does not make use of any random oracle. - For specific assumptions (such as RSA, Diffie-Hellman and Short Integer Solution (SIS)) we further manage to obtain a more efficient flat-tree construction. Our framework explains and generalizes most of the existing schemes as well as providing a generic means for constructing tight signature schemes based on arbitrary assumptions, which improves the standard Merkle tree transformation. Moreover, we obtain the first tightly secure signature scheme from the SIS assumption and several schemes based on Diffie-Hellman in the standard model. During the talk, I will mainly focus on the generic transformation and, if time permits, I will also show some concrete constructions from Diffie-Hellman and SIS.