Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Verifiable Order Statistics for Secure Aggregation

Hsu-Chun Hsiao, Chih-Yuan Wang, Joseph M. Hellerstein, Wei-Chung Teng and Chin-Laung Lei

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-48
April 7, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-48.pdf

In-network aggregation can save significant bandwidth in a distributed query system, but is subject to attack by adversaries. Prior work addressed settings where data sources are trusted, but the aggregation infrastructure needs to be secured. We study extensions that also make aggregate queries robust to adversarial data sources, which can inject spurious values into the data stream to be aggregated. Wagner observed that the field of robust statistics can provide tools here, since robust estimators (medians, trimmed means, median absolute deviations, etc.) provide formal guarantees on the degree to which perturbed data can have an effect on aggregate results. This raises the challenge of developing verifiable in-network algorithms for robust estimators. Many of the natural robust estimators are built on order statistics, so we focus here on verifiable techniques for in-network computation of order statistics. To our knowledge, there is no mechanism that guarantees both the efficiency and verifiability of the order statistics computation. In this work, we present the FM3 Proof Sketch aggregation protocol, which efficiently and securely computes various approximate order statistics including medians, median absolute deviations, quantiles, ranks, and frequent items. We derive robustness and approximation guarantees for those queries in adversarial environments, and demonstrate empirically that our scheme is practically useful via experiments on real and synthetic data.


BibTeX citation:

@techreport{Hsiao:EECS-2009-48,
    Author = {Hsiao, Hsu-Chun and Wang,  Chih-Yuan and Hellerstein, Joseph M. and Teng, Wei-Chung and Lei, Chin-Laung},
    Title = {Verifiable Order Statistics for Secure Aggregation},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {Apr},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-48.html},
    Number = {UCB/EECS-2009-48},
    Abstract = {In-network aggregation can save significant bandwidth in a distributed query system, but is subject to attack by adversaries. Prior work addressed settings where data sources are trusted, but the aggregation infrastructure needs to be secured. We study extensions that also make aggregate queries robust to adversarial data sources, which can inject spurious values into the data stream to be aggregated. Wagner observed that the field of robust statistics can provide tools here, since robust estimators (medians, trimmed means, median absolute deviations, etc.) provide formal guarantees on the degree to which perturbed data can have an effect on aggregate results. This raises the challenge of developing verifiable in-network algorithms for robust estimators. Many of the natural robust estimators are built on order statistics, so we focus here on verifiable techniques for in-network computation of order statistics. To our knowledge, there is no mechanism that guarantees both the efficiency and verifiability of the order statistics computation. In this work, we present the FM3 Proof Sketch aggregation protocol, which efficiently and securely computes various approximate order statistics including medians, median absolute deviations, quantiles, ranks, and frequent items. We derive robustness and approximation guarantees for those queries in adversarial environments, and demonstrate empirically that our scheme is practically useful via experiments on real and synthetic data.}
}

EndNote citation:

%0 Report
%A Hsiao, Hsu-Chun
%A Wang,  Chih-Yuan
%A Hellerstein, Joseph M.
%A Teng, Wei-Chung
%A Lei, Chin-Laung
%T Verifiable Order Statistics for Secure Aggregation
%I EECS Department, University of California, Berkeley
%D 2009
%8 April 7
%@ UCB/EECS-2009-48
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-48.html
%F Hsiao:EECS-2009-48