Research of Privacy-Preserving Proximity Test

doi:10.3969/j.issn.1671-1122.2024.06.001

Abstract

Abstract:

With the rapid development of emerging technologies such as mobile computing and the Internet of Things, location-based services (LBS) are playing an increasingly important role in people's daily lives. Many applications (e.g., mobile dating) use LBS to capture and collect the user's precise location, and perform proximity user discovery by performing distance calculations. However, while LBS brings convenience to users, it also exposes it to the risk of leaking private location information. At present, most LBS applications record the user's precise location in plaintext, which is easy to leak information such as the user's location and mobility patterns. In addition, most existing research efforts that can protect the user's private location data have some shortcomings, such as high communication overhead, long communication time, or a lack of computational security. Therefore, this paper proposed an efficient privacy-preserving proximity test solution to protect user's location privacy, and constructd a optimized privacy-preserving proximity test protocol for circles based on Brakerski/Fan-Vercauteren (B/FV) homomorphic encryption. Compared with the existing work, the proposed scheme used lattice-based encryption and had better communication performance. In addition, this paper implementd a prototype system based on B/FV homomorphic encryption, and gove the potential application in scenarios with high privacy protection requirements and low arithmetic speed limitations. The experimental results of the prototype system show that the proposed scheme has a broad practical application prospect in practical deployment applications.

Key words: location-based service, privacy-preserving proximity test, homomorphic encryption, lattice-based encryption

CLC Number:

TP309

LI Zengpeng, WANG Siyang, WANG Mei. Research of Privacy-Preserving Proximity Test[J]. Netinfo Security, 2024, 24(6): 817-830.

Figures/Tables 6

References 23

[1]	WHITTAKER Z. A Leaky Database Spilled 2FA Codes for the World’s Tech Giants \| TechCrunch[EB/OL]. (2024-02-29)[2024-04-15]. https://techcrunch.com/2024/02/29/leaky-database-two-factor-codes/.
[2]	CHENG R, ZHANG Yu, BERTINO E, et al. Preserving User Location Privacy in Mobile Data Management Infrastructures[C]// Springer. International Workshop on Privacy Enhancing Technologies. Heidelberg: Springer, 2006: 393-412.
[3]	SIKSNYS L, THOMSEN J R, SALTENIS S, et al. A Location Privacy Aware Friend Locator[C]// Springer. International Symposium on Advances in Spatial & Temporal Databases. Heidelberg: Springer, 2009: 405-410.
[4]	ZHENG Yao, LI Ming, LOU Wenjing, et al. Location Based Handshake and Private Proximity Test with Location Tags[J]. IEEE Transactions on Dependable & Secure Computing, 2017, 14(4): 406-419.
[5]	PAILLIER P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[J]. Advances in Cryptology Leurocrypt, 1999, 1592: 223-238.
[6]	DAMGAARD I, GEISLER M, KROIGAARD M. A Correction to 'Efficient and Secure Comparison for on-Line Auctions'[J]. International Journal of Applied Cryptography, 2009, 1(4): 323-324.
[7]	ELGAMAL T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[J]. lEEE Transactions on Information Theory, 1985, 31(4): 469-472.
[8]	NARAYANAN A, THIAGARAJAN N, LAKHANI M, et al. Location Privacy via Private Proximity Testing[C]// The Internet Society. Network and Distributed System Security Symposium. San Diego: The Internet Society, 2011: 381-386.
[9]	ZHONG Ge, GOLDBERG I, HENGARTNER U. Louis, Lester and Pierre: Three Protocols for Location Privacy[C]// Springer. International Conference on Privacy Enhancing Technologies. Heidelberg: Springer, 2007: 62-76.
[10]	SEDENKA J, GASTI P. Privacy-Preserving Distance Computation and Proximity Testingon Earth, Done Right[C]// ACM. ACM Asia Conference on Computer and Communications Security. New York: ACM, 2014: 99-110.
[11]	ERKIN Z, FRANZ M, GUAJARDO J, et al. Privacy-Preserving Face Recognition[C]// Springer. Privacy Enhancing Technologies. Heidelberg: Springer, 2009: 235-253.
[12]	KOLESNIKOV V, SADEGHI A, SCHNEIDER T. Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima[C]// Springer. International Conference on Cryptology and Network Security. Heidelberg: Springer, 2009: 1-20.
[13]	HALLGREN P, OCHOA M, SABELFELD A. A Parallelizable Decentralized Privacy-Preserving Location Proximity Protocol[C]// IEEE. Privacy, Security & Trust. New York: IEEE, 2015: 1-6.
[14]	ZHU Hui, WANG Fengwei, LU Rongxing, et al. Efficient and Privacy-Preserving Proximity Detection Schemes for Social Applications[J]. IEEE Internet of Things Journal, 2018, 5(4): 2947-2957.
[15]	JARVINEN K, KISS A, SCHNEIDER T, et al. Faster Privacy-Preserving Location Proximity Schemes[C]// Springer. Cryptology and Network Security. Heidelberg: Springer, 2018: 3-22.
[16]	DEMMLER D, SCHNEIDER T, ZOHNER M. ABY-A Framework for Efficient Mixed-Protocol Secure Two-Party Computation[EB/OL]. (2015-02-01)[2024-04-15]. https://api.semanticscholar.org/CorpusID:14639818.
[17]	JARVINEN K, KISS A, SCHNEIDER T, et al. Faster Privacy-Preserving Location Proximity Schemes for Circles and Polygons[J]. IET Information Security, 2020, 14(3): 254-265.
[18]	ALOUFI A, HU Peizhao, LIU Hang, et al. Universal Location Referencing and Homomorphic Evaluation of Geospatial Query[EB/OL]. (2021-03-01)[2024-04-15]. https://doi.org/10.1016/j.cose.2020.102137.
[19]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. (Leveled) Fully Homomorphic Encryption without Bootstrapping[J]. ACM Transactions on Computation Theory, 2014, 6(3): 1-36.
[20]	MASCETTI S, FRENI D, BETTINI C, et al. Privacy in Geo-Social Networks: Proximity Notification with Untrusted Service Providers and Curious Buddies[J]. VLDB Journal, 2011, 20(4): 541-566.
[21]	FAN Junfeng, VERCAUTEREN F. Somewhat Practical Fully Homomorphic Encryption[EB/OL]. (2012-03-22)[2024-04-15]. https://eprint.iacr.org/2012/144.
[22]	BLOOM B H. Space/Time Trade-Offs in Hash Coding with Allowable Errors[J]. Communications of ACM, 1970, 13(7): 422-426.
[23]	PAGH A, PAGH R, RAO S S. An Optimal Bloom Filter Replacement[C]// SIAM. Proceedings of the Sixteenth Annual ACM SIAM Symposium on Discrete Algorithms. Vancouver: SIAM, 2005: 823-829.

方案	TTP	通信	计算	1-RTT	基于格的加密
文献[3]方案	有	—	—	×	×
文献[20]方案	有	—	—	×	×
文献[8]方案	有	$O(12\log n+4\iota )$	$\begin{align} & 4E+4S+2A+ \\ & 2M \\ \end{align}$	√	×
文献[10]方案	无	$O(7\log n)$	$\begin{align} & 19E+52S+8M+ \\ & 6C+4I+T \\ \end{align}$	×	×
文献[9]方案（Louis）	有	$O(22\log n+\log \tau )$	$\begin{align} & 21E+9S+4A+ \\ & 15M+3h \\ \end{align}$	×	×
文献[9]方案（Lester）	无	$\begin{align} & O(\log p+\log t+ \\ & \log \tau ) \\ \end{align}$	$\begin{align} & 10E+8S+9A+ \\ & 8M \\ \end{align}$	√	×
文献[9]方案（Pierre）	无	$O(12\log p+\log \tau )$	$\begin{align} & 13E+9S+12A+ \\ & 13M \\ \end{align}$	√	×
文献[13]方案	无	$O(6\log n+\log \tau )$	$\begin{align} & 6E+(14+2\tau )S+ \\ & (8+\tau )A+6M \\ \end{align}$	√	×
文献[15]方案	无	$\begin{align} & O(5\log n+1.44\varepsilon \tau + \\ & \log u) \\ \end{align}$	$\begin{align} & 14E+(\tau +15)S+ \\ & (\tau +2)A+(\tau +3)M \\ \end{align}$	√	×
本文方案	无	$\begin{align} & O((9n+1)\log q+ \\ & 1.44\varepsilon \tau ) \\ \end{align}$	$\begin{align} & (17+\tau )S+(9+ \\ & \tau )A+5M+(\tau +1)h \\ \end{align}$	√	√