Paper 2014/820

Operational Signature Schemes

Michael Backes, Ozgur Dagdelen, Marc Fischlin, Sebastian Gajek, Sebastian Meiser, and Dominique Schröder


Functional encryption, as introduced by Boneh, Sahai, and Waters (TCC'11), generalizes public-key encryption systems to include functional decryption capabilities. Recently, Boyle et al. as well as Bellare and Fuchsbauer (both PKC'14) formalized analogous notions for signature schemes. Here we discuss that both their notions are limited in terms of expressiveness in the sense that they cannot cast known signature schemes supporting operations on data in their frameworks. We therefore propose a notion of what we call, for sake of distinctiveness, operational signature schemes which captures functional signatures, policy-based signatures, sanitizable signatures, P-homomorphic signatures, ring signatures, aggregate signatures etc., and also their message authentication code counterparts. We discuss possible instantiations for operational signatures. We give some positive result about achieving our general notion of operational signatures presenting a compact construction that relies on a new combination of indistinguishability obfuscation and random oracles. We then indicate that it is unlikely to be able to instantiate operational signature schemes in general using one-wayness and, under some circumstances, even using specific ``non-interactive'' assumptions like RSA.

Note: Our contributions include and subsume the preliminary work called (Delegatable) Functional Signatures (DFS) by Backes, Meiser, and Schroeder (ePrint Archive 2013/408). Here we generalize their notions and results in several ways. Our definition covers both MACs and signature schemes and admits arbitrary input sequences, thereby covering a much larger class of known signature schemes. We also provide a construction for the more general notion. We also adapt their impossibility result, which shows that constructing DFS requires blind signatures to the more general case of OSS.

Available format(s)
Publication info
Functional cryptographyrandom oracle obfuscationmessage authentication systemsexistential relations
Contact author(s)
sebastian gajek @ gmail com
2014-10-12: last of 2 revisions
2014-10-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michael Backes and Ozgur Dagdelen and Marc Fischlin and Sebastian Gajek and Sebastian Meiser and Dominique Schröder},
      title = {Operational Signature Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2014/820},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.