Paper 2013/401

Functional Signatures and Pseudorandom Functions

Elette Boyle, Shafi Goldwasser, and Ioana Ivan

Abstract

In this paper, we introduce two new cryptographic primitives: \emph{functional digital signatures} and \emph{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 \emph{signing keys for a function} $f$, which allow one to sign any message in the range of $f$. As a special case, this implies the ability to generate keys for predicates $P$, which allow one to sign any message $m$, for which $P(m) = 1$. 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 $F$ on any point in the domain, there are additional \emph{secret keys for a function} $f$, which allow one to evaluate $F$ on any $y$ for which there exists an $x$ such that $f(x)=y$. As a special case, this implies \emph{pseudorandom functions with selective access}, where one can delegate the ability to evaluate the pseudorandom function on inputs $y$ for which a predicate $P(y)=1$ holds. We define and provide a sample construction of a functional pseudorandom function family for prefix-fixing functions.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown status
Contact author(s)
ioanai @ mit edu
History
2013-10-29: last of 3 revisions
2013-06-20: received
See all versions
Short URL
https://ia.cr/2013/401
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/401,
      author = {Elette Boyle and Shafi Goldwasser and Ioana Ivan},
      title = {Functional Signatures and Pseudorandom Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2013/401},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/401}},
      url = {https://eprint.iacr.org/2013/401}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.