The main contribution of this paper is twofold. First, we propose DFS, a novel cryptographic primitive that unifies several seemingly different signature primitives, including functional signatures as defined by Boyle, Goldwasser, and Ivan (eprint 2013/401), sanitizable signatures, identity based signatures, and blind signatures. To achieve this unification, we present several definitions of unforgeability and privacy. Finding appropriate and meaningful definitions in this context is challenging due to the natural mealleability of DFS and due to the multi-party setting that may involve malicious keys.
Second, we present a complete characterization of the instantiability of DFS under common assumptions, like the existence of one-way functions. Here, we present both positive and negative results. On the positive side we show that DFS not achieving our notion of privacy can be constructed from one-way functions. Furthermore, we show that unforgerable and private DFS can be constructed from doubly enhanced trapdoor permutations. On the negative side we show that the previous result is optimal regarding its underlying assumptions presenting an impossibility result for unforgeable private DFS from one-way permutations.Category / Keywords: public-key cryptography / Functional signatures, delegatable functional signatures, malleable signature schemes Date: received 20 Jun 2013, last revised 10 Oct 2013 Contact author: ds at ca cs uni-saarland de Available format(s): PDF | BibTeX Citation Version: 20131010:093752 (All versions of this report) Short URL: ia.cr/2013/408 Discussion forum: Show discussion | Start new discussion