**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 thatallows homomorphic 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 efﬁcient.

**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 ﬁnd 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-homomorphic encryption.Our protocols can be used by an untrusted aggregatorto securely compute the minimum value or k-th minimumvalues in the aggregation of all users’ privatedata. We rigorously deﬁne and prove the securityof our two protocols in a standard cryptographicmodel (please see Section 3 for the deﬁnition 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 efﬁcient in general.

**CONCLUSION**

** **

In this paper, we study how a data aggregator in amobile phone sensing scenario can efﬁciently computethe minimum value or the k-th minimum value inall mobile phone users’ private data. Using standarddeﬁnitions 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 efﬁcient.

**REFERENCES**

** **

[1] R. Herring, A. Hoﬂeitner, D. Work, O. Tossavainen, andA. Bayen, *Mobile Millennium-Participatory Trafﬁc 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 trafﬁc 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,”in *MobiSys*, 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,”in *Proceedings 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, “Efﬁcient and privacy-preserving dataaggregation in mobile sensing,” in *ICNP*. IEEE, 2012, pp.1–10.

[9] Q. Li, G. Cao, and T. F. L. Porta, “Efﬁcient 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,“Efﬁcient and provably secure aggregation of encrypted datain wireless sensor networks,” *ACM Trans. Sen. Netw.*, pp. 1–36,2009.