首页|Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates
Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
NSTL
万方数据
This paper investigates the problem of collecting multidimensional data throughout time(i.e.,longitudinal studies)for the fundamental task of frequency estimation under Local Differential Privacy(LDP)guarantees.Contrary to frequency estimation of a single attribute,the multidimensional aspect demands particular attention to the privacy budget.Besides,when collecting user statistics longitudinally,privacy progressively degrades.Indeed,the"multiple"settings in combination(i.e.,many attributes and several collections throughout time)impose several challenges,for which this paper proposes the first solution for frequency estimates under LDP.To tackle these issues,we extend the analysis of three state-of-the-art LDP protocols(Generalized Randomized Response-GRR,Optimized Unary Encoding-OUE,and Symmetric Unary Encoding-SUE)for both longitudinal and multidimensional data collections.While the known literature uses OUE and SUE for two rounds of saniti-zation(a.k.a.memoization),i.e.,L-OUE and L-SUE,respectively,we analytically and experimentally show that starting with OUE and then with SUE provides higher data utility(i.e.,L-OSUE).Also,for attributes with small domain sizes,we propose Longitudinal GRR(L-GRR),which provides higher utility than the other protocols based on unary encoding.Last,we also propose a new solution named Adaptive LDP for LOngitudinal and Multidi-mensional FREquency Estimates(ALLOMFREE),which randomly samples a single attribute to be sent with the whole privacy budget and adaptively selects the optimal protocol,i.e.,either L-GRR or L-OSUE.As shown in the results,ALLOMFREE consistently and considerably outperforms the state-of-the-art L-SUE and L-OUE protocols in the quality of the frequency estimates.
Local differential privacyDiscrete distribution estimationFrequency estimationMultidimensional dataLongitudinal studies
Héber H.Arcolezi、Jean-Fran?ois Couchot、Bechara Al Bouna、Xiaokui Xiao
展开 >
Inria and École Polytechnique(IPP),Palaiseau,France
TICKET Lab.,Antonine University Hadat-Baabda,Baabda,Lebanon
School of Computing,National University of Singapore Singapore Singapore
展开 >
Agence Nationale de la Recherche(ANR)Region of Bourgogne Franche-Comté CADRAN ProjectH.Arcolezi was partially supported by the European Research Council(ERC)project HYPATIA under the European Union's Horizon 2020
NETL
NSTL
万方数据
