International Association
for Cryptologic Research

The progress in communication and hardware technology increases the computational capabilities of personal devices.

Data is produced massively from ubiquitous devices that cannot be stored locally. Moreover, third party authorities

in order to increase their value in the market with more knowledge, seek to collect

individual data inputs, such that they can make a decision with more relevant information. Aggregators, acting as third

parties, are interested in learning a statistical function as the sum over a census of data. Users are reluctant to

reveal their information in cleartext, since it is treated as personal sensitive information. The paradoxical paradigm

of preserving the privacy of individual data while granting an untrusted third party to learn in cleartext a function

thereof, is partially addressed by the current privacy preserving aggregation protocols.

Current solutions are either focused on a honest-but-curious Aggregator who is trusted to follow the rules of the

protocol or they model a malicious Aggregator with trustworthy users. That limits the security analysis to users who

are trustworthy to not share any secret information with a malicious Aggregator. In this paper we are the first to

propose a protocol with fully malicious users who collude with a malicious Aggregator in order

to forge a message of a trusted user. We introduce the new cryptographic primitive of \\emph{convertible tag}, that

consists of a two-layer authentication tag. Users first tag their data with their secret key and then an untrusted

\\emph{Converter} converts the first layer tags in a second layer. The final tags allow the Aggregator to produce a

proof for the correctness of a computation over users\' data. Security and privacy of the scheme is preserved against

the \\emph{Converter} and the Aggregator, under the notions of \\emph{Aggregator obliviousness} and \\emph{Aggregate

unforgeability} security definitions, augmented with malicious users. Our protocol is provable secure under standard

assumptions in the random oracle model.