This is taken from my Master Thesis on

Homomorphic Signatures over Lattices.

## What are homomorphic signatures

Imagine that Alice owns a large data set, over which she would like to perform some computation. In a homomorphic signature scheme, Alice signs the data set with her secret key and uploads the signed data to an untrusted server. The server then performs the computation modeled by the function to obtain the result over the signed data.

Alongside the result , the server also computes a signature certifying that is the correct result for . The signature should be short – at any rate, it must be independent of the size of . Using Alice’s public verification key, anybody can verify the tuple without having to retrieve all the data set nor to run the computation on their own again.

The signature is a *homomorphic signature*, where *homomorphic* has the same meaning as the mathematical definition: `*mapping of a mathematical structure into another one in such a way that the result obtained by applying the operations to elements of the first structure is mapped onto the result obtained by applying the corresponding operations to their respective images in the second one*‘. In our case, the *operations* are represented by the function , and the *mapping* is from the matrices to the matrices .

Notice how the very idea of **homomorphic signatures challenges the basic security requirements of traditional digital signatures**. In fact, for a traditional signatures scheme we require that it should be computationally infeasible to generate a valid signature for a party without knowing that party’s private key. Here, we *need* to be able to generate a valid signature on *some data* (i.e. results of computation, like ) *without* knowing the secret key. What we require, though, is that it must be computationally infeasible to forge a valid signature for a result . In other words, the security requirement is that *it must not be possible to cheat on the signature of the result*: if the provided result is validly signed, then it must be the *correct* result.

The next ideas stem from the analysis of the signature scheme devised by Gorbunov, Vaikuntanathan and Wichs. It relies on the *Short Integer Solution* hard problem on lattices. The scheme presents several limitations and possible improvements, but it is also the first homomorphic signature scheme able to evaluate arbitrary arithmetic circuits over signed data.

Continue reading “A note on the hopes for Fully Homomorphic Signatures”