In this work we relate the various notions via direct and concrete security reductions that are tight. We start by developing the first formal model for fully hierarchical proxy signatures, which, as we point out, also addresses vulnerabilities of previous schemes when self-delegation is used. Next, we prove that proxy signatures are, in fact, equivalent to key-insulated signatures. We then use this fact and other results to establish a tight hierarchy among the key-evolving notions, showing that intrusion-resilient signatures and key-insulated signatures are equivalent, and imply forward-secure signatures. We also introduce other relations among extended notions.
Besides the importance of understanding the relationships among the various notions that were originally designed with different goals or with different system configuration in mind, our findings imply new designs of schemes. For example, many proxy signatures have been presented without formal model and proofs, whereas using our results we can employ the work on key-insulated schemes to suggest new provably secure designs of proxy signatures schemes.
Category / Keywords: foundations / Proxy Signatures, Key Evolving Signatures, Security Hierarchy, Concrete Reductions Publication Info: The extended abstract of the paper will be appeard in Eurocrypt 2004. Date: received 21 Feb 2004, last revised 23 Feb 2004 Contact author: satoshi at cs columbia edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20040223:154641 (All versions of this report) Discussion forum: Show discussion | Start new discussion