We consider the problem of publicly verifiable privacy-preserving data aggregation in the presence of a malicious aggregator colluding with malicious users. State-of-the-art solutions either split the aggregator into two parties under the assumption that they do not collude, or require many rounds of interactivity and have non-constant verification time. In this work, we propose mPVAS, the first publicly verifiable privacy-preserving data aggregation protocol that allows arbitrary collusion, without relying on trusted third parties during execution, where verification runs in constant time. We also show three extensions to mPVAS: mPVAS+, for improved communication complexity, mPVAS-IV, for the identification of malicious users, and mPVAS-UD, for graceful handling of reduced user availability without the need to redo the setup. We show that our schemes achieve the desired confidentiality, integrity, and authenticity. Finally, through both theoretical and experimental evaluations, we show that our schemes are feasible for real-world applications.

@en

Large amounts of data are continuously generated by individuals, apps, or dedicated devices. These data can be aggregated to compute useful statistics from multiple sources using data aggregation protocols. However, oftentimes these data contain private information that must be protected from misuse. Privacy-preserving protocols can help to compute the same statistics without revealing the private input data to unauthorized parties. However, most privacy-preserving data aggregation schemes only work in the honest-but-curious model, where participants do not deviate from the protocol. As a result, the computed statistics cannot always be trusted. In particular, the aggregator, which is the party responsible for collecting the data is usually trusted with computing the correct result. However, a compromised aggregator may decide to output any value of its choosing without anyone noticing. Schemes with public verifiability help to counter malicious aggregators who try to falsify the final result by tampering with the inputs of honest users. However, they do not consider cases where both the aggregator and a subset of the users may be malicious, meaning they can deviate from the protocol and collude with each other in order to output results of their choosing. In this work, we develop a privacy-preserving data aggregation protocol to compute the sum of a set of private inputs such that a verifier can efficiently detect tampering even in the face of a malicious aggregator and a subset of malicious users. We also provide two extensions for better performance and for malicious user detection. We show that the scheme achieves the desired properties of confidentiality, integrity, and authenticity. Finally, theoretical and experimental evaluations show that its performance makes it feasible for real-world applications.