一种基于多边形范围的位置接近性检测隐私保护方法

摘要

本发明公开了一种基于多边形范围的位置接近性检测隐私保护方法，包括：步骤1,设置安全参数并计算得到系统参数；步骤2，基于同态加密算法获得接收方的私钥和公钥；步骤3，接收方设置一个包含接收方位置坐标的多边形，基于多边形的顶点集合和接收方的公钥通过同态加密算法计算得到密文集合并发送给发送方；发送方基于自身位置坐标、系统参数和密文集合计算得到接近性检测的密文结果集合并发送给接收方；步骤4，接收方获得接近性检测结果。本发明提出了安全性高的接近性检测隐私保护方法,对原始方向进行正确地随机化处理，在混淆原方向值的同时保留其符号比特(即正负性)，能够在提供隐私保护的同时提供正确的接近性检测结果。

权利要求

1.一种基于多边形范围的位置接近性检测隐私保护方法，其特征在于，包括：步骤1，设置安全参数并计算得到系统参数；所述系统参数包括隐私保护协议的随机数空间长度；

步骤2，根据安全参数，基于同态加密算法获得接收方的私钥和公钥；

步骤3，接收方设置一个包含接收方位置坐标的多边形，获得所述多边形的顶点坐标集合，基于顶点坐标集合和接收方的公钥通过同态加密算法计算得到密文集合并发送给发送方；发送方基于自身位置坐标、系统参数和密文集合计算得到接近性检测的密文结果集合并发送给接收方；

步骤4，接收方根据其私钥对接近性检测的密文结果集合进行解密运算，获得封装在密文结果集合中的接近性检测结果。

2.如权利要求1所述的基于多边形范围的位置接近性检测隐私保护方法，其特征在于，所述同态加密算法为加法同态加密算法或者全同态加密算法。

3.如权利要求2所述的基于多边形范围的位置接近性检测隐私保护方法，其特征在于，所述步骤1中：所述安全参数设置为1μ，表示μ个连续的1，其中，所述μ为正整数；

所述系统参数依据加法同态加密算法设置，加法同态加密算法定义为AHE：(KeyGen，Enc，Dec)，其中，KeyGen表示密钥生成算法，Enc表示加密算法，Dec表示解密算法；加法同态加密算法的明文空间长度设置为其明文空间的比特数，定义为lm；用户位置坐标空间的比特数定义为lc，所述 隐私保护协议的随机数空间长度定义为lr，所述

4.如权利要求3所述的基于多边形范围的位置接近性检测隐私保护方法，其特征在于，所述步骤2包括：输入安全参数1μ，运行(sk，pk)∈R KeyGen(1μ)生成接收方的私钥和公钥；(sk，pk)∈R KeyGen(1μ)为加法同态加密算法的密钥生成算式，表示从输入安全参数1μ后产生的密钥集合KeyGen(1μ)中随机选取sk和pk，sk表示接收方的私钥，pk表示接收方的公钥。

5.如权利要求3所述的基于多边形范围的位置接近性检测隐私保护方法，其特征在于，所述步骤3包括：步骤3-1，接收方设置一个包含接收方位置坐标(xA，yA)的n边多边形，n边多边形的顶点坐标集合为＜(x1，y1)，(x2，y2)，...，(xi，yi)，(xi+1，yi+1)，...，(xn，yn)＞，且顶点集合中每个坐标值的比特数为ec；

步骤3-2，接收方按照i＝1，i＝2，...，i＝n的顺序依次基于接收方的公钥pk计算密文和并将密文集合 发送给发送方B；

其中，所述i＇：＝(i+1)modn，即将i+1对n取模运算的结果赋值给i＇；1≤i≤n；

表示依据加法同态加密算法的加密算法函数将输入接收方的公钥pk和xi后得到的输出值赋值给xi的密文 表示依据加法同态加密算法的加密算法函数将输入接收方的公钥pk和yi后得到的输出值赋值给yi的密文表示依据加法同态加密算法的加密算法函数将输入接收方的公钥pk和xi·yi后得到的输出值赋值给xi·yi的密文 表示依据加法同态加密算法的加密算法函数将输入接收方的公钥pk和-yi·xi′后得到的输出值赋值给-yi·xi′的密文 所述[n]＝{1，...，n}，表示1到n的所有正整数集合；

步骤3-3，发送方选择随机数集合{ri}i∈[n]，其中， 发送方按照i＝1，i＝2，...，i＝n的顺序依次计算密文结果并将计算的接近性检测的密文结果集合 发送给接收方；发送方的位置坐标为(xB，yB)，且每个坐标值的比特数为lc。

6.如权利要求3所述的基于多边形范围的位置接近性检测隐私保护方法，其特征在于，所述步骤4包括：步骤4-1，接收方根据其私钥sk对接近性检测的密文结果集合 中的密文结果进行解密运算获得方向值 得到随机化后的方向集合

步骤4-2，接收方检测如果方向集合 中所有方向值都大于等于0，则接收方在其设置的多边形范围内。

7.如权利要求5所述的基于多边形范围的位置接近性检测隐私保护方法，其特征在于，所述n边多边形为接收方根据其实际需要个性化定制的地理检测范围。

说明书

一种基于多边形范围的位置接近性检测隐私保护方法

技术领域

[0001] 本发明涉及一种隐私保护方法，特别是涉及一种基于多边形范围的位置接近性检测隐私保护方法。

背景技术

[0002] 如今，许多移动设备(例如，智能手机或平板电脑)可实时测量并报告精确位置，很大程度上促进了移动网络上的基于移动位置服务(LBS，Location Based Service)的发展。一个最基础的LBS是位置接近性检测，其功能为使一个用户能够测试另一个用户是否就在其附近，位置接近性检测可以帮助用户找到他们附近的朋友、优步汽车、或紧急情况下的医务人员，推动了大量社交应用程序的发展。虽然有些用户不反对将其位置共享给第三方进行位置接近性检测，但是位置信息的泄露可能造成严重的隐私威胁，如恶意跟踪、骚扰、甚至绑架等。潜在的攻击者可能来自从好奇的社交媒体联系人、家庭成员、甚至是职业罪犯(例如，窃贼检查受害者是否在家)。因此，用户往往期望基于位置的移动应用在提供保留的位置接近检测服务的同时，保护用户隐私的确切位置。

[0003] 以往的接近性检测的隐私保护协议通常是基于圆形范围，即以一方位置坐标为圆心和一定半径确定一个接近性范围来判断另一方的位置是否在该圆内。圆形范围的接近性检测不能使用户进行特定的定制，例如排除一些不想要的区域或范围。在文献[Hui Zhu,Fengwei Wang,Rongxing Lu,Fen Liu,Gang Fu,and Hui Li.Efficient and privacy-preserving proximity detection schemes for social applications.IEEE IoT 
Journal,2017]中作者基于文献[F.Feito,J.C.Torres,and A.Urena,Orientation,
simplicity,and inclusion test for planar polygons,Computers&Graphics,vol.19,
no.4,pp.595–600,1995]提出的范围检测方法提出了一个基于多边形范围的接近性检测的隐私保护协议，即用户可以定制一个任意多边形来作为接近性检测范围，从而使得检测结果更加精确更贴近用户的需要。但是，发明人在最新的研究成果中[Kimmo Jarvinen,_
Agnes Kiss,Thomas Schneider,Oleksandr Tkachenko,and Zheng Yang.Faster 
privacy-preserving location proximity schemes.In CANS 2018]发现Hui Zhu等人提
出的上述这个基于多边形范围的接近性检测的隐私保护协议存在不安全性，并不能有效保护用户的位置信息。

发明内容

[0004] 本发明旨在至少解决现有技术中存在的技术问题，特别创新地提出了一种新型的安全的基于多边形范围的位置接近性检测隐私保护方法。

[0005] 为了实现本发明的上述目的，本发明提供了一种基于多边形范围的位置接近性检测隐私保护方法，包括：

[0006] 步骤1,设置安全参数并计算得到系统参数；所述系统参数包括隐私保护协议的随机数空间长度；

[0007] 步骤2，根据安全参数，基于同态加密算法获得接收方的私钥和公钥；

[0008] 步骤3，接收方设置一个包含接收方位置坐标的多边形，获得所述多边形的顶点坐标集合，基于顶点坐标集合和接收方的公钥通过同态加密算法计算得到密文集合并发送给发送方；发送方基于自身位置坐标、系统参数和密文集合计算得到接近性检测的密文结果集合并发送给接收方；

[0009] 步骤4，接收方根据其私钥对接近性检测的密文结果集合进行解密运算，获得封装在密文结果集合中的接近性检测结果。

[0010] 在本发明的一种优选实施方式中，所述同态加密算法为加法同态加密算法或者全同态加密算法。

[0011] 在本发明的一种优选实施方式中，所述步骤1中：

[0012] 所述安全参数设置为1μ，表示μ个连续的1，其中，所述μ为正整数；

[0013] 所述系统参数依据加法同态加密算法设置，加法同态加密算法定义为AHE：(KeyGen，Enc，Dec)，其中，KeyGen表示密钥生成算法，Enc表示加密算法，Dec表示解密算法；
加法同态加密算法的明文空间长度设置为其明文空间的比特数，定义为lm；用户位置坐标空间的比特数定义为lc，所述 隐私保护协议的随机数空间长度定义为lr，所述

[0014] 在本发明的一种优选实施方式中，所述步骤2包括：

[0015] 输入安全参数1μ，运行(sk，pk)∈R KeyGen(1μ)生成接收方的私钥和公钥；(sk，pk)∈RKeyGen(1μ)为加法同态加密算法的密钥生成算式，表示从输入安全参数1μ后产生的密钥集合KeyGen(1μ)中随机选取sk和pk，sk表示接收方的私钥，pk表示接收方的公钥。

[0016] 在本发明的一种优选实施方式中，所述步骤3包括：

[0017] 步骤3-1，接收方设置一个包含接收方位置坐标(xA，yA)的n边多边形，n边多边形的顶点坐标集合为＜(x1，y1)，(x2，y2)，...，(xi，yi)，(xi+1，yi+1)，...，(xn，yn)＞，且顶点集合中每个坐标值的比特数为lc；

[0018] 步骤3-2，接收方按照i＝1，i＝2，…，i＝n的顺序依次基于接收方的公钥pk计算密文 和并将密文集合 发送给发送方B；

[0019] 其中，所述i':＝(i+1)modn，即将i+1对n取模运算的结果赋值给i'；1≤i≤n；表示依据加法同态加密算法的加密算法函数将输入接收方的公钥pk和
xi后得到的输出值赋值给xi的密文 表示依据加法同态加密算法的
加密算法函数将输入接收方的公钥pk和yi后得到的输出值赋值给yi的密文
表示依据加法同态加密算法的加密算法函数将输入接收
方的公钥pk和xi·yi后得到的输出值赋值给xi·yi的密文
表示依据加法同态加密算法的加密算法函数将输入接收方的公钥pk和-yi·xi'后得到的输出值赋值给-yi·xi'的密文 所述[n]＝{1，...，n}，表示1到n的所有正整数集合；

[0020] 步骤3-3，发送方选择随机数集合{ri}i∈[n]，其中 1≤i≤n，发送方按照i＝1，i＝2，…，i＝n的顺序依次计算密文结果
并将计算的接近性检测的密文结果集合 发送给接收方；发送方的位置坐标为(xB，
yB)，且每个坐标值的比特数为lc。

[0021] 在本发明的一种优选实施方式中，所述步骤4包括：

[0022] 步骤4-1，接收方根据其私钥sk对接近性检测的密文结果集合 中的密文结果进行解密运算获得方向值 得到随机化后的方向集合

[0023] 步骤4-2，接收方检测如果方向集合 中所有方向值都大于等于0，则接收方在其设置的多边形范围内。

[0024] 在本发明的一种优选实施方式中，所述n边多边形为接收方根据其实际需要个性化定制的地理检测范围。

[0025] 综上所述，由于采用了上述技术方案，本发明的有益效果是：

[0026] 本发明首个提出了安全性高的基于同态加密算法和多边形范围的接近性检测隐私保护方法，同时在方向值 计算执行过程中进行了定制和优化，运行效率高。由于选择的随机数集合以及随机数空间长度lr能够对原始方向进行正确地随机化处理，在混淆原方向值的同时保留其符号比特(即正负性)，因此能够在提供隐私保护的同时提供正确的接近性检测结果。

[0027] 本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

[0028] 图1是本发明基于多边形范围的位置接近性检测隐私保护方法的流程图。

具体实施方式

[0029] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。

[0030] 在本发明的描述中，需要理解的是，术语“纵向”、“横向”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。

[0031] 在本发明的描述中，除非另有规定和限定，需要说明的是，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是机械连接或电连接，也可以是两个元件内部的连通，可以是直接相连，也可以通过中间媒介间接相连，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。

[0032] 本发明公开了一种基于多边形范围的位置接近性检测隐私保护方法，其流程如图1所示，包括：

[0033] S1,设置安全参数并计算得到系统参数；系统参数包括隐私保护协议的随机数空间长度；

[0034] S2，根据安全参数，基于同态加密算法获得接收方的私钥和公钥；

[0035] S3，接收方设置一个包含接收方位置坐标的多边形，获得所述多边形的顶点坐标集合，基于顶点坐标集合和接收方的公钥通过同态加密算法计算得到密文集合并发送给发送方；发送方基于自身位置坐标、系统参数和密文集合计算得到接近性检测的密文结果集合并发送给接收方；

[0036] S4，接收方根据其私钥对接近性检测的密文结果集合进行解密运算，获得封装在密文结果集合中的接近性检测结果。

[0037] 在本发明的一种优选实施方式中，同态加密算法为加法同态加密算法或者全同态加密算法。

[0038] 在本发明的一种优选实施方式中，在S1中：

[0039] 安全参数设置为1μ，表示μ个连续的1，其中，μ为正整数；

[0040] 系统参数依据加法同态加密算法设置，加法同态加密算法定义为AHE：(KeyGen，Enc，Dec)，其中，KeyGen表示密钥生成算法，Enc表示加密算法，Dec表示解密算法；加法同态加密算法的明文空间长度设置为其明文空间的比特数，定义为lm，例如lm＝256；用户位置坐标空间的比特数定义为lc，所述 隐私保护协议的随机数空间长度定义为lr，所述

[0041] 在本实施方式中，假设S为一个集合，那么我们用公式a∈R S来表示从集合S中随机的选取一个元素a。AHE为additively homomophic encryption的缩写，为加法同态加密算法的英文缩写。加法同态加密算法有多种，优选但不限于为Paillier算法。加法同态加密算法的表达式AHE：(KeyGen，Enc，Dec)的具体定义如下：

[0042] 1)(sk，pk)∈R KeyGen(1μ)：密钥生成算法函数，输入一个安全参数1μ，从密钥生成算法函数生成的密钥集合中随机选取出私钥sk和对应公钥pk。

[0043] 2)C∈R Enc(pk，m)：加密算法函数，输入公钥pk和消息m，从加密算法函数生成的密文集合中随机选择一个作为消息m加密后的密文C。

[0044] 3)m←Dec(sk，C)：解密算法函数，输入私钥sk和密文C，输出密文C解密后对应的消息m。

[0045] 若给定消息m1和m2，对应的两个密文C1＝Enc(pk，m1)和C2＝(pk，m2)，AHE的加法同态性表现为：

[0046] 1)Dec(sk，C1·C2)＝m1+m2和

[0047] 2)Dec(sk，(C1)t)＝t·m1。

[0048] 在本发明的一种优选实施方式中，S2包括：

[0049] 输入安全参数1μ，运行(sk，pk)∈R KeyGen(1μ)生成接收方的私钥和公钥；(sk，pk)∈R KeyGen(1μ)为加法同态加密算法的密钥生成算式，表示从输入安全参数1μ后产生的密钥集合KeyGen(1μ)中随机选取sk和pk，sk表示接收方的私钥，pk表示接收方的公钥。

[0050] 在本发明的一种优选实施方式中，S3包括：

[0051] 步骤3-1，接收方设置一个包含接收方位置坐标(xA，yA)的n边多边形，n边多边形的n个顶点坐标集合为<(x1，y1)，(x2，y2)，...，(xi，yi)，(xi+1，yi+1)，...，(xn，yn)>，且顶点集合中每个坐标值的比特数为lc，即所有顶点在x轴或y轴坐标值的比特数均为lc；

[0052] 步骤3-2，接收方按照i＝1，i＝2，…，i＝n的顺序依次基于接收方的公钥pk计算密文 和并将密文集合 发送给发送方B；

[0053] 其中，所述i':＝(i+1)modn，即将i+1对n取模运算的结果赋值给i'；1≤i≤n；表示依据加法同态加密算法的加密算法函数将输入接收方的公钥pk和
xi后得到的输出值赋值给xi的密文 表示依据加法同态加密算法的
加密算法函数将输入接收方的公钥pk和yi后得到的输出值赋值给yi的密文
表示依据加法同态加密算法的加密算法函数将输入接收
方的公钥pk和xi·yi后得到的输出值赋值给xi·yi的密文
表示依据加法同态加密算法的加密算法函数将输入接收方的公钥pk和-yi·xi'后得到的输出值赋值给-yi·xi'的密文 所述[n]＝{1，...，n}，表示1到n的所有正整数集合；步骤
3-3，发送方选择随机数集合{ri}i∈[n]，其中 1≤i≤n，发送方按照i＝1，i＝
2，…，i＝n的顺序依次计算密文结果 并将计
算的接近性检测的密文结果集合 发送给接收方；发送方的位置坐标为(xB，yB)，其
中每个坐标值的比特数为lc，即发送方在x轴或y轴坐标值的比特数均为lc。
表示将等号右边的算式的值赋值给第i个密文结
果

[0054] 在本发明的一种优选实施方式中，所述步骤4包括：

[0055] 步骤4-1，接收方根据其私钥sk对接近性检测的密文结果集合 中的密文结果进行解密运算获得方向值 得到随机化后的方向集合
表示依据加法同态加密算法的解密算法函数将输入接收方
的私钥sk和 后得到的输出值赋值给方向值

[0056] 步骤4-2，接收方检测如果方向集合 中所有方向值都大于等于0，则接收方在其设置的多边形范围内。

[0057] 在本发明的一种优选实施方式中，n边多边形为接收方根据其实际需要个性化定制的地理检测范围。

[0058] 在本发明的一个应用场景中，设计了一个基于加法同态加密算法AHE：(KeyGen，Enc，Dec)和多边形范围的位置接近性检测隐私保护协议。该隐私保护协议包括2个部分:第一个部分为密钥和参数生成部分，第二个部分为在线接近性检测。每个部分的具体执行过程被定义如下：

[0059] 1、密钥和参数生成：输入安全参数1μ，接收方A首先调用密钥生成算法函数(sk，pk)∈R KeyGen(1μ)生成A的私钥和公钥。公钥pk被发送到发送方B。设lm是加法同态加密的消息空间的比特数长，用户位置坐标空间的比特数，定义为lc，所述 lr是隐私保护随机空间的比特数， 且满足lr＞μ。

[0060] 2、在线位置接近性检测阶段：

[0061] 1)用户A和B获得坐标为(xA，yA)和(xB，yB)的实时位置。然后A生成一个带n边的多边形P，P包含(xA，yA)。我们假设多边形P的顶点坐标集合为：

[0062] <(x1，y1)，(x2，y2)，...，(xi，yi)，(xi+1，yi+1)，...，(xn，yn)>，且顶点集合中每个坐标值的比特数为lc。

[0063] 2)对于i∈[n]和i′＝i+1 mod n，接收方A逐个计算密文和 然后A
将密文集合 发送给用户B。

[0064] 3)收到 后，发送方B选择随机数集合{ri}i∈[n]，其中循环从i＝1到i＝n，B计算密文结果为
然后B将计算密文结果集合 发送给接收方A。

[0065] 4)接收方A收到 后，根据其私钥通过解密算式 进行解密运算获得随机化后的方向集合 接收方检测如果方向集合中 所有的
方向值都大于等于0，则B在A指定的多边形范围内。

[0066] 通过以上协议，两个用户在不知道相互位置坐标的情况下使得接收方知道发送方是否在其附近，从而达到接近性检测的同时实现隐私保护目的。同时，本发明可以进一步和其它基于位置的服务进行结合，例如附近朋友发现和停车位查找等服务，实现具体隐私保护应用。此外，同态加密的安全性结合本协议随机数的参数选择和接近性结果模糊化处理过程，保证了本发明的安全性。

[0067] 本发明的性能分析：

[0068] 在下表中，总结了本发明的性能，包括通信量和计算量，其具体性能与AHE算法、多边形的边数n相关；我们假设C表示通用的密文，En表示加法运算,Ex表示指数运算，D表示解密运算；

[0069]

[0070] 本发明的性能与多边形的边数量n线性相关，而与用户A和B之间的距离是没有关系的，因此性能好。

[0071] 本发明的特点和优势：

[0072] 本发明提出首个安全的基于多边形范围和同态加密算法的位置接近性隐私保护协议。接收方可以根据其实际需要个性化定制的需要检测的地理范围，从而更加精确的获得接近性检测结果；同时，本发明可以适用于两用户任意距离的接近性检测，不受范围的约束。本发明的性能好，在多边形边数一定的情况下，本发明可在同样的计算量的情况下用于任意大小范围内的位置接近性检测，因此性能较高应用范围更广。

[0073] 在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

[0074] 尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。