一种移动互联网中隐私保护的定位签到系统及方法

摘要

本发明公开了一种移动互联网中隐私保护的定位签到系统及方法，假设签到系统中有1个签到发起者，n个签到参与者；系统为分布式结构，包括签到发起端、签到客户端两个部分；签到发起端由部署在签到发起者的服务器上的程序实现，用于产生签到任务，其中包括签到指定区域的坐标信息、指定签到任务的参与者；签到客户端由签到参与者的手机应用程序实现，通过LBS定位服务或卫星定位得到当前坐标，将坐标点作为输入利用安全多方几何计算协议与签到发起端进行双向通信，从而实现隐私保护的签到。本发明在确保签到者和签到发起者的坐标点隐私的前提下，实现了判定签到者的坐标是否属于签到发起者所指定区域的功能，提升了效率。

说明书

技术领域

本发明属于基于位置的服务(LBS)技术和安全两方几何计算技术领域，涉及一种移动互联网中隐私保护的定位签到系统及方法，特别涉及针对复杂凹多边形区域的特点、用户坐标点位置信息的隐私保护的需要、以及签到区域隐私保护的需求，通过结合同态加密算法、点与多边形位置射线判定法的一种移动互联网中隐私保护的定位签到系统及方法。

背景技术

随着科技的发展，手机作为人类生活必不可少的工具，已经渗透到人们生产生活的方方面面。它将互联网与人们的生活紧密连接。移动性的引入使得互联网增加了地理位置这一维度的信息。因此与地理位置的结合是移动互联网最为重要的特性之一。基于位置的服务(LBS：Location-Based Service)成为了移动互联网中最为关键的服务模式之一。这种基于位置的服务模式在发展的过程也受到隐私泄露问题的制约。位置隐私的泄漏使得恶意的服务参与者能够确定目标的位置和生活规律，这对使用者的安全产生了巨大威胁。

其中手机定位是手机上的一个核心基础功能。举一个常见的例子，在某些签到打卡的应用中，签到的发起者需要获知签到人是否到达指定的区域范围内，但又不希望将自己的指定区域泄露给签到人，同时签到人出于对个人隐私的保护，不希望将自己的位置信息暴露给签到发起者。

对于这种需要保护双方隐私的应用场景，目前已存在一些解决方法，例如基于同态加密算法和安全多方几何计算的签到系统；简单来说，签到系统的作用就是判定一个参与者是否到达签到发起者指定的区域内。同态加密算法具有这样的特性：对加密后得到的密文实施某种操作的结果就是对被加密的明文实施另一种操作的结果的密文。安全多方几何计算保证了多个参与者在不泄露自己位置信息的前提下协同计算出签到结果。

然而，已有的基于同态加密算法和安全多方几何计算的签到系统的问题转化方式只能针对简单的凸多边形区域适用，对于凹多边形以及更复杂的多边形区域则无法判定签到者是否位于指定区域中。还有些方案在设计的过程中使用计算复杂度较高的密码学原语，导致了整个系统的效率低，不适用于实际场景。

发明内容

为了解决上述的技术问题，本发明提供了一种移动互联网中隐私保护的定位签到系统及方法。

本发明的系统所采用的技术方案是：一种移动互联网中隐私保护的定位签到系统，假设签到系统中有1个签到发起者，n个签到参与者；其特征在于：所述系统为分布式结构，包括签到发起端、签到客户端两个部分；签到发起端由部署在签到发起者的服务器上的程序实现，用于产生签到任务，其中包括签到指定区域的坐标信息、指定签到任务的参与者；签到客户端由签到参与者的手机应用程序实现，通过LBS定位服务或卫星定位得到当前坐标，将坐标点作为输入利用安全多方几何计算协议与签到发起端进行双向通信，从而实现隐私保护的签到。

本发明的方法所采用的技术方案是：一种移动互联网中隐私保护的定位签到方法，其特征在于，包括以下步骤：

步骤1：系统初始化；

步骤2：签到发起阶段；

步骤3：签到执行阶段；

步骤4：公布结果。

本发明方法与现有的技术相比有如下的优点和有益效果：

(1)本发明在确保签到者和签到发起者的坐标点隐私的前提下，实现了判定签到者的坐标是否属于签到发起者所指定区域的功能；

(2)提出了一种更适用于复杂多边形的坐标点与指定区域关系判断的方法，相比较已有的方案，由于设计的算法思路不同，提升了方案的效率。

附图说明

图1：本发明实施例的系统模型图；

图2：本发明实施例的方法流程图。

具体实施方式

为了便于本领域普通技术人员理解和实施本发明，下面结合附图及实施例对本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明和解释本发明，并不用于限定本发明。

请见图1，本发明提供的一种移动互联网中隐私保护的定位签到系统，假设签到系统中有1个签到发起者，n个签到参与者；系统为分布式结构，包括签到发起端、签到客户端两个部分；签到发起端由部署在签到发起者的服务器上的程序实现，用于产生签到任务，其中包括签到指定区域的坐标信息、指定签到任务的参与者；签到客户端由签到参与者的手机应用程序实现，通过LBS定位服务或卫星定位得到当前坐标，将坐标点作为输入利用安全多方几何计算协议与签到发起端进行双向通信，从而实现隐私保护的签到。

本实施例的系统包括签到发起端(签到发起人)、签到客户端(签到者)、LBS服务提供商，三者之间通过互联网进行双向的通信。本实施例的签到发起人与签到者向LBS服务提供商发送服务请求，LBS服务提供商响应请求。签到发起人与签到者之间建立长联接的会话进行通信。

请见图2，本发明提供的一种移动互联网中隐私保护的定位签到方法，包括以下步骤：

步骤1：系统初始化；

步骤1.1：签到发起者根据运行初始化算法G(τ)得到元组(q₁,q₂,G,G₁,e)，G,G₁是阶为n＝q₁q₂的群，e：G×G→G₁是双线性映射，随机选择两个生成元并令那么h就是群G的q₁阶子群的随机生成元。公开系统公钥PK₁＝(n,G,G₁,e,h,k)，保留私钥SK₁＝q₁。

步骤1.2：签到者根据安全参数运行算法G(τ)得到元组(q₁,q₂,G,G₁,e)，G,G₁是阶为n＝q₁q₂的群，e：G×G→G₁是双线性映射，随机选择两个生成元并令那么h就是群G的q₁阶子群的随机生成元。公开系统公钥PK₂＝(n,G,G₁,e,h,k)，保留私钥SK₂＝q₁。

步骤2：签到发起阶段：

步骤2.1：签到发起者根据LBS服务商提供的定位功能找出指定签到区域多边形的顶点坐标P_i(x_i,y_i)。

步骤2.2：签到发起者随机选择将坐标点P_i作为明文消息，并利用自己的公钥PK₁计算密文将发送给签到者。

步骤3：签到执行阶段；

步骤3.1：签到者利用LBS服务获取当前坐标点a(x_a,y_a)，随机选取一个坐标点b(x_b,y_b)，选取随机数r，并使用公钥PK₁做加密操作：

W＝E(x_ay_b-x_by_a+r)

将计算结果M和W发送给签到发起者。

步骤3.2：签到发起者使用私钥SK₁解密,计算如下：

从而得到直线L_ab与多边形顶点的叉积S，利用sgn(S)得出直线L_ab与多边形顶点P_i的相对位置。

如果sgn(S)＝1，那么多边形顶点P_i在直线L_ab的顺时针方向；如果sgn(S)＝-1，那么多边形顶点P_i在直线L_ab逆时针方向；如果sgn(S)＝0，那么多边形顶点P_i与直线L_ab共线。

得到的结果记作序列T∈{-1,0,1}ⁿ。找出T中的跳变的下标i记作集合L，跳变的情况有：(-1,1)、(1,-1)、(0,1)、(0,-1)、(-1,0)、(1,0)。若T中无跳变情况，则签到者在指定区域外，签到发起者通知签到者重新签到。

步骤3.3：签到者使用自己的公钥PK₂加密当前坐标点a(x_a,y_a)，计算密文：

将发送给签到发起者。

步骤3.4：签到发起者选取随机数r，计算集合l中的线段与坐标点a的叉积：

W′＝E(x_iy_i+1-x_i+1y_i+r)

将计算得到的密文发送给签到者。

步骤3.5：签到者使用私钥SK₂解密,计算如下：

从而得到集合L中的线段与坐标点a的叉积S_l，利用sgn(S_l)得出集合L中的线段与坐标点a的相对位置。

如果sgn(S_l)＝1,则坐标点a在线段顺时针方向，如果sgn(S_l)＝-1,则坐标点a在线段逆时针方向，如果sgn(S_l)＝0,则坐标点a在线段上。

集合L中的线段与坐标点a的相对位置记作序列T′∈{-1,0,1}ⁿ，如果序列中存在0，则坐标点a在指定签到区域内；如果-1或1的个数为奇数个，则坐标点a在指定签到区域内，否则坐标点a在指定签到区域外。

步骤4：公布结果；

坐标点a在指定签到区域外，则签到失败；否则，签到成功。得到签到结果的一方将结果发送给另一方。

本发明利用安全多方几何计算协议，使得签到发起者和签到者的坐标隐私不泄露的情况下，完成了基于位置的签到判定功能。同时该方法更适用于复杂多边形的指定区域的场景，相比较已有的方案，由于设计的算法思路不同，提高了方法的执行效率。

应当理解的是，本说明书未详细阐述的部分均属于现有技术。

应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。