隐私保护近邻检测研究

doi:10.3969/j.issn.1671-1122.2024.06.001

摘要/Abstract

摘要：

随着移动计算和物联网等新兴技术的飞速发展，基于位置的服务（Location Based Service，LBS）在人们日常生活中扮演着愈发重要的角色。许多应用（如移动交友）通过LBS 获取、收集用户的精确位置，并通过执行距离计算来实现近距离用户发现等功能。然而，LBS 在为用户带来便利的同时，也使其面临着泄露隐私位置信息的风险。目前，大多数LBS 应用均以明文形式记录用户精确位置，极易泄露用户的位置和移动模式等信息。此外，现有的能够保护用户隐私位置数据的研究工作存在一些缺陷，如通信开销高、通信时间长或计算安全性不足等。因此，文章提出一种保护用户位置隐私的高效近邻检测方法，该方法基于B/FV（Brakerski/Fan-Vercauteren）同态加密构造优化的圆范围内的隐私保护近邻检测协议。与现有的工作相比，文章方案使用基于格的加密，且具有较优的通信性能。此外，文章实现了基于B/FV 同态加密的方案原型系统，并给出在具有高隐私保护要求和低算术速度限制的场景中的潜在应用，通过对该原型系统的实验结果表明，该方案在实际部署应用中具有广阔的应用前景。

关键词: 基于位置的服务, 隐私保护近邻检测, 同态加密, 基于格的加密

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

中图分类号:

TP309

李增鹏, 王思旸, 王梅. 隐私保护近邻检测研究[J]. 信息网络安全, 2024, 24(6): 817-830.

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

图/表 6

图1

表1

图2

图3

图4

图5

参考文献 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}$	√	√