IMDEA Software

IMDEA initiative

Home > News > 2021 > Dario Fiore, Aikaterini Mitrokotsa, Luca Nizzardo and Elena Pagnin receive the 2020 Premium Award for Best Paper in the IET

February 1, 2021

Dario Fiore, Aikaterini Mitrokotsa, Luca Nizzardo and Elena Pagnin receive the 2020 Premium Award for Best Paper in the IET

Scientific results

The researchers Dario Fiore (IMDEA Software Institute), Aikaterini Mitrokotsa (Chalmers University of Technology), Luca Nizzardo (Protocol Labs Research) and Elena Pagnin (Lund University) receive the 2020 Premium Award for Best Paper in the IET (The Institution of Engineering and Technology) for the paper: “Multi-Key Homomorphic Authenticators.”

The technological innovations offered by modern IT systems are changing the way digital data is collected, stored, processed, and consumed. As an example, think of an application where data is collected by some organisations (e.g. hospitals), stored and processed on remote servers (e.g. the Cloud) and finally consumed by other users (e.g. medical researchers) on other devices. On the one hand, this computing paradigm is very attractive, particularly as data can be shared and exchanged by multiple users. On the other hand, it is evident that in such scenarios, one may be concerned about security: while the users that collect and consume the data may trust each other (up to some extent), trusting the Cloud can be problematic for various reasons. More specifically, two main security concerns to be addressed are those about the privacy and authenticity of the data stored and processed in untrusted environments.

While it is widely known that privacy can be solved in such a setting using, e.g. homomorphic encryption, in this work, the authors focus on the orthogonal problem of providing authenticity of data during computation. Towards this goal, their contribution is on advancing the study of homomorphic authenticators (HAs), a cryptographic primitive that has been the subject of recent work.

Homomorphic authenticators (HAs) enable a client to authenticate a large collection of data elements and outsource them, along with the corresponding authenticators, to an untrusted server. At any later point, the server can generate a short authenticator vouching for the correctness of the output y of a function f computed on the outsourced data. The notion of HAs studied in prior work, however, only supports executions of computations over data authenticated by a single user.

In this paper, the authors introduce and formally define multi‐key HAs, they propose a construction of a multi‐key homomorphic signature based on standard lattices and supporting the evaluation of circuits of bounded polynomial depth, and they provide a construction of multi‐key homomorphic MACs based only on pseudorandom functions and supporting the evaluation of low‐degree arithmetic circuits.

In conclusion, this paper provides an innovative solution through the notion of multi‐key HAs. This primitive guarantees that the corruption of one user affects the data of that user only, but does not endanger the authenticity of computations among the other (un‐corrupted) users of the system. Moreover, the proposed system is dynamic, in the sense that compromised users can be assigned new keys and be easily reintegrated.

This paper is an extended version (with additional results and detailed proofs) of the paper “Multi-Key Homomorphic Authenticators” presented by the same authors at ASIACRYPT 2016.