Homomorphic Signatures and Message Authentication Codes

Homomorphic message authenticators allow to validate computation on previously signed data. The holder of a dataset {

m

1

, …,

m

ℓ

} uses her secret key

sk

to produce corresponding tags (

σ

1

, …,

σ

ℓ

) and stores the authenticated dataset on a remote server. Later the server can (publicly) compute

m

 = 

f

(

m

1

, …,

m

ℓ

) together with a succinct tag

σ

certifying that

m

is the correct output of the computation

f

. A nice feature of homomorphic authenticators is that the validity of this tag can be verified

without

having to know the original dataset. This latter property makes the primitive attractive in a variety of context and applications, including, for instance, verifiable delegation of computation on outsourced data.

In this short survey, I will give an overview of the state of the art in the areas of homomorphic signatures and message authentication codes. I will (briefly) describe some of the most recent results and provide an overview of the main challenges that remain to address.