[BGI14] Functional Signatures and Pseudorandom Functions

Authors: Elette Boyle, Shafi Goldwasser, Ioana Ivan | Venue: PKC 2014 | Source

Abstract

In this paper, we introduce two new cryptographic primitives: functional digital signatures and functional pseudorandom functions.

In a functional signature scheme, in addition to a master signing key that can be used to sign any message, there are signing keys for a function , which allow one to sign any message in the range of . As a special case, this implies the ability to generate keys for predicates , which allow one to sign any message , for which .

We show applications of functional signatures to constructing succinct non-interactive arguments and delegation schemes. We give several general constructions for this primitive based on different computational hardness assumptions, and describe the trade-offs between them in terms of the assumptions they require and the size of the signatures.

In a functional pseudorandom function, in addition to a master secret key that can be used to evaluate the pseudorandom function on any point in the domain, there are additional secret keys for a function , which allow one to evaluate on any for which there exists an such that . As a special case, this implies pseudorandom functions with selective access, where one can delegate the ability to evaluate the pseudorandom function on inputs for which a predicate holds. We define and provide a sample construction of a functional pseudorandom function family for prefix-fixing functions.

BibTeX

@Inproceedings{PKC:BoyGolIva14,
  author = {Elette Boyle and Shafi Goldwasser and Ioana Ivan},
  title = {Functional Signatures and Pseudorandom Functions},
  pages = {501--519},
  editor = {Hugo Krawczyk},
  booktitle = {PKC~2014: 17th International Conference on Theory and Practice of Public Key Cryptography},
  volume = {8383},
  series = {Lecture Notes in Computer Science},
  address = {Buenos Aires, Argentina},
  month = {mar~26--28},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2014},
  doi = {10.1007/978-3-642-54631-0_29},
}