Adaptively Secure Fully Homomorphic Signatures Based on Lattices.

Abstract

In a homomorphic signature scheme, given the public key and a vector of signaturesσ: = (σ1,..., σl) over l messages µ: = (µ1,..., µl), there exists an efficient algorithm to produce a signature σ ′ for µ = f(µ). Given the tuple (σ′, µ, f), anyone can then publicly verify the validity of the signature σ′. Inspired by the recent (selectively secure) key-homomorphic functional encryption for circuits, re-cent 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 adaptively secure homomorphic signature scheme that can eval-uate any circuit over signed data. For poly-logarithmic depth circuits, our scheme achieves adaptive security under the standard Small Integer Solution (SIS) assumption. For 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. 1