EFFICIENT AND PRIVACY-PRESERVING MIN AND K-TH MIN COMPUTATIONS IN MOBILE SENSING SYSTEMS
ABSTRACT
Protecting the privacy of mobile phone user participants is extremely important for mobile phone sensing applications. In this paper, we study how an aggregator can expeditiously compute the minimum value or the k-th minimum value of all users’data without knowing them. We construct two secure protocols using probabilistic coding schemes and a cipher system thatallowshomomorphic bitwise XOR computations for our problems. Following the standard cryptographic security dentition in the semi-honest model, we formally prove our protocols’ security. The protocols proposed by us can support time-series data andneed not to assume the aggregator is trusted. Moreover, different from existing protocols that are based on secure arithmeticsum computations, our protocols are based on secure bitwise XOR computations, thus are more efficient.
EXISTING SYSTEM:
Most previous works on privacy-preserving data aggregationassume a trusted aggregator, which is differentfrom our scenario.In recent years, there are a few works that study privacy-preservingdata aggregation for mobile sensing without assuminga trusted aggregator. However, most of them only consider how to let the aggregatorcompute the sum of users’ data securely. Onlyin [7], [8], [9], after proposing their privacy-preservingprotocols for sum computation, the authors show howto compute the Min based on their sum computationprotocols.In, Shi et al. use a binary search approach inprivacy-preserving data aggregation, for computingthe maximum, minimum, and percentile of data. Asimilar idea of binary search is also used in thispaper, for constructing our protocols for computingthe minimum and k-th minimum valueLi et al. ’s works are very close to ours. Both consider the same problem in a similarscenario as we do in this paper. Based on, Li etal. propose a scheme that utilizes the redundancy insecurity to reduce the communication cost incurredby each user’s joining and/or leaving activities in[9]. The main differences between their works andours is that their protocol traverses the entire dataspace to find the minimum value, and is based onsummation protocols, while our protocols follow theidea of binary search and are based on bitwise XORoperations.
PROPOSED SYETM:
we propose new Min and k-thMin computation protocols for time-series data basedon another technique, XOR-homomorphicencryption.Our protocols can be used by an untrusted aggregatorto securely compute the minimum value or k-thminimumvalues in the aggregation of all users’ privatedata. We rigorously define and prove the securityof our two protocols in a standard cryptographicmodel (please see Section 3 for the definition andSections 4.2 and 5.3 for the proofs). Our protocolssupport time-series data well in the sense that theyonly need to establish the keys for once only. Dueto the fact that we construct our protocols based onsecure bitwise XOR computations, rather than basedon secure arithmetic sum computations, our protocolsare more efficient in general.
CONCLUSION
In this paper, we study how a data aggregator in amobile phone sensing scenario can efficiently computethe minimum value or the k-th minimum value inall mobile phone users’ private data. Using standarddefinitions and paradigms in cryptography, we formallyprove our protocols are secure and thus areable to protect all users’ private data. Compared withexisting protocols that are based on arithmetic sumcomputation, our protocols are based on bitwise XORcomputation and thus are more efficient.
REFERENCES
[1] R. Herring, A. Hofleitner, D. Work, O. Tossavainen, andA.Bayen, Mobile Millennium-Participatory Traffic Estimation UsingMobile Phones, 2009.
[2] A. Thiagarajan, L. Ravindranath, K. LaCurts, S. Madden,H. Balakrishnan, S. Toledo, and J. Eriksson, “Vtrack: accurate,energy-aware road traffic delay estimation using mobilephones,” in SenSys, D. E. Culler, J. Liu, and M. Welsh, Eds.ACM, 2009, pp. 85–98.
[3] T. Das, P. Mohan, V. N. Padmanabhan, R. Ramjee, andA. Sharma, “Prism: platform for remote sensing using smartphones,”inMobiSys, S. Banerjee, S. Keshav, and A. Wolman,Eds. ACM, 2010, pp. 63–76.
[4] R. Rana, C. Chou, S. Kanhere, N. Bulusu, and W. Hu, “Earphone:an end-to-end participatory urban noise mapping system,”inProceedings of the 9th ACM/IEEE International Conferenceon Information Processing in Sensor Networks. ACM, 2010,pp. 105–116.
[5] X. Bao and R. R. Choudhury, “Movi: mobile phone basedvideo highlights via collaborative sensing,” in MobiSys,S. Banerjee, S. Keshav, and A. Wolman, Eds. ACM, 2010,pp. 357–370.
[6] R. Johnson and P. Kuby, Elementary statistics.Cengage Learning,2007.
[7] J. Shi, R. Zhang, Y. Liu, and Y. Zhang, “Prisense: Privacypreservingdata aggregation in people-centric urban sensingsystems,” in INFOCOM. IEEE, 2010, pp. 758–766.
[8] Q. Li and G. Cao, “Efficient and privacy-preserving dataaggregation in mobile sensing,” in ICNP. IEEE, 2012, pp.1–10.
[9] Q. Li, G. Cao, and T. F. L. Porta, “Efficient and privacy-awaredata aggregation in mobile sensing,” IEEE Trans. DependableSec. Comput., vol. 11, no. 2, pp. 115–129, 2014.
[10] C. Castelluccia, A. C.-F. Chan, E. Mykletun, and G. Tsudik,“Efficient and provably secure aggregation of encrypted datain wireless sensor networks,” ACM Trans. Sen. Netw., pp. 1–36,2009.