As we known, a homomorphic signature scheme consists of the usual algorithms $(\text{KeyGen} , \text{Sign} , \text{Verify})$ as well as an additional algorithm $\text{Evaluate}$ that “translates” functions on messages to functions on signatures. If $\sigma$ is a valid set of signatures on messages $m$, then $\text{Evaluate}(f, \sigma)$ should be a valid signature for $f(m)$.

In several papers I read, the evaluation algorithm is defined as $$\sigma' \gets \text{Evaluate}(pk, \tau, f, \vec{\sigma})$$ and the verification algorithm is defined as $$0 \text{ or } 1 \gets \text{Verify}(pk, \tau, m, f, \sigma')$$ such that for every messages $\vec{m}$, every tag $\tau$, there is $$ \text{Verify}(pk, \tau, f(\vec{m}), f, \text{Evaluate}(pk, \tau, f, \vec{\sigma})) = 1$$ I want to know why $f$ is one of the inputs in the algorithm $\text{Verify}$.

Why cannot we the define the verification algorithm as $$0 \text{ or } 1 \gets \text{Verify}'(pk, \tau, m, \sigma')$$ such that for every messages $\vec{m}$, every tag $\tau$, there is $$ \text{Verify}'(pk, \tau, f(\vec{m}), \text{Evaluate}(pk, \tau, f, \vec{\sigma})) = 1$$

I think that homomorphic signature schemes are similar to homomorphic encryption scheme. In homomorphic encryption schemes, the decryption algorithm does not use $f$ to decrypt the ciphertext. If the verification algorithm needs $f$, how can we verify correctly if the signatures are calculated by the evaluation algorithm for more than once?


The function $f$ is part of the input to $\mathsf{Verify}$, because the goal of homomorphic signatures is to compute authenticated functions on signed messages. In particular, given a message $z$ and a signature $\sigma_z$, we want to not only verify that $\sigma_z$ is a valid signature for $z$, but moreover that $z$ is the output of some function $f$ applied to some inputs signed under some tag $\tau$.

To take an example from this paper, you can think of the tag $\tau$ as being "grades" and a list $(m_i, \sigma_i)$ being a bunch of individual grades separately signed under tag $\tau$. Homomorphic signatures now enable the owner of these signed individual grades to compute a signature $\sigma_z$ that attests that some value $z$ is indeed the average of the grades $m_i$.

This authenticity requirement is in stark contrast to (fully) homomorphic encryption, where you only want the ability to alter ciphertexts, but make no requirements on the authenticity of the produced encryption.

A notion that may be closer to what you are looking for are so called Malleable Signatures (see Def. 3.1), which are defined by the algorithms $\mathsf{Keygen}, \mathsf{Sign}, \mathsf{Verify}, \mathsf{SigEval}$, where the first three algorithms are defined exactly as in any standard signature scheme. The algorithm $\mathsf{SigEval}$ takes as input $(\mathsf{pk}, f, \vec{m}, \vec{\sigma})$, where $\mathsf{pk}$ is a public key, $f$ is a function, $\vec{m}$ is a vector of messages, and $\vec{\sigma}$ is the vector of corresponding signatures. It outputs a new signature $\sigma'$ such that $\mathsf{Verify}(\mathsf{pk}, f(\vec{m}), \sigma') = 1$.

Note that if you do not want to authenticate the computed function, then it may also not be necessary to use tags in the definition of your signature scheme.

| improve this answer | |
  • $\begingroup$ Thanks. In the homomrphic encryption scheme, can we only verify the signatures that have been calculated once by the evlauation algorithm? Or can we verify the signatures that have been calculated by multiple times, where the authenticated function is the input of the evlauation algorithm at the last time? $\endgroup$ – TeamBright Apr 6 at 14:48
  • $\begingroup$ I guess that depends on the scheme. In general this does not have to be true I think. The scheme presented in eprint.iacr.org/2014/897.pdf for evaluating arbitrary circuits states that composition is possible in their scheme (see paragraph "composition" on page 2). $\endgroup$ – Cryptonaut Apr 6 at 14:53
  • $\begingroup$ One more question, is there a "fully homomorphic" version of malleable signatures? I mean, arbitrary circuit is admissible in that scheme. Does it have any name like "fully malleable signatures" or somthing else? $\endgroup$ – TeamBright Apr 6 at 15:01
  • $\begingroup$ I don't know whether there are explicit non-generic constructions, but I assume that you can construct them generically using SNARKs in combination with universal circuits, which would probably be pretty inefficient. Not sure though $\endgroup$ – Cryptonaut Apr 6 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.