基于边缘计算的隐私保护定位
基于移动边缘计算的隐私保护无线传感器位置协议
摘要
各类物联网应用的出现为人们的生活带来了极大的便利，而无线传感器定位是其中最重要的基础之一。安全与隐私问题应始终是系统设计的首要考虑因素，然而，无线传感器定位的隐私保护尤为困难。本文针对最常见的定位算法——三边测量法和多边测量法，基于Paillier同态加密方案提出了两种隐私保护的定位协议。这些协议设计在移动边缘计算架构中。与其他通过身份匿名来保护位置隐私的方案不同，所提出的协议保护了传感器真实位置信息的隐私。半诚实且彼此不共谋的基站将加密的距离数据发送给边缘服务器，边缘服务器在密文上进行计算并生成传感器的加密位置。该协议的安全性基于Paillier加密的语义安全性。为了以隐私保护的方式获取传感器的位置，所有额外的计算仅包括每个基站的一次加密步骤和传感器的一次解密步骤，并且只需要两次消息传输，因此所提出的协议是安全且实用的。
1. 引言
随着信息技术和传感器网络的快速发展，物联网(IoT)的各种应用已进入人们的生活，如智能家居/楼宇/城市、智能交通、环境监测、医疗保健等。物联网的应用通过传感器收集多种信息（Perera等人，2014年），而无线传感器的位置在其中占据重要地位。例如，一个社交网络应用程序需要获取用户的位置，以便能够向他/她推荐附近的人，追踪他/她的足迹等。近年来，大量基于物联网的应用程序都依赖于定位功能。
在一个传感器网络中，某些节点的位置是已知的，例如基站、卫星、WiFi路由器等，我们称它们为信标节点。通常，定位过程可以分为两个步骤（可选地包含一个优化步骤）：
- 信息收集 。收集用于定位的信息，例如距离、角度等。传感器与信标节点之间的距离可以通过接收信号强度指示（RSSI）、到达时间（ToA）、到达时间差（TDoA）进行测量。角度可以通过到达角（AoA）进行测量。
- 位置计算 。使用收集的信息来计算传感器的位置。简单的算法包括三边测量法，多边测量法，和三角测量法。
在云计算模式中，在信息收集步骤之后，信息被发送到云服务器，服务器执行计算并将传感器的位置返回。然而，由于数据必须从传感器往返传输到遥远的云服务器，这给无线网络带来了巨大的额外开销。因此，传统的云计算无法满足需要即时响应的应用，例如自动驾驶。
边缘计算是一种在靠近数据源的网络边缘执行数据处理的新范式。它是一种优化云计算系统的方法。边缘计算的出现带来了巨大优势，萨特亚纳延（Satyanarayanan, 2017）总结出边缘计算至少在四个方面有所帮助：高度响应的云服务、通过边缘分析实现可扩展性、隐私策略执行以及屏蔽云中断。
图1描述了一种移动边缘计算（MEC）的框架。借助MEC，定位过程中的位置计算步骤可以迁移到边缘服务器上，从而使应用程序能够快速获得响应，并降低整个网络的负载。
尽管有诸多优势，但在边缘计算中应仔细考虑安全与隐私问题。与传统的云计算不同，由于边缘计算基础设施采用分布式部署，容易受到现场攻击。近年来，许多研究探讨了各类边缘计算的安全性，例如索等人（2013）、易等人（2015）、斯托伊梅诺维奇等人（2016）以及罗曼等人（2018）。
位置是一种非常敏感且私人的信息，应谨慎收集、存储和使用，否则可能会造成严重危害。例如，恐怖分子可能通过欺骗自动驾驶系统中车辆的位置信息来实施恐怖袭击。服务提供商通常希望获取用户信息以定制其服务，但不幸的是，安全性在供应商中往往优先级较低，位置信息的安全与隐私也不例外。基于位置的服务（LBS）经常面临攻击。陈等人（2017）总结了与基于位置的服务（LBS）相关的安全问题。他们详细讨论了定位解决方案在鲁棒性、安全性与隐私方面的最新进展，还包括了针对位置数据隐私的法律手段。加密是一种基于内容的保护方法，通常被认为是安全的最后一道防线。我们主要关注使用加密方法来保护位置信息的安全与隐私。
1.1 相关工作
为了实现无线传感器定位的安全性和隐私目标，现有的加密方法旨在信息收集阶段和位置计算阶段均发挥作用。
保护无线传感器定位的安全性包括安全定位和安全位置验证。安全定位是指在受到攻击者攻击的情况下，定位过程仍然能够正确进行；而安全位置验证方案则允许节点验证其他节点（可能是恶意节点）所声称的位置信息。曾等人（2013）对安全定位和安全位置验证进行了综述。一些代表性论文包括萨斯特里等人（2003）、辛格利和普雷内尔（2005）、查普昆和许博（2006），以及魏和关（2013）。这些研究采用了距离绑定技术（布兰兹和肖特姆，1994）、（阿布-马福兹和汉克，2013），其中加密距离绑定是一种证明者与验证者之间的零知识证明协议，它允许证明者向验证者证明两者之间距离的上限，同时保持真实距离的机密性。
在无线定位系统中，隐私保护尤其困难，因为传感器首先需要通过无线电波连接到基站等特定节点，才能接入网络。传感器的位置由接入节点测量的信息以及基站坐标等公开信息计算得出，而所有这些信息都不受传感器控制。一种替代的隐私保护方案是隐藏所有能够识别传感器的信息，例如使用假名，即位置未受保护，但传感器是匿名的。然而，该方法的安全实现较为困难，在实践中仍可能存在追踪用户的风险（赛赫等人，2016）。
隐私保护的另一个主题是基于位置服务中的隐私保护。传感器希望获得基于其位置的服务，但同时又不泄露其真实位置。此外，还有一种替代方法是保护传感器的身份而非其位置，但奥姆等人指出，传统的匿名化技术在提供足够的隐私级别方面 largely failed（奥姆，2009）。因此，我们需要真正保护用户位置信息的技术，且密码学是一个重要的工具。
一些研究采用安全多方计算（SMPC）协议来保护基于位置的服务（LBS）中的隐私。卡特等人（2016）研究了移动设备计算中的外包安全函数评估问题。他们工作的主要贡献是将姚氏混淆电路的繁重计算任务外包给云服务器。作为其方案的一个示例，他们实现了一个外包版本的迪杰斯特拉最短路径算法，该算法可用于设计隐私保护的导航移动应用。SMPC确实能够实现隐私保护，但其计算开销过大，即使移动设备需要云服务器的协助才能执行协议，也不适用于传感器。
另一种直观的隐私保护思路是使用同态加密。传感器可以加密其位置，服务器则能在密文上进行计算而无法获知数据内容。2009年，金特里提出了一种全同态加密（FHE）方案（金特里，2009），该方案允许对加密数据执行任意计算，但效率太低而难以实际应用。尽管后续有一些研究改进了其效率（Brakerski and Vaikuntanathan, 2014）、（布拉克斯等人，2014），但目前不同的实现仍需显著改进才能实用。存在一些实用的部分同态加密方案，仅支持某些操作，例如Paillier加密（帕耶，1999）是一种加法同态加密，埃尔加马尔加密（埃尔加马尔，1985）是一种乘法同态加密。它们可以为一些定义明确的小问题提供可行的解。
1.2 我们的贡献
在本论文中，基于移动边缘计算架构，我们提出了两种基于Paillier同态加密方案的隐私保护位置估计协议。
在基于距离的位置计算中，传感器到基站的距离对基站而言并非秘密，但为了计算传感器的位置，需要多个基站共享该传感器到所有基站的距离。在传统的计算方法中，传感器的位置是明文的，因此基站能够获知该位置，并容易受到威胁。
在我们的隐私保护的位置估计算法中，我们将基站视为半诚实方，且它们之间不会相互共谋。每个基站将距离视为自身的秘密，并使用传感器的公钥对其进行加密。然后所有基站将加密后的数据发送给边缘服务器，边缘服务器对密文进行计算，得到传感器的加密位置。
隐私在该计算模式下得到了良好保护，因为所有在网络中传输的信息均被加密，且传感器的位置信息在整个过程中从未以明文形式出现，只有传感器自身才能获取其自身的位置信息。
对应于最常见的基于距离、三边测量法和多边测量法的位置计算算法，我们设计了两种隐私保护协议。在这两种协议中，传感器仅需对位置的X和Y坐标各进行两次解密操作，每个基站仅需两次加密操作，边缘服务器仅需一些乘法运算。它只需要两次交互，即从基站到边缘服务器和从边缘服务器到传感器。因此，计算复杂度和交互复杂度都较低，且高效实用。
1.3 组织结构
本文的其余部分组织如下。在第2节中，我们介绍了Paillier加密方案及其同态性质的预备知识。在第3节中，我们给出了隐私保护的三边定位协议的构造方法。在第4节中，我们描述了隐私保护的最大似然估计定位协议，这是最高效的多边测量方法。在第5节中，我们分析了我们协议的安全性和效率。在第6节中，我们对论文进行了总结。
2. 预备知识
2.1 IND-CPA安全性用于公钥加密
在Katz和Lindell（2014）中，描述了公钥加密在存在窃听者情况下的不可区分加密的定义，然后他们声明该定义也是IND-CPA安全的。此处，我们对其定义稍作修改，直接给出IND-CPA安全的定义。给定一个公钥加密方案=(Gen、Enc、Dec)和一个敌手A，考虑以下实验：
实验 1 不可区分PubK cpa A, (n)
- 挑战者通过运行Gen(1n)生成(pk,sk)。
- 将公钥pk提供给对手A，然后其输出一对等长的明文m0,m1。
- 挑战者选择一个均匀比特b∈{ 0, 1}，然后计算密文c← Encpk(mb)并将其提供给A。
- 对手A继续选择明文并通过Encpk(·)计算其对应的密文，然后输出一个比特b′。
- 如果b′= b，则实验输出1，表示对手A成功；否则输出0。
定义 2.1. 一个公钥加密方案 =(Gen, Enc, Dec)是IND-CPA安全的，如果对于所有概率多项式时间攻击者 A, 存在一个可忽略函数negl使得
$$
P r[ P ubK cpa A, (n)= 1] ≤ \frac{1}{2} + negl(n)
$$
2.2 佩利耶加密及其性质
在1999年，Pascal Paillier提出了一种概率性公钥加密方案（Paillier, 1999），该方案以佩利耶加密而闻名。它基于计算n次剩余类问题，并实现了IND-CPA安全性。
2.2.1 佩利耶加密
佩利耶加密方案是一个三元组，由概率多项式时间算法(Gen,Enc,Dec)构成，其定义如下：
实验 2 Paillier加密
- Gen ：一个概率密钥生成算法。输入一个安全参数1^k，输出(N,p,q)，其中N== pq，且p和q是k比特的素数（除了在k上可忽略的概率外）。计算φ(N)==(p−− 1)(q−− 1)。公钥PK为N，私钥SK为< N, φ(N)>。我们记作(PK,SK)←← Gen(1^k)
- 加密 ：一个概率消息加密算法。输入一个公钥 N，和一个消息 m ∈ Z N ，选择一个随机数 a均匀分布的r ∈ Z ∗N ，并计算
$$
c:=[(1+ N) m · r N mod N 2]
$$
然后输出密文 c。我们记它为 c ← Enc PK(m)。 - 解密 ：一种确定性解密算法。输入一个私钥< N φ(N)>和一个密文 c，输出
$$
m:=[[ c φ(N) mod N 2] −1 N · φ(N) −1 mod N]
$$
我们记它为m：=解密私钥(密文)。
2.2.2 计算密文的 a+ b
Paillier加密方案是一种加法同态算法。
假设，c a 和 c b 分别是消息 a, b 的两个密文，即
$$
c_a =[( 1 + N) a · r N a mod N 2 ]
$$
$$
c_b = [( 1 + N) b · r N b mod N 2 ]
$$
Let
$$
c_a ∗ c_b=[(1+ N) a · r N a mod N 2] ∗[(1+ N) b · r N b mod N 2]=[ (1+ N) a+ b ·(r_b ∗ r_b) N mod N 2]
$$
容易看出，c a ∗ c b 就是消息 a + b 的密文，也就是说，我们可以通过将 a 和 b 的密文相乘来得到 (a + b) 的密文。我们记作 s C
$$
Enc_{PK}(a+ b)= Enc_{PK}(a) ∗ Enc_{PK}(b) \quad (2.1)
$$
3. 隐私保护的三边定位协议
3.1 三边测量法定位算法
在几何学中，三边测量法是通过测量距离来确定点的绝对或相对位置的过程。如图2所示，为了确定传感器S的未知坐标(x, y)，首先由三个基站A、B和C（其坐标(x A, y A)、(x B, y B)和(x C, y C)为公开已知）利用到达时间(ToA)、接收信号强度指示(RSSI)等方法测量它们到S的距离d A、d B、d C。以(x A, y A)、(x B, y B)和(x C, y C)为圆心，d A、d B、d C为半径，可以构造三个圆，这三个圆的交点即为传感器S的位置。
基于欧几里得距离公式，我们有
$$
\begin{cases}
(x −x_A)^2 +(y −y_A)^2 = d_A^2 \quad (3.1−1)\
(x −x_B)^2 +(y −y_B)^2 = d_B^2 \quad (3.1−2)\
(x −x_C)^2 +(y −y_C)^2 = d_C^2 \quad (3.1−3)
\end{cases}
$$
通过线性化方程(3.1–3)–(3.1–1)和(3.1–3)–(3.1–2)，我们得到
$$
\begin{cases}
2(x_A −x_C)x + 2(y_A −y_C)y = (d_C^2 −x_C^2 −y_C^2) −(d_A^2 −x_A^2 −y_A^2) \
2(x_B −x_C)x + 2(y_B −y_C)y = (d_C^2 −x_C^2 −y_C^2) −(d_B^2 −x_B^2 −y_B^2)
\end{cases}
\quad (3.1)
$$
Let
$$
s_A= d_A^2 −x_A^2 −y_A^2, \quad s_B= d_B^2 −x_B^2 −y_B^2, \quad s_C= d_C^2 −x_C^2 −y_C^2 \quad (3.2)
$$
and
$$
A=\begin{pmatrix}
2(x_A −x_C) & 2(y_A −y_C) \
2(x_B −x_C) & 2(y_B −y_C)
\end{pmatrix}, \quad X=\begin{pmatrix} x \ y \end{pmatrix}, \quad b=\begin{pmatrix} s_C − s_A \ s_C − s_B \end{pmatrix} \quad (3.3)
$$
然后，公式(3.1)可以写成
$$
AX= b \quad (3.4)
$$
解的 Eq.(3.4)是
$$
X= A^{−1} b \quad (3.5)
$$
记
$$
A^{−1}=\begin{pmatrix} a_{11} & a_{12} \ a_{21} & a_{22} \end{pmatrix}
$$
Then
$$
X=\begin{pmatrix} x \ y \end{pmatrix} = A^{−1} b=\begin{pmatrix} a_{11} & a_{12} \ a_{21} & a_{22} \end{pmatrix} ·\begin{pmatrix} s_C − s_A \ s_C − s_B \end{pmatrix} =\begin{pmatrix} (a_{11}+ a_{12}) s_C+(−a_{11}) s_A+(−a_{12}) s_B \ (a_{21}+ a_{22}) s_C+(−a_{21}) s_A+(−a_{22}) s_B \end{pmatrix} \quad (3.6)
$$
3.2 隐私保护三边定位协议的构建
从第3.1节的计算过程中，我们可以推导出隐私保护的思路。
在方程(3.6)中，我们可以看到传感器S的X和Y坐标都可以表示为s A、s B、s C的线性组合，且该线性组合的系数是矩阵A −1中的元素。
首先，让我们来看矩阵A −1的计算。从方程(3.3)可以看出，A是由基站A、B和C的坐标生成的。一旦基站部署完成，其位置将固定且公开已知。因此，A可以被公开计算，同样地，A −1也可以公开计算。此外，由于A −1可在基于基站A、B和C的每次三角测量定位中重复使用，为了避免重复计算并减少在线交互，我们让边缘服务器提前计算A −1并将其存储在基站中。这是一个预计算过程。
其次，从方程(3.2)可以看出，s A、s B、s C 是由私有距离d A、d B、d C 计算得到的，因此它们只能由基站A、B和C秘密计算。
现在，通过Paillier加密的加法同态性，传感器S坐标的密文可以通过三个基站各自生成的三个密文相乘来计算。
我们的隐私保护型三边定位协议在协议3.1中进行了描述。
实验 3.1 隐私保护三边定位协议
- 共同输入 ：
- Paillier加密（Gen, Enc, Dec）。无线传感器S的公钥 PK = N。
- 基站A、B和C的位置坐标 (x A, y A), (x B, y B), 和 (x C, y C)。
- 私有输入 :
- 无线传感器S持有其私钥SK =< N φ(N) >。
- 基站A持有其自身与无线传感器S之间的距离d A，基站B持有距离d B，基站C持有距离d C。
- 私有输出 : 无线传感器 S输出其位置坐标x, y。
- 协议 ：
- 预计算阶段 边缘服务器计算
$$
A^{−1}=\begin{pmatrix}
2(x_A −x_C) & 2(y_A −y_C) \
2(x_B −x_C) & 2(y_B −y_C)
\end{pmatrix}^{−1}
=\begin{pmatrix} a_{11} & a_{12} \ a_{21} & a_{22} \end{pmatrix}
$$
并向 A −1发送至基站 A、 B和 C。 - 交互式阶段
- ∗基站 A计算
$$
s_A= d_A^2 −x_A^2 −y_A^2
$$
$$
c^{(x)} A= Enc {PK}((−a_{11}) s_A)
$$
$$
c^{(y)} A= Enc {PK}((−a_{21}) s_A)
$$
并发送 c(x) A, c(y) A到边缘服务器，
∗基站 B计算
$$
s_B= d_B^2 −x_B^2 −y_B^2
$$
$$
c^{(x)} B = Enc {PK}((−a_{12}) s_B)
$$
$$
c^{(y)} B = Enc {PK}((−a_{22}) s_B)
$$
并发送 c(x) B , c(y) B 到边缘服务器，
∗基站 C计算
$$
s_C= d_C^2 −x_C^2 −y_C^2
$$
$$
c^{(x)} C = Enc {PK}((a_{11}+ a_{12}) s_C)
$$
$$
c^{(y)} C = Enc {PK}((a_{21}+ a_{22}) s_C)
$$
并发送 c(x) C, c(y) C到边缘服务器， - 边缘服务器计算 d
$$
c^{(x)} = c^{(x)}_A ∗ c^{(x)}_B ∗ c^{(x)}_C
$$
$$
c^{(y)} = c^{(y)}_A ∗ c^{(y)}_B ∗ c^{(y)}_C
$$
并发送 c(x) , c(y)到无线传感器S。
- ∗基站 A计算
- 解密和输出阶段
无线传感器 S解密 c (x) , c (y )并获取其位置坐标(x, y)通过
$$
x = 解密_{SK} ( c^{(x)} )
$$
$$
y = 解密_{SK} ( c^{(y)} )
$$
基于移动边缘计算的隐私保护无线传感器位置协议
4. 隐私保护的多边测量法定位协议
4.1 基于最小二乘算法的多边测量法
第3.1节中描述的算法处于理想状态，但在存在距离误差的真实环境中，这些圆可能不会相交于一点。在这种情况下，将使用经典的最小二乘法多边定位算法。
如图3所示，有n个基站参与了定位过程。同样，基于欧几里得距离公式，我们有
$$
\begin{cases}
(x − x_1)^2 +(y − y_1)^2 = d_1^2 \quad (4.1−1)\
(x − x_2)^2 +(y − y_2)^2 = d_2^2 \quad (4.1−2)\
\cdots \
(x − x_n)^2 +(y − y_n)^2 = d_n^2 \quad (4.1−n)
\end{cases}
$$
对于 i = 1 到 n −1, 我们计算(4.1−n)–(4.1−i)并得到方程
$$
\begin{cases}
2(x_1 −x_n)x + 2(y_1 −y_n)y = (d_n^2 −x_n^2 −y_n^2) −(d_1^2 −x_1^2 −y_1^2) \
2(x_2 −x_n)x + 2(y_2 −y_n)y = (d_n^2 −x_n^2 −y_n^2) −(d_2^2 −x_2^2 −y_2^2) \
\cdots \
2(x_{n−1} −x_n)x + 2(y_{n−1} −y_n)y = (d_n^2 −x_n^2 −y_n^2) −(d_{n−1}^2 −x_{n−1}^2 −y_{n−1}^2)
\end{cases}
\quad (4.1)
$$
Let
$$
s_1= d_1^2 −x_1^2 −y_1^2, \quad s_2= d_2^2 −x_2^2 −y_2^2, \quad \cdots, \quad s_n= d_n^2 −x_n^2 −y_n^2 \quad (4.2)
$$
and
$$
A= \begin{pmatrix}
2(x_1 −x_n) & 2(y_1 −y_n) \
2(x_2 −x_n) & 2(y_2 −y_n) \
\vdots & \vdots \
2(x_{n−1} −x_n) & 2(y_{n−1} −y_n)
\end{pmatrix}, \quad X=\begin{pmatrix} x \ y \end{pmatrix}, \quad b= \begin{pmatrix} s_n − s_1 \ s_n − s_2 \ \vdots \ s_n − s_{n−1} \end{pmatrix} \quad (4.3)
$$
然后，式(4.1)可写为
$$
AX= b \quad (4.4)
$$
然后，我们可以使用最小二乘法方程求解方程(4.4)并获得最大似然解
$$
X=(A^T A)^{−1} A^T · b \quad (4.5)
$$
记
$$
(A^T A)^{−1} A^T=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n−1} \ a_{21} & a_{22} & \cdots & a_{2,n−1} \end{pmatrix}
$$
Then
$$
X=\begin{pmatrix} x \ y \end{pmatrix} =(A^T A)^{−1} A^T · b
= \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n−1} \ a_{21} & a_{22} & \cdots & a_{2,n−1} \end{pmatrix} × \begin{pmatrix} s_n − s_1 \ s_n − s_2 \ \vdots \ s_n − s_{n−1} \end{pmatrix}
= \begin{pmatrix}
(a_{11} + \cdots + a_{1,n−1}) s_n +(−a_{11}) s_1 + \cdots+(−a_{1,n−1}) s_{n−1} \
(a_{21} + \cdots + a_{2,n−1}) s_n +(−a_{21}) s_1 + \cdots+(−a_{2,n−1}) s_{n−1}
\end{pmatrix} \quad (4.6)
$$
4.2 隐私保护多边定位协议的构造
分析过程与第4.2节中的相同，通过最小二乘法的多边定位算法生成的传感器S坐标的密文，也可以通过将n个基站各自独立生成的n个密文相乘来计算。
我们的隐私保护三边定位协议在协议4.1中进行了描述。
实验 4.1 隐私保护的多边测量法定位协议
- 公共输入 ：
- 帕累托加密（Gen, Enc, Dec）。无线传感器S的公钥PK = N。
- 基站A₁, A₂, …, Aₙ的位置坐标(x₁, y₁), (x₂, y₂), …, (xₙ, yₙ)。
- 私有输入 ：
- 无线传感器S持有其私钥SK =< N φ(N) >。
- 对于i = 1, …, n，基站Aᵢ持有其自身与无线传感器 S之间的距离 dᵢ。
- 私有输出 ：无线传感器 S输出其位置坐标(x, y)。
- 该协议 ：
- 预计算阶段
边缘服务器计算（A T A） −1 A T ，其中
$$
A= \begin{pmatrix}
2(x_1 −x_n) & 2(y_1 −y_n) \
2(x_2 −x_n) & 2(y_2 −y_n) \
\vdots & \vdots \
2(x_{n−1} −x_n) & 2(y_{n−1} −y_n)
\end{pmatrix}
$$
记
$$
(A^T A)^{−1} A^T=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n−1} \ a_{21} & a_{22} & \cdots & a_{2,n−1} \end{pmatrix}
$$
并发送 (A T A) −1 A T 到基站 A₁, A₂, …, Aₙ。 - 交互式阶段
- ∗基站Aₙ计算
$$
s_n= d_n^2 −x_n^2 −y_n^2
$$
$$
c^{(x)} n= Enc {PK}((a_{11}+ \cdots + a_{1,n−1}) s_n)
$$
$$
c^{(y)} n= Enc {PK}((a_{21}+ \cdots + a_{2,n−1}) s_n)
$$
并发送 c(x)ₙ , c(y)ₙ 到边缘服务器，
∗ 对于 i= 1 到 n −1, 基站 Aᵢ 计算
$$
s_i= d_i^2 −x_i^2 −y_i^2
$$
$$
c^{(x)} i = Enc {PK}((−a_{1i}) s_i)
$$
$$
c^{(y)} i = Enc {PK}((−a_{2i}) s_i)
$$
并发送 c(x)ᵢ, c(y)ᵢ 到边缘服务器 - 边缘服务器计算
$$
c^{(x)} = c^{(x)}_1 ∗ c^{(x)}_2 ∗\cdots ∗ c^{(x)}_n
$$
$$
c^{(y)} = c^{(y)}_1 ∗ c^{(y)}_2 ∗\cdots ∗ c^{(y)}_n
$$
并向无线传感器S发送c(x)、c(y)。
- ∗基站Aₙ计算
- 解密和输出阶段
无线传感器 S解密 c (x) , c (y )并获取其位置坐标(x, y)通过
$$
x = Dec_{SK} ( c^{(x)} )
$$
$$
y= Dec_{SK} ( c^{(y)} )
$$
5. 安全性和效率分析
5.1 安全性分析
在移动边缘计算架构中，我们协议的安全目标是保护传感器位置的隐私，而攻击者包括外部敌手、基站和边缘服务器。
我们假设基站和边缘服务器是半诚实的，且基站之间不共谋。这一假设是合理的，因为作为移动服务提供商基础设施的一部分，基站和边缘服务器必须在服务合同的约束下严格执行协议，但它们是好奇的，并希望从其交互数据中推导出一些额外的信息。
在我们的两个协议中，仅有两次数据传输：第一次是基站将与距离相关的密文传输给边缘服务器，第二次是边缘服务器将位置的密文传输给传感器。直观上，所有在网络上传输的数据都是密文，攻击者无法获取其内容，除非他们能够解密，因此隐私性依赖于加密方案的安全性。
为了定义位置协议的位置隐私，我们采用了加密方案中 IND-CPA安全的相同思想。从语义角度来看，具有位置隐私的位置协议意味着：给定该位置协议的交互脚本，攻击者无法获得关于真实位置的任何信息。另一个角度是，给定两个位置以及其中一个位置生成的交互脚本，攻击者无法确定该交互脚本是由哪个位置生成的。因此我们将位置隐私转化为位置不可区分。
注意在我们提出的两个协议中，传感器的公钥以及基站的位置是公开已知的，因此攻击者可以选择任意位置，并模拟一段合法的交互脚本。因此攻击者具有选择位置攻击的能力。
5.1.1 位置隐私的形式化定义
给定一个定位协议 和一个攻击者 A, 考虑以下位置可区分实验：
实验 5 位置区分实验 LP IND−CLA A(n)
- 挑战者设置一个包含 (pk, sk) 的 , 实例。
- 对手 A 获得公钥 pk，然后输出一对位置 (x₀, y₀), (x₁, y₁)。
- 挑战者选择一个均匀比特 b ∈ {0, 1}，并将 (x_b, y_b) 视为传感器的位置，并生成 的交互脚本，然后将该脚本交给 A。
- 对手 A 继续选择位置并计算 π 的交互脚本，然后输出一个比特 b′。
- 如果 b′ = b，则实验输出1，表示对手 A 成功，否则输出0。
定义 5.1. 若对于所有概率多项式时间攻击者 A, 协议 是 LIND-CLA （在选择位置攻击下位置不可区分，Location Indistinguishable under the Choose Location Attack），如果对所有概率多项式时间攻击者 A, 存在一个可忽略函数 negl 使得
$$
P r[ LP IND−CLA_A (n)= 1] ≤ \frac{1}{2} + negl(n)
$$
5.1.2 所提协议的安全性证明
我们将证明我们提出的两个协议均满足 LIND-CLA 安全性，其基于 Paillier 加密的 IND-CPA 安全性。
定理 5.2。 协议3.1中的隐私保护三方定位协议在Paillier加密的 IND-CPA安全基础上是LIND-CLA安全的。
证明。 设P=(Gen, Enc, Dec)是一个Paillier加密方案，且L是协议3.1中的隐私保护的三边定位协议。假设A_L是L的一个对手，其优势为δ，即
$$
P r[ LP IND−CLA_{A_L} (n)= 1] ≤ \frac{1}{2} + δ \quad (5.1)
$$
现在，基于A_L的能力，我们构建一个敌手A_P，其试图攻破 Paillier加密的IND-CPA安全性。
1. 设CP是A_P的挑战者，然后CP运行生成并获得公钥pk和私钥sk。CP将公钥pk发送给A_P。
2. A_P生成一个L实例，在该实例中，他将pk设为传感器的公钥。他将公钥pk发送给A_L。
3. A_L选择一对位置(x₀, y₀)、(x₁, y₁)，并将它们发送给A_P。
4. A_P执行利用基站A、B和C的位置坐标 (x_A, y_A)、(x_B, y_B) 和 (x_C, y_C)，计算
$$
A^{-1}=\begin{pmatrix}
2(x_A −x_C) & 2(y_A −y_C) \
2(x_B −x_C) & 2(y_B −y_C)
\end{pmatrix}^{-1}
=\begin{pmatrix} a_{11} & a_{12} \ a_{21} & a_{22} \end{pmatrix}
$$
• 通过公式
$$
d_{0A} = \sqrt{(x_A − x_0)^2 + (y_A − y_0)^2}, \quad d_{0B} = \sqrt{(x_B − x_0)^2 + (y_B − y_0)^2}, \quad d_{0C} = \sqrt{(x_C − x_0)^2 + (y_C − y_0)^2}
$$
计算 (x₀, y₀) 与基站 A、B 和 C 之间的距离。
• 通过
$$
d_{1A} = \sqrt{(x_A − x_1)^2 + (y_A − y_1)^2}
$$
计算 (x₁, y₁) 与基站 A 之间的距离。
• 计算
$$
s_{0A}=(d_{0A})^2 −x_A^2 −y_A^2, \quad s_{0B}=(d_{0B})^2 −x_B^2 −y_B^2, \quad s_{0C}=(d_{0C})^2 −x_C^2 −y_C^2
$$
• 计算
$$
s_{1A}=(d_{1A})^2 −x_A^2 −y_A^2
$$
• 计算
$$
m_0 = −a_{11} · s_{0A}, \quad m_1 = −a_{11} · s_{1A}
$$
5. A_P向CP发送m₀和m₁。
6. CP随机选择一个比特b ∈ {0, 1}，并发送密文c = Enc_pk(m_b)给A_P。
7. A_P执行以下操作：模拟基站A，计算 c(y)A = Enc_pk(−a₁₂ · s₀A)，将 (c, c(y)A) 发送给边缘服务器；模拟基站B，计算 c(x)B = Enc_pk(−a₁₁ · s₀B) 和 c(y)B = Enc_pk(−a₁₂ · s₀B)，将 (c(x)B, c(y)B) 发送给边缘服务器；模拟基站C，计算 c(x)C = Enc_pk(−a₁₁ · s₀C) 和 c(y)C = Enc_pk(−a₁₂ · s₀C)，将 (c(x)C, c(y)C) 发送给边缘服务器；模拟边缘服务器，计算 c(x) = c ∗ c(x)B ∗ c(x)C 和 c(y) = c(y)A ∗ c(y)B ∗ c(y)C，将 (c(x), c(y)) 发送给传感器。
8. A_P将第7步生成的交互脚本发送给A_L。
9. 在收到A_P发来的交互脚本后，A_L将b′发送给A_P。
10. A_P将b′发送给CP。
现在让我们分析一下 A_P的成功概率。A_P成功的情况有两种。
情况1。 在上述步骤的步骤6中，CP选择b = 0。这种情况发生的概率为1/2。在这种情况下，A_P在步骤7生成的交互脚本是关于位置 (x₀, y₀) 的正确脚本，假设A_L返回b′ = 0的概率为 1/2 + δ，因此在此情况下，A_P的成功概率为 1/2(1/2 + δ)。
情况2。 在上述步骤的步骤6中，CP选择b = 1。这种情况发生的概率也为1/2。在这种情况下，注意到在步骤7中对基站A的模拟中，c由s₁A计算得出，而c(y)A由s₀A计算得出，因此由A_P生成的交互脚本是一个非法脚本。在此情况下，A_L在位置区分实验中没有任何优势，因此A_L返回b′ = 1的概率仅为1/2，因此在这种情况下，A_P的成功概率为1/2(1/2)。
从情况1和情况2可知，A_P的成功概率为
$$
P r[ PubK cpa_{A_P, P} (n)= 1] = \frac{1}{2}\left(\frac{1}{2} + δ\right) + \frac{1}{2}\left(\frac{1}{2}\right) = \frac{1}{2} + \frac{1}{2}·δ \quad (5.2)
$$
我们已经知道Paillier加密是IND-CPA安全的，因此根据定义2.1，存在一个可忽略函数 negl’，使得A_P
$$
P r[ PubK cpa_{A_P, P} (n)= 1] ≤ \frac{1}{2} + negl’(n) \quad (5.3)
$$
由 Eq. (5.2)和(5.3)，可得
$$
\frac{1}{2} + \frac{1}{2}·δ ≤ \frac{1}{2} + negl’(n) \quad (5.4)
$$
即
$$
δ ≤ 2 negl’(n) \quad (5.5)
$$
将 Eq.(5.5)代入 Eq.(5.1)并令 negl(n)=2 negl’(n), 可得
$$
P r[ LP IND−CLA_A (n)= 1] ≤ \frac{1}{2} + negl(n)
$$
因此，协议 3.1是 LIND-CLA。
定理 5.3。 协议4.1中的隐私保护三方定位协议在Paillier加密的 IND-CPA安全基础上是LIND-CLA安全的。
定理 5.3的证明与定理 5.2的证明非常相似，此处省略证明。
5.2 效率分析
我们首先分析通信轮次复杂度。在两个协议中，仅需要两次数据传输：第一次是从基站到边缘服务器，第二次是从边缘服务器到传感器。因此，这两个协议的通信轮次均为两轮。
然后我们分析通信流量。从协议3.1和4.1的交互阶段可以看出，在这两个协议中，每个基站需要发送两个Paillier加密的密文，边缘服务器也需要发送两个密文。Paillier加密的密文空间是Z_N²，因此每个密文长度为log₂N²比特。协议3.1中有三个基站，协议4.1中有n个基站，因此协议3.1的总通信流量为8log₂N²比特，协议4.1的总通信流量为(2n + 2)log₂N²比特。
最后，我们分析计算开销。从两个协议的描述可以看出，每个基站需要进行两次加密操作，边缘服务器仅需进行n − 1次模乘操作（其中n为基站数量），而传感器需要进行两次解密操作。由于在Paillier加密中，每次加密需要2log₂N次模N²乘法运算，每次解密需要log₂N次模N²乘法运算，其中N为公钥。
我们总结了计算成本和通信成本，见表1。
| 通信轮次 | 通信流量（比特） | 计算开销（MN²s） | |
|---|---|---|---|
| 基站 | 边缘服务器总计 | ||
| P 3.1 | 2 | 2log₂N² | 2log₂N² |
| P 4.1 | 2 | 2log₂N² | 2log₂N² |
| 1 MN²：模 N²乘法计算 | 2 N: Paillier加密的公钥， | 3 n:基站数量 |
6. 结论与未来工作
在本论文中，我们致力于设计隐私保护的无线传感器定位协议。我们利用边缘计算架构，主要技术是加法同态加密的应用。我们选择两种基于距离的无线定位算法，即三边测量法和最小二乘法多边测量法。并将它们转换为隐私保护协议。这两种算法能够被转换的原因在于，它们都可以被线性化为线性方程，且方程的解可以表示为秘密距离的线性组合。然后，基于加法同态，可以通过每个距离的密文计算出解的密文。因此，我们协议的设计非常直观且简单，其安全性完全基于同态加密。整个协议是安全且实用的。
实际上，仍然存在各种无线定位算法，其中一些基于距离差，另一些基于角度。考虑到效率，这些算法通常基于数值计算进行设计。基本上，这些算法中包含非线性操作，因此我们的转换模式无法直接应用于它们以生成其隐私保护版本。
我们将在未来的工作中尝试解决这些问题。第一个可行的方法是寻找现有定位算法的线性化方法。第二种方法是利用同态加密的更多性质，例如Paillier加密的明文乘法性质。最后，也许我们可以使用安全多方计算（SMPC）的技术来解决该问题。
码道开发者社区，聚焦华为云码道 CodeArts 代码智能体，沉淀 Agent、Skill、鸿蒙开发实战内容，供开发者查阅资料、交流技术、分享工程实践
更多推荐
14
0- 0
已为社区贡献1条内容
所有评论(0)