Paper 2014/916

Adaptively Secure Fully Homomorphic Signatures Based on Lattices

Xavier Boyen, Xiong Fan, and Elaine Shi

Abstract

In a homomorphic signature scheme, given the public key and a vector of signatures $\vec{\sigma}:= (\sigma_1, \ldots, \sigma_l)$ over $l$ messages $\vec{\mu}:= (\mu_1, \ldots, \mu_l)$, there exists an efficient algorithm to produce a signature $\sigma'$ for $\mu = f(\vec{\mu})$. Given the tuple $(\sigma', \mu, f)$, anyone can then publicly verify the validity of the signature $\sigma'$. Inspired by the recent (selectively secure) key-homomorphic functional encryption for circuits, recent works propose fully homomorphic signature schemes in the selective security model. However, in order to gain adaptive security, one must rely on generic complexity leveraging, which is not only very inefficient but also leads to reductions that are ``unfalsifiable''. In this paper, we construct the first \emph{adaptively secure} homomorphic signature scheme that can evaluate any circuit over signed data. For {\it poly-logarithmic depth} circuits, our scheme achieves adaptive security under the standard {\it Small Integer Solution} (SIS) assumption. For {\it polynomial depth} circuits, the security of our scheme relies on sub-exponential SIS --- but unlike complexity leveraging, the security loss in our reduction depends only on circuit depth and on neither message length nor dataset size.

Note: This paper is currently under submission to a conference. This work is subsequent to the the recent works by Gorbunov et al. (2014/463) and Wichs (2014/451), but concurrent with the more recent work by Gorbunov et al. (2014/897).

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
xfan @ cs umd edu
History
2015-11-14: last of 3 revisions
2014-11-06: received
See all versions
Short URL
https://ia.cr/2014/916
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/916,
      author = {Xavier Boyen and Xiong Fan and Elaine Shi},
      title = {Adaptively Secure Fully Homomorphic Signatures Based on Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2014/916},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/916}},
      url = {https://eprint.iacr.org/2014/916}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.