Multi-key Homomorphic Authenticators
Homomorphic authenticators (HAs) enable a client to authenticate a large collection of data elements \(m_1, \ldots , m_t\) and outsource them, along with the corresponding authenticators, to an untrusted server. At any later point, the server can generate
- PDF / 480,137 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 8 Downloads / 186 Views
2
IMDEA Software Institute, Madrid, Spain {dario.fiore,luca.nizzardo}@imdea.org Chalmers University of Technology, Gothenburg, Sweden {aikmitr,elenap}@chalmers.se
Abstract. Homomorphic authenticators (HAs) enable a client to authenticate a large collection of data elements m1 , . . . , mt 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, i.e., y = f (m1 , . . . , mt ). Recently researchers have focused on HAs as a solution, with minimal communication and interaction, to the problem of delegating computation on outsourced data. The notion of HAs studied so far, however, only supports executions (and proofs of correctness) of computations over data authenticated by a single user. Motivated by realistic scenarios (ubiquitous computing, sensor networks, etc.) in which large datasets include data provided by multiple users, we study the concept of multi-key homomorphic authenticators. In a nutshell, multi-key HAs are like HAs with the extra feature of allowing the holder of public evaluation keys to compute on data authenticated under different secret keys. In this paper, we introduce and formally define multi-key HAs. Secondly, we propose a construction of a multi-key homomorphic signature based on standard lattices and supporting the evaluation of circuits of bounded polynomial depth. Thirdly, we provide a construction of multi-key homomorphic MACs based only on pseudorandom functions and supporting the evaluation of low-degree arithmetic circuits. Albeit being less expressive and only secretly verifiable, the latter construction presents interesting efficiency properties.
1
Introduction
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 organizations (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 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 c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part II, LNCS 10032, pp. 499–530, 2016. DOI: 10.1007/978-3-662-53890-6 17
500
D. Fiore et al.
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 [27], in this work we focus on
Data Loading...
