Paper 2014/420

Bounded Fully Homomorphic Signature Schemes

Xiang Xie and Rui Xue

Abstract

Homomorphic signatures enable anyone to publicly perform computations on signed data and produce a compact tag to authenticate the results. In this paper, we construct two bounded fully homomorphic signature schemes, as follows. \begin{itemize} \item For any two polynomials $d=d(\lambda), s=s(\lambda)$, where $\lambda$ is the security parameter. Our first scheme is able to evaluate any circuit on the signatures, as long as the depth and size of the circuit are bounded by $d$ and $s$, respectively. The construction relies on indistinguishability obfuscation and injective (or polynomially bounded pre-image size) one-way functions. \medskip \item The second scheme, removing the restriction on the size of the circuits, is an extension of the first one, with succinct verification and evaluation keys. More specifically, for an a-prior polynomial $d=d(\lambda)$, the scheme allows to evaluate any circuit on the signatures, as long as the depth of the circuit is bounded by $d$. This scheme is based on differing-inputs obfuscation and collision-resistant hash functions and relies on a technique called recording hash of circuits. \end{itemize} Both schemes enjoy the composition property. Namely, outputs of previously derived signatures can be re-used as inputs for new computations. The length of derived signatures in both schemes is independent of the size of the data set. Moreover, both constructions satisfy a strong privacy notion, we call {\em semi-strong context hiding}, which requires that the derived signatures of evaluating any circuit on the signatures of two data sets are {\em identical} as long as the evaluations of the circuit on these two data sets are the same.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
homomorphic signatureindistinguishability obfuscationdiffering-inputs obfuscation
Contact author(s)
xiexiangiscas @ gmail com
History
2014-06-05: received
Short URL
https://ia.cr/2014/420
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/420,
      author = {Xiang Xie and Rui Xue},
      title = {Bounded Fully Homomorphic Signature Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2014/420},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/420}},
      url = {https://eprint.iacr.org/2014/420}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.