Eurocrypt 2015: Universal Signature Aggregators

Suppose you have a collection of signatures on different messages under different keys, and another party wants to verify that you have all of them. You could send all the signatures, and the other party could obtain the relevant public keys and then verify the signatures. However if you have a lot of signatures this is a lot of data to transfer. Aggregate signatures allow you to combine all the signatures into one of size independent of the number you have combined.

Most aggregate signatures make use of algebraic properties of the underlying scheme's signatures. This means that those generating the signatures to be aggregated all have to use the appropriate scheme. Venkata Koppula's talk this morning asked if we could aggregate signatures from different schemes. He went on to answer the question in the positive, calling such a tool a universal aggregator.

Syntactically, a universal signature aggregator looks like this:

Security says that given the public parameters and a public key for a signature scheme, an adversary with access to a signing oracle cannot compute a valid aggregate signature involving a signature under the given public key on a message he did not query to the signing oracle.

The idea behind the constructions is to first verify the signatures, then transform them into an aggregation-friendly form, then aggregate them. The problem now is the transformation step. At this point in the talk I expected to see some NIZK action, but the tool of choice was instead everyone's favourite hammer, indistinguishability obfuscation.

The construction presented this morning had the aggregation-friendly form of a signature be the evaluation of a one-way function on the signature tuple, with the OWF outputting points in Z_N with N an RSA modulus. Rather than passing out the key to the OWF in the parameters the setup phase generates an obfuscation of a program that evaluates the OWF. This means (selective) security can be shown by replacing this obfuscated program with an obfuscation of a version of the program that refuses to act on the selected challenge signature tuple.

There are additional constructions in the paper, including one with adaptive security, but they all follow the same general outline. The paper (joint work with Susan Hohenberger and Brent Waters) can be found on eprint.