Homomorphic Signatures from Chameleon Hash Functions

Abstract

Homomorphic signature schemes provide a feasible solution to the authenticity problem on an untrusted server, such as cloud. In a homomorphic signature scheme, given a $n$-length signed dataset $\delta=\{\delta_1, \delta_2,\delta_3, \cdots, \delta_k\} $ and its corresponding message set $\mu=\{\mu_1, \mu_2,\mu_3, \cdots, \mu_k\} $, anyone can publicly perform computations and produce a new signature $\delta^{'}$ for the messages $\mu^{'}=f(\mu_1, \mu_2,\mu_3, \cdots, \mu_k)$, where $f$ is a function or a circuit. If the generated homomorphic signature $\delta^{'}$ is valid, then the owner of the dataset (such as cloud users) convinces that $\mu^{'}$ is indeed the correct output of the function $f$ over the original messages even if he forgets it. In this work, the main contribution is to build a bridge between leveled Fully Homomorphic Signature Scheme (FHSS) and Homomorphic Chameleon Hash Function (HCHF), which is a new cryptographic primitive introduced by us based on prior works. We first present the definition and specific construction of HCHF and then use this forceful technique to construct leveled fully homomorphic signature schemes for any polynomial-depth circuit. In our standard model scheme, the size of evaluated homomorphic signature grows polynomially in the depth of the circuit. The security of our scheme is based on the property of collision resistance of HCHF, which can be reduced to the Small Integer Solution (SIS) in hard random lattices.

DOI: http://dx.doi.org/10.5755/j01.itc.46.2.14320