位置服务（location-based service，LBS）是一类在定位技术、地理信息系统和第三方位置服务提供商的支撑下，以用户位置信息为基础，向移动用户提供与位置相关的增值服务的总称^[1-2]。近年来，LBS作为移动互联网中最重要的移动服务之一，正在全球以惊人的速度发展普及，呈现出井喷式发展态势。用户在享受更多位置服务的同时，也产生了大量位置数据信息，这些信息往往会明显或隐性地暴露用户的个人隐私信息，产生蝴蝶效应，引发更严重的个人隐私安全问题^[3]。《Science》的“The end of privacy”^[4]专题就曾指出，从用户的运动轨迹和位置信息，就能推理出其惯用路线、家庭工作单位地点、健康状况、生活习惯、兴趣爱好、社交关系、平时乘坐交通工具^[5]等个人隐私信息。位置相关敏感信息的泄露已成为LBS中最大的隐私威胁，也给LBS在军用、民用领域的全方位普及带来了前所未有的挑战。然而，在当前移动社交网络中，LBS的应用几乎都离不开多方之间位置信息的实时共享^[6]，其中因共享导致的隐私泄露问题不容忽视。因此，如何在共享的同时实现对用户的位置隐私保护，已经成为研究者关注的热点和亟待解决的问题，深入研究符合网络特点和现实需求的LBS位置隐私保护技术具有广阔的应用前景和重要的现实意义。

传统的位置信息共享过程实行的是刚性的“全部或全不”隐私保护策略，无法满足用户的个性化、弹性位置隐私保护需求。为此，Marias等^[7]最先提出将秘密共享技术用于位置信息的隐私保护，将用户位置信息利用随机数加密拆分成多个份额，并存放于多个STS（share the secret）服务器中，当用户发起位置服务时，位置服务器需要向每个STS服务器发出申请获得份额。虽然，该方案因引入额外的存储服务器会增加新的性能瓶颈与安全风险，也无法根据不同访问权限提供分级精度的位置共享结果，但是，其提出的多服务器秘密共享存储技术非常值得借鉴。Dürr等^[8]借鉴多服务器存储的方法提出了在不可信系统中利用秘密共享策略实现位置共享隐私保护。该方案将系统假设为部分可信，基于坐标变换和空间模糊设计了位置秘密共享方法，分发有限精度的位置份额给多个位置服务器，不同精度的份额集合可重构出不同程度模糊的位置信息。但是，该方案有两个份额产生算法，较为复杂，多级别的位置信息需要多次共享，用户终端计算量较大。为了克服上述缺点，Skvortsov等^[9]在开放的网络环境下，将精确位置模糊成具有不同半径的圆形区域，令攻击者从一定数量的份额中再难得到更加精确的位置信息。但是，该方案在较长时间内目标位置更新时生成的份额并不更新，仅适用于“签到”模式，且存储份额的服务器发生问题时，仍会泄露一定精度的目标位置信息。同时，Wernke等^[10]提出了Pshare方案。该方案是第一个针对语义位置的多秘密共享隐私保护方案，解决了连续位置更新问题，增强了算法抵抗多种攻击的鲁棒性，并在后续研究中进行了优化和仿真^[11-12]。然而，上述方案的计算量较大，当位置份额数量或参与存储份额的位置服务器增加时，其计算份额和重构位置的运算开销也会急剧增加，在移动互联网中资源受限的用户终端上并不适用。2017年，Skvortsov等^[13]改变了之前文献[8-9, 11-12]方案中一直采用的“平等份额分发”模式，而预设服务器具有不同的可信级，可信度高的服务器能够存储更高精度的位置信息，反之亦然。但由于可信度高的服务器存储的是更高精度（更多数量）份额，该类服务器易变成攻击热点，且该方案直接采用一般概率信任模型^[14]进行分级，需要额外维护管理一个服务器信任分级数据库。

综上所述，虽然LBS中位置共享隐私保护问题没有得到完美解决，但这些方案将位置信息转化为一系列份额分发给多个位置服务器以实现隐私保护的思想具有可借鉴性。作者针对多用户位置共享中的好友查找应用^[15-16]，基于弹性位置隐私保护策略，提出了一种能够满足用户个性化需求的分级位置共享隐私保护方案。本方案不需要引入其他服务器，也不依赖于位置服务器集的可信度，利用基于中国剩余定理的门限可变多秘密共享方法弹性地满足用户不同精度位置信息的共享需求。

1 方案描述 1.1 系统模型

如图1所示，方案的系统模型主要由定位系统和位置隐私保护系统两部分组成。其中，位置隐私保护系统由查询目标 ${Q_o}$ 、用户终端 ${C_{{*}}}$ （共享 ${Q_o}$ 位置的用户）以及n个位置服务器集合（ ${s{p_1},s{p_2}, \cdots ,s{p_n}}$ ）组成。

1.2 位置转换模型

用户通过两种位置转换模型可灵活地将真实位置坐标转换成不同精度的位置信息分级共享给其他用户，即自主把握共享位置的对象与精度级别，这更有利于满足实际网络环境中用户的个性化隐私需求。

1）地理位置转换模型

通常情况下，通过定位系统获得的位置经纬度坐标一般都以度（°）、分（′）、秒（″）表示，若用G表示查询目标的精确位置，则用户真实位置的地理坐标数字表示为 $G = \left\{ {I_1^\circ ,{{I_2'}},{{I_3''}},J_1^\circ ,{{J_2'}},{{J_3''}}} \right\}$ 。用 ${G_{{L_i}}} = p(G,{L_i}) = \{ {T_{i,1}},{T_{i,2}}, \cdots ,{T_{i,{r_{{L_i}}}}}\} $ 表示由真实位置而来的精度级别为L_i的位置信息。此时，根据度、分、秒的精度级别，可将地理位置转换成： ${G_{{L_1}}} = p(G,{L_1}) = \left\{ {{I^\circ_1},{J^\circ_1}} \right\} = \{ {T_{1,1}},{T_{1,2}}\} $ 即 ${L_1}$ 精度级（精确到度）的位置坐标； ${G_{{L_2}}} = p(G,{L_2}) = \left\{ {{I^\circ_1},{{I_2'}},{J^\circ_1},{{J_2'}}} \right\} = \{ {T_{2,1}},{T_{2,2}},{T_{2,3}},{T_{2,4}}\} $ 即 ${L_2}$ 精度级（精确到分）的位置坐标； ${G_{{L_3}}} = p(G,{L_3}) = \left\{ {I^\circ_1},{{I_2'}},{{I_3''}},{J^\circ_1},{{J_2'}},{{J_3''}} \right\} = \{ {T_{3,1}},{T_{3,2}}, \cdots ,{T_{3,6}}\} $ 即 ${L_3}$ 精度级（精确到秒）的位置坐标。 ${G_{{L_1}}}$ 、 ${G_{{L_2}}}$ 、 ${G_{{L_3}}}$ 构成了 ${L_{\max }} = 3$ 的不同精度级别的位置信息，即为需要共享的秘密，每组的秘密个数分别为 ${r_1} = 2$ ， ${r_2} = 4$ ， ${r_3} = 6$ 。

2）语义位置转换模型

根据通用规则，语义位置通常表示为{国家，省（州），市，区（县），乡/镇（街道），门牌号}，可根据一定数字映射关系（规则）建立语义转换数据库，将语义位置对应表示为数字。如语义位置{中国，陕西省，西安市，未央区，三桥武警路，66号}对应的数字坐标可转换为{0086，71，00，86，0010，66}。精确位置的语义位置对应的数字坐标可表示为 $G = \left\{ {{s_1},{s_2}, \cdots ,{s_{L_{\max} }}} \right\}$ 。与地理位置转换类似，查询目标 ${Q_o}$ 能够灵活地将不同精度级别的语义位置转化为不同的数字坐标。其语义位置可定义为以下精度递增的6个级别： ${G_{{L_1}}} = p(G,{L_1}) = \left\{ {{s_1}} \right\} = \left\{ {{T_{1,1}}} \right\}$ 表示 ${L_1}$ 精度级的位置坐标，即共享的位置信息仅体现 ${Q_o}$ 所在的国家； ${G_{{L_2}}} = p(G,{L_2}) = \left\{ {{s_1},{s_2}} \right\} = \left\{ {{T_{2,1}},{T_{2,2}}} \right\}$ 表示 ${L_2}$ 精度级（精确到省域）的位置坐标；以此类推， ${G_{{L_3}}} = p(G,{L_3}) = \left\{ {{s_1},{s_2},{s_3}} \right\} = \left\{ {T_{3,1}},{T_{3,2}},\right. \left.{T_{3,3}} \right\}$ 表示 ${L_3}$ 精度级（精确到市域）的位置坐标； ${G_{{L_4}}}$ 表示 ${L_4}$ 精度级（精确到区（县）域）的位置坐标； ${G_{{L_5}}}$ 表示 ${L_5}$ 精度级（精确到乡（镇）街道域）的位置坐标； ${G_{{L_6}}}$ 表示 ${L_6}$ 精度级（精确到门牌域）的位置坐标。由此， ${G_{{L_1}}},{G_{{L_2}}}, \cdots ,{G_{{L_6}}}$ 构成 ${L_{\max }} = 6$ 的不同精度级别的位置信息，即为需要共享的秘密，每组的秘密个数分别为 ${r_1} = 1$ ， ${r_2} = 2$ ， ${r_3} = 3$ ， ${r_4} = 4$ ， ${r_5} = 5$ ， ${r_6} = 6$ 。

1.3 位置信息共享机制

本方案中位置信息共享机制将 ${Q_o}$ 定义的 ${L_{\max }}$ 个不同精度级的位置信息，并打包成一组秘密进行处理转换，采用基于中国剩余定理的多秘密共享方法^[17]对位置份额进行一次分发，可使不同位置份额集重构出不同精度级别的位置信息。共享机制主要包括3个部分：系统参数初始化、秘密分发和秘密重构。

1.3.1 初始化

${G_{{L_1}}},{G_{{L_2}}}, \cdots ,{G_{{L_{\max }}}}$ 构成 ${L_{\max }}$ 组需要共享的秘密集，每组的秘密个数分别为 ${r_{{L_1}}},{r_{{L_2}}}, \cdots ,{r_{{L_{\max }}}}$ 。各组秘密分别根据不同的 $\left( {{t_i},n} \right)$ 的门限访问进行共享，其中， ${t_i}$ 为计算 ${G_{{L_i}}}$ 时需要的份额数量（门限值）， $1 \le i \le {L_{\max }}$ ，门限值满足 $1 \le {t_1} \le {t_2} \le \cdots \le {t_{{L_{\max }}}}$ 。 ${Q_o}$ 在分发秘密时将门限访问结构、参与的位置服务器等信息在公告牌上发布。

1.3.2 份额生成与分发

${Q_o}$ 将不同精度级别的位置信息与不同信任关系的用户共享，其中，精度级别和 ${C_{{*}}}$ 的对应关系由 ${Q_o}$ 自行确定发送给位置服务器。 ${Q_o}$ 首先为每个参与的位置服务器 $s{p_1},s{p_2}, \cdots ,s{p_n}$ 产生并发送一个主份额，产生过程如下：

1）查询目标选择 ${L_{\max }}$ 个互不相同的素数 ${q_1} < {q_2} < \cdots < {q_{{L_{\max }}}}$ ，满足 ${T_{i,j}} < {q_i}(1 \le i \le {L_{\max }},j = 1,2, \cdots ,{r_{{L_i}}})$ ， $n < {q_1}$ 和 ${r_{{L_{\max }}}} < {q_1}$ ；若 ${r_{{L_{\max }}}} > {t_1}$ ，则还要满足 ${r_{{L_{\max }}}} - {t_1} + 1 + n < {q_1}$ 。

2）若 ${r_{{L_{\max }}}} > {t_1}$ ，在区间 $[{r_{{L_{\max }}}} - {t_1} + 1,{q_1})$ 上任意选择 $n$ 个不同整数 ${x_1},{x_2}, \cdots ,{x_n}$ 分别作为 $s{p_1},s{p_2}, \cdots ,s{p_n}$ 的公开身份标志；若 ${r_{{L_{\max }}}} \le {t_1}$ ，在 $[1,{q_1}]$ 上任意选择 $n$ 个不同整数 ${x_1},{x_2}, \cdots ,{x_n}$ 作为 $s{p_1},s{p_2}, \cdots ,s{p_n}$ 的公开身份标志。

3）令 ${a_0},{a_1}, \cdots ,{a_{{r_{{L_{\max }}}} - 1}}$ 分别为下列 ${r_{{L_{\max }}}}$ 组恒等式的解：

$\left\{ \begin{array}{l} \left\{ \begin{array}{l} {a_0} \equiv {T_{1,1}}od {q_1},\\ {a_0} \equiv {T_{2,1}}od {q_2},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\vdots \\ {a_0} \equiv {T_{{L_{\max }},1}}od {q_{{L_{\max }}}}; \end{array} \right.\left\{ \begin{array}{l} {a_1} \equiv {T_{1,2}}od {q_1},\\ {a_1} \equiv {T_{2,2}}od {q_2},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\vdots \\ {a_1} \equiv {T_{{L_{\max }},2}}od {q_{{L_{\max }}}}; \end{array} \right.\\ \begin{array}{*{20}{l}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\cdots \end{array}\\ \left\{ \begin{array}{l} {a_{{r_{{L_1}}} - 1}} \equiv {T_{1,{r_{{L_1}}}}}od {q_1},\\ {a_{{r_{{L_1}}} - 1}} \equiv {T_{2,{r_{{L_1}}}}}od {q_2},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\vdots \\ {a_{{r_{{L_1}}} - 1}} \equiv {T_{{L_{\max }},{r_{{L_1}}}}}od {q_{{L_{\max }}}}; \end{array} \right.\left\{ \begin{array}{l} {a_{{r_{{L_1}}}}} \equiv 0od {q_1},\\ {a_{{r_{{L_1}}}}} \equiv {T_{2,{r_{{L_1}}} + 1}}od {q_2},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\vdots \\ {a_{{r_{{L_1}}}}} \equiv {T_{{L_{\max }},{r_{{L_1}}} + 1}}od {q_{{L_{\max }}}}; \end{array} \right.\\ \begin{array}{*{20}{l}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\cdots \end{array}\\ \left\{ \begin{array}{l} {a_{{r_{{L_{\max }}}} - 1}} \equiv 0od {q_1},\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\vdots \\ {a_{{r_{{L_{\max }}}} - 1}} \equiv 0od {q_{{L_{\max }} - 1}},\\ {a_{{r_{{L_{\max }}}} - 1}} \equiv {T_{{L_{\max }},{r_{{L_{\max }}}}}}od {q_{{L_{\max }}}}\end{array} \right. \end{array} \right.$

(1)

由中国剩余定理可求得式（1）的解 ${a_0},{a_1}, \cdots , {a_{{r_{{L_{\max }}}} - 1}}$ 。

4）构造多项式。令 $M =\displaystyle \prod\limits_{i = 1}^{{L_{\max }}} {{q_i}} $ ：

①若 ${r_{{L_{\max }}}} > {t_1}$ ，对于 $i = 1,2, \cdots ,{L_{\max }} - 1$ ，计算 ${b_{{t_i}}}, {b_{{t_i} + 1}}, \cdots ,{b_{{t_{i + 1}} - 1}}$ ：

设 $j = {t_i},{t_i} + 1, \cdots ,{t_{i + 1}} - 1$ ， ${b_j} = {{\textit{z}}_j} \times {\lambda _j} \times \displaystyle\prod\limits_{u = 1}^i {{q_u}} od \;M$ ，其中， ${{\textit{z}}_j}$ 为 $\left\{ {1,2, \cdots ,{q_i} - 1} \right\}$ 上的任意整数， ${\lambda _j}$ 为任意非零整数，则构造一个多项式，此多项式的阶为 $({r_{{L_{\max }}}} + {t_{{L_{\max }}}} - {t_1} - 1)$ ：

$ \begin{aligned}[b] F(x) =& {a_0} + {a_1}x + \cdots + {a_{{r_{_{{L_{\max }}}}} - 1}}{x^{{r_{{L_{\max }}}} - 1}} + \\ &{b_{{t_1}}}{x^{{r_{{L_{\max }}}}}} + \cdots + {b_{{t_{{L_{\max }}}} - 1}}{x^{{r_{{L_{\max }}}} + {t_{{L_{\max }}}} - {t_1} - 1}} \end{aligned} $

(2)

②若 ${r_{{L_{\max }}}} \le {t_1}$ ，则任意选择 $\left( {{t_1} - {r_{{L_{\max }}}}} \right)$ 个整数，满足 $1 < {a_{{r_{L{}_{\max }}}}},{a_{{r_{L{}_{\max }}} + 1}}, \cdots ,{a_{{t_1} - 1}} < M$ ，设 $j = {t_i},{t_i} + 1, \cdots ,{t_{i + 1}} - 1$ ， ${a_j} = {{\textit{z}}_j} \times {\lambda _j} \times \displaystyle\prod\limits_{u = 1}^i {{q_u}} od \;M$ ，其中， ${{\textit{z}}_j}$ 为 $\left\{ {1,2, \cdots ,{q_i} - 1} \right\}$ 上的任意整数， ${\lambda _j}$ 为任意非零整数，构造如下多项式，此多项式阶为 $\left( {{t_{{L_{\max }}}} - 1} \right)$ ：

${\;\;\;\;\;\;\;\;\;\;\;F(x)} = {a_0} + {a_1}x + \cdots + {a_{{t_{_{{L_{\max }}}}} - 1}}{x^{{t_{{L_{\max }}}} - 1}}$

(3)

5）计算 $s{p_1},s{p_2}, \cdots ,s{p_n}$ 的主份额 ${S_i}(1 \le i \le n)$ ：

$ {S_i} = F({x_i})od M $

(4)

6）若 ${r_{{L_{\max }}}} > {t_1}$ ，计算公共值 ${d_i}\left( {1 \le i \le {r_{{L_{\max }}}} - {t_1}} \right)$ ：

${d_i} = F\left( i \right)od M$

(5)

7）将 ${S_i}$ 通过安全信道传送给各参与的位置服务器 $s{p_i}$ ，公布 ${q_1},{q_2}, \cdots ,{q_{{L_{\max }}}}$ ；若 ${r_{{L_{\max }}}} > {t_1}$ ，再公布公共值 ${d_1},{d_2}, \cdots ,{d_{{r_{{L_{\max }}}} - {t_1}}}$ 。由位置服务器存储并管理收到的份额及公共值。

1.3.3 秘密重构

${Q_o}$ 自主定义不同用户对自身位置的访问权限级别并形成“好友列表”发送给位置服务器。需要共享 ${Q_o}$ 位置时，位置服务器运行访问控制机制（查看 ${Q_o}$ “好友列表”）后，将生成的影子份额发送给该用户即可重构出对应精度级别的位置信息。

假设用户 ${C_A}$ 要对 ${Q_o}$ 进行好友查找，共享其位置， ${Q_o}$ 确定该用户的访问权限等级为 ${L_i}$ 级：

1）若 ${r_{{L_{\max }}}} > {t_1}$ ，由于 ${a_j} \equiv 0\;od \;{q_i}(j = {r_{{L_i}}},{r_{{L_{i + 1}}}}, \cdots , {r_{{L_{\max }} - 1}})$ 和 ${b_j} \equiv 0\;od \;{q_i}(j = {t_i},{t_i} + 1, \cdots ,{t_{{L_{\max }}}} - 1)$ ，则 ${G_{{L_i}}}$ 对应的秘密多项式为：

${\;\;\;\;\;\;\;\;\;\;\;{F_i}(x)} = F\left( x \right)od \;{q_i}\left( { \in {\mathbb{Z}_{{q_i}}}\left[ x \right]} \right)$

(6)

且满足 $\deg ({F_i}(x)) \le {r_{{L_{\max }}}} + {t_i} - {t_1} - 1$ 。

${t_i}$ 个位置服务器 $s{p_j}\left( {1 \leq j \leq {t_i}} \right)$ 向用户发送其生成的影子份额：

$ {S_{i,j}} = {S_j}od \;{q_i} $

(7)

则用户得到 ${t_i}$ 个点 $({x_1},{S_{i,1}}),({x_2},{S_{i,2}}), \cdots ,({x_{{t_i}}},{S_{i,{t_i}}})$ ，再利用已公布的公共信息 ${d_1},{d_2}, \cdots ,{d_{{r_{{L_{\max }}}} - {t_1}}}$ ，用户可分别计算：

$\left\{ {\begin{array}{*{20}{l}} {{{d}_1'} \equiv {d_1}od \;{q_i},} \\ {{{d}_2'} \equiv {d_2}od \;{q_i},} \\ \quad\quad\quad\vdots \\ {{{d}_{{r_{{L_{\max }}}} - t{}_1}'} \equiv {d_{{r_{{L_{\max }}}} - t{}_1}}od \;{q_i}} \end{array}} \right.$

(8)

则用户又可得到 $({r_{{L_{\max }}}} - {t_1})$ 个点 $(1,{d'_1}),(2,{d'_2}), \cdots ,({r_{{L_{\max }} - {t_1}}}, {d'_{{r_{{L_{\max }}}} - {t_1}}})$ ，利用Lagrange插值多项式重构秘密多项式 ${F_i}\left( x \right)$ ：

$ \begin{aligned}[b] {F_i}\left( x \right) &= F\left( x \right)od \;{q_i} = \\ &\;\;\left(\sum\limits_{j = 1}^{{t_i}} {\left( {{S_{i,j}}\prod\limits_{h = 1,h \ne j}^{{t_i}} {\frac{{x - {x_h}}}{{{x_j} - {x_h}}}} \prod\limits_{v = 1}^{{r_{{L_{\max }}}} - {t_1}} {\frac{{x - v}}{{{x_j} - v}}} } \right)} +\right. \\ &\left.\;\sum\limits_{j = 1}^{{r_{{L_{\max }}}} - {t_1}} {\left( {{{d}_j'}\prod\limits_{v = 1,v \ne j}^{{r_{{L_{\max }}}} - {t_1}} {\frac{{x - v}}{{j - v}}} \prod\limits_{h = 1}^{{t_i}} {\frac{{x - {x_h}}}{{j - {x_h}}}} } \right)}\right)od \;{q_i} = \\ &\;\;\;\;\;\;\;{a_0} + {a_1}x + \cdots + {a_{{r_{{L_{\max }}}} - 1}}{x^{{r_{{L_{\max }}}} - 1}} + \\ &\;{b_{{t_1}}}{x^{{r_{{L_{\max }}}}}} + \cdots + {b_{{t_{{L_{\max }}}} - 1}}{x^{{r_{{L_{\max }}}} + {t_{{L_{\max }}}} - {t_1} - 1}}od \;{q_i} = \\ &\;\;\;\;\;\;\;{a_0} + {a_1}x + \cdots + {a_{{r_{{L_{\max }}}} - 1}}{x^{{r_{{L_{\max }}}} - 1}} + \\ &\;\;\;\;\;\;\;{b_{{t_1}}}{x^{{r_{{L_{\max }}}}}} + \cdots + {b_{{t_i} - 1}}{x^{{r_{{L_{\max }}}} + {t_i} - {t_1} - 1}}od \;{q_i}\\[-10pt] \end{aligned} $

(9)

由 ${F_i}\left( x \right)$ 的前 ${r_{{L_i}}}$ 个系数即可恢复出精度为 ${L_i}$ 级的位置坐标 ${G_{{L_i}}} = \left\{ {{T_{{L_i},1}},{T_{{L_i},2}}, \cdots ,{T_{{L_i},{r_{{L_i}}}}}} \right\}$ ，其中：

$\left\{ \begin{array}{l} {T_{{L_i},1}} = {a_0}od \;{q_i}, \\ {T_{{L_i},2}} = {a_1}od \;{q_i}, \\ \quad\quad\quad\vdots \\ {T_{{L_i},{r_{{L_i}}}}} = {a_{{r_{{L_i}}} - 1}}od \;{q_i} \\ \end{array} \right.$

(10)

2）若 ${r_{{L_{\max }}}} \le {t_1}$ ，则 ${G_{{L_i}}}$ 对应的秘密多项式为：

${\;\;\;\;\;\;\;\;\;\;\;\;{F_i}\left( x \right)} = F\left( x \right)od \;{q_i}\left( { \in {\mathbb{Z}_{{q_i}}}[x]} \right)$

(11)

且满足 $\deg ({F_i}(x)) \le {t_i} - 1$ 。

${t_i}$ 个位置服务器 $s{p_j}\left( {1 \le j \le {t_i}} \right)$ 向用户发送其生成的影子份额：

$ {S_{i,j}} = {S_j}od \;{q_i} $

(12)

则用户可得到 ${t_i}$ 个点 $({x_1},{S_{i,1}}),({x_2},{S_{i,2}}), \cdots ,({x_{{t_i}}},{S_{i,{t_i}}})$ ，利用Lagrange插值多项式重构秘密多项式：

$\begin{aligned}[b] {F_i}\left( x \right) &= F\left( x \right)od \;{q_i} = \\ &\;\;\;\;\;\;\;\sum\limits_{j = 1}^{{t_i}} {\left( {{S_{i,j}}\prod\limits_{h = 1,h \ne j}^{{t_i}} {\frac{{x - {x_h}}}{{{x_j} - {x_h}}}} } \right)} od \;{q_i} = \\ &\;\;\;\;{a_0} + {a_1}x + \cdots + {a_{{t_{{L_{\max }}}} - 1}}{x^{{t_{{L_{\max }}}} - 1}}od \;{q_i} = \\ &\;\;\;\;\;\;\;{a_0} + {a_1}x + \cdots + {a_{{r_{{L_i}}} - 1}}{x^{{r_{{L_i}}} - 1}} + \\ &\;\;\;\;\;{a_{{r_{{L_{\max }}}}}}{x^{{r_{{L_{\max }}}}}} + \cdots + {a_{{t_i} - 1}}{x^{{t_i} - 1}}od \;{q_i} \end{aligned} $

(13)

利用式（10）计算得出 ${F_i}\left( x \right)$ 的前 ${r_{{L_i}}}$ 个系数即可恢复出精度为 ${L_i}$ 级的位置坐标 ${G_{{L_i}}} = \left\{ {T_{{L_i},1}},{T_{{L_i},2}}, \cdots ,\right. {T_{{L_i},{r_{{L_i}}}}} \}$ 。

1.4 位置共享隐私保护方案

作者设计的多用户位置共享分级隐私保护方案的执行过程如图2所示。

${Q_o}$ 通过定位系统确定自身当前的准确位置 $G$ ，通过运行终端上的位置转换模型将 $G$ 转换为不同精度级别的位置数字表示 ${G_{{L_i}}}$ ，再利用多秘密共享份额生成算法将 ${G_{{L_1}}},{G_{{L_2}}}, \cdots ,{G_{{L_{\max }}}}$ 打包生成主份额 ${S_i}\left( {1 \le i \le n} \right)$ ，分发给 $s{p_1},s{p_2}, \cdots ,s{p_n}$ 存储管理。 ${C_A}$ 或 ${C_B}$ 对 ${Q_o}$ 进行好友查找位置共享时，相应数量的位置服务器会根据 ${Q_o}$ “好友列表”和各自的访问权限等级提供影子份额， ${C_A}$ 和 ${C_B}$ 即可重构出其对应精度级的 ${Q_o}$ 位置共享结果。具体步骤如下：

1） ${Q_o}$ 通过定位系统，获取自身位置坐标 $G$ 。

2） ${Q_o}$ 启用位置转换模型，根据自身隐私需求将位置转换为 $L{}_{\max }$ 个不同精度级的位置数据， $p\left( {G,{L_i}} \right)$ 表示G对应的L_i精度级的位置数据：

$\left\{ \begin{array}{l} {G_{{L_1}}} = p\left( {G,{L_1}} \right), \\ {G_{{L_2}}} = p\left( {G,{L_2}} \right), \\ \quad\quad\quad\vdots \\ {G_{L\max }} = p\left( {G,{L_{\max }}} \right) \\ \end{array} \right.$

(14)

3） ${Q_o}$ 利用位置信息共享机制将不同精度级别的位置数字坐标作为一组秘密进行转换分割，产生秘密份额并计算主份额 ${S_i}\left( {1 \le i \le n} \right)$ 。

4） ${Q_o}$ 将主份额 ${S_i}\left( {1 \le i \le n} \right)$ 发送给位置服务器集中 $n$ 个不同的位置服务器 $s{p_1},s{p_2}, \cdots ,s{p_n}$ ，位置服务器存储管理所得主份额，且最多只能获得一个主份额；每个位置服务器执行一个访问控制机制，用户的访问权限由 ${Q_o}$ 自行定义。

5）当 ${C_A}$ 查询共享 ${Q_o}$ 位置时，位置服务器会在 ${Q_o}$ 的“好友列表”中查询其对应的访问权限等级，假设 ${C_A}$ 被 ${Q_o}$ 允许获得的位置精度级别为 ${L_i}$ ，则 ${C_A}$ 可访问 ${t_i}$ 个位置服务器获得影子份额集。

6）被授权访问的 ${t_i}$ 个位置服务器根据存储的份额和 ${L_i}$ 计算其影子份额 ${S_{i,j}}$ ，发送给 ${C_A}$ 。

7） ${C_A}$ 收到影子份额后，执行秘密重构恢复出 ${G_{{L_i}}} = p\left( {G,{L_i}} \right)$ ，完成好友位置查找，共享得到精度级为 ${L_i}$ 的位置信息。

2 方案分析 2.1 安全性分析

在复杂的移动社交网络中，LBS应用中的隐私威胁主要在于不可信的 $sp$ 集和其他网络用户^[18]。 $sp$ 可能会在利益驱动下滥用或故意泄露其存储的位置信息，其他用户会伺机窥探推测他人的位置隐私，二者往往也会因自身安全漏洞将存储的位置信息及查询结果泄露给攻击者。

引　理 　本方案能够实现对 ${Q_o}$ 位置共享的分级隐私保护，并能抵抗：1）对单个位置服务器的攻击；2）数量少于 ${t_1}$ 的多个位置服务器合谋攻击；3）用户（ ${L_i}$ 级）与数量少于 ${t_{i + 1}}$ 的多个位置服务器合谋攻击；4） ${L_i}$ 级用户之间、 ${L_i}$ 级与 ${L_{i + 1}}$ 级用户之间的合谋攻击。

证明：

1）方案的正确性、可行性、有效性在文献[19]中利用多项式形式的中国剩余定理及数论中插值多项式唯一性定理已被详细证明，在此不再赘述。

2）对于任何访问结构，都存在实现该访问结构上完备的秘密共享方案^[20]，即满足任意授权子集都可以很容易地恢复出秘密，但任意的非授权子集都得不到关于秘密的任何信息。当 ${r_{{L_{\max }}}} > {t_1}$ 时， ${G_{{L_i}}}$ 对应的秘密多项式阶为 $\deg ({F_i}(x)) \le {r_{{L_{\max }}}} + {t_i} - {t_1} - 1$ ，至少需要 $({r_{{L_{\max }}}} + {t_i} - {t_1})$ 个点才能计算出 ${F_i}(x)$ ，而事先在发送主份额阶段公布了 $({r_{{L_{\max }}}} - {t_1})$ 个点 ${d_1},{d_2}, \cdots ,{d_{{r_{{L_{\max }}}} - {t_1}}}$ 的值。至少还需要 ${t_i}$ 个位置服务器的影子份额才能确定 ${F_i}(x)$ 以获得 ${G_{{L_i}}}$ ，少于 ${t_i}$ 个位置服务器的影子份额则无法确定 ${F_i}(x)$ ，也得不到关于所共享的多组秘密的任何信息，即满足Shamir门限方案安全性特点；同理，当 ${r_{{L_{\max }}}} \le {t_1}$ 时， ${G_{{L_i}}}$ 对应的秘密多项式阶为 $\deg ({F_i}(x)) \le {t_i} - 1$ ，因此，至少需要 ${t_i}$ 个位置服务器的影子份额才能确定 ${F_i}(x)$ 以获得 ${G_{{L_i}}}$ ，而少于 ${t_i}$ 个位置服务器的影子份额无法确定 ${F_i}(x)$ ，也得不到关于所共享的多组秘密的任何信息，这也满足Shamir门限方案安全性特点。因此，本方案同Shamir的门限方案一样是安全完备的。能够抵抗单个服务器攻击或低于最小门限值个数 ${t_1}$ 的服务器合谋攻击，位置服务器也无法通过其所掌握的份额对位置信息进行有用的推测。

3）用户与多个位置服务器的合谋攻击实质上是多个位置服务器合谋攻击的特殊情况^[12]。本方案中，即使对应位置精度级 ${L_i}$ 的用户联合门限访问结构的授权子集中 ${t_i}$ 个位置服务器的主份额计算出 ${G_{{L_1}}}, {G_{{L_2}}}, \cdots ,{G_{{L_{i - 1}}}}$ ，也并不影响系统的安全性，这相当于本身可获得更高精度位置结果的用户自然也能够获知精度更低的位置结果。因此，本方案能够抵抗用户与授权子集中 ${t_i}$ 个位置服务器的合谋攻击；进一步地，除了 $s{p_1},s{p_2}, \cdots ,s{p_{{t_i}}} $ 与用户合谋外，还需要属于 ${t_{i + 1}}$ 门限访问结构的授权子集中至少 $({t_{i + 1}} - {t_i})$ 个服务器与用户合谋，提供其计算出的影子份额才能重构出更高精度的位置结果 ${G_{{L_{i + 1}}}}$ ，这正说明本方案具有灵活分级隐私保护属性，即当更多服务器提供份额时能够提高重构位置信息的精度。综上所述，本方案能够抵抗 ${L_i}$ 级用户与少于 ${t_{i + 1}}$ 个数量的位置服务器合谋攻击。

4）假设用户 ${C_A}$ 、 ${C_B}$ 及 ${C_C}$ 合谋， ${C_A}$ 和 ${C_B}$ 都可计算出 ${G_{{L_i}}}$ ， ${C_C}$ 可计算出 ${G_{{L_i} + 1}}$ 。显然，由于 ${C_A}$ 和 ${C_B}$ 都能够利用 ${t_i}$ 个不同的份额计算确定出 ${G_{{L_i}}}$ 的多项式 ${F_i}\left( x \right)$ ，但根据 ${F_i}\left( x \right)$ 的唯一确定性，即使用多于 ${t_i}$ 个属于同一级别 ${G_{{L_i}}}$ 的影子份额，也只能确定出同一个多项式 ${F_i}\left( x \right)$ ，仍然只能得到 ${G_{{L_i}}}$ 。由于本方案中各精度级的位置信息的多项式是相互独立生成且具有唯一性，不会因合谋后份额增加得到关于 ${F_{i + 1}}\left( x \right)$ 及 ${G_{{L_i} + 1}}$ 的任何有用信息， ${C_A}$ 与 ${C_B}$ 合谋也不会得到新的关于 ${G_{{L_i} + 1}}$ 的有用信息。即使不与 ${C_A}$ 合谋， ${C_C}$ 本身也能够计算出 ${G_{{L_i} + 1}}$ ， ${C_A}$ 提供其拥有的影子份额也不会带来关于 ${G_{{L_i} + 2}}$ 及其相应多项式 ${F_{i + 2}}\left( x \right)$ 的任何有用信息。

本方案与文献[11-13]方案在是否需要可信sp集、应用对象范围、位置份额、抵抗攻击类型等方面的对比见表1。如表1所示，与同类方案相比，本方案可同时实现地理和语义位置共享的分级隐私保护、抵抗多种常见攻击，安全性高且不依赖于 $sp$ 集的可信度。

2.2 性能分析

本方案的运算主要分为3部分： ${Q_o}$ 端主要完成自身不同精度级别的位置坐标转换和利用基于中国剩余定理生成主份额的计算，位置服务器端主要负责生成影子份额的计算， ${C_*}$ 端主要通过拉格朗日插值公式计算重构出其对应级别的位置信息。下面以第1.2节中地理位置坐标为仿真对象，其中， ${G_{{L_1}}}$ 、 ${G_{{L_2}}}$ 、 ${G_{{L_3}}}$ 构成了 ${L_{\max }} = 3$ 组不同精度级别的位置信息，每组的秘密个数分别为 ${r_1} = 2$ ， ${r_2} = 4$ ， ${r_3} = 6$ ，分别对 ${Q_o}$ 、位置服务器和 ${C_*}$ 的终端进行仿真实验。实验环境是：64 bit的Windows 10操作系统，CPU为4210M的Intel core i5，内存为12 GB DDR3L，运行平台为Python 3.5，运行软件为PyCharm2018.2。

实验仿真结果中， $n$ 变化时的计算时间对数坐标见图3。如图3所示，各位置服务器及 ${Q_o}$ 、 ${C_*}$ 端的计算开销小， ${Q_o}$ 端计算开销保持在10^–4～10^–3 s级之间， ${C_*}$ 端计算开销保持在10^–1～1 s级之间，位置服务器端计算开销保持在10～10^–4 s级之间。且 ${C_*}$ 端、各服务器的计算时间并未因 $n$ 增加而剧增， ${Q_o}$ 的计算时间发生了10^–3 s级的线性变化。

${t_3}$ 变化时的计算时间对数坐标见图4。如图4所示，最高精度位置信息恢复门限值 ${t_3}\left( {{t_3} \ge {t_2} \ge{t_1}} \right)$ 增加时，各位置服务器及 ${Q_o}$ 端的计算时间并未因 ${t_3}$ 增加而显著增加， ${C_*}$ 端的计算时间发生了秒级增加。

${t_1}$ 变化时的计算时间对数坐标见图5。如图5所示，最低精度位置信息恢复门限值 ${t_1}\left( {{t_3} \ge{t_2} \ge {t_1}} \right)$ 增加， ${Q_o}$ 端、各位置服务器及 ${C_*}$ 端的计算时间均未显著增加。

${t_2}$ 变化时的计算时间对数坐标见图6。如图6所示，当中间精度位置信息恢复门限值 ${t_2}$ 增加时， ${Q_o}$ 端、各位置服务器的计算时间并未显著增加，C_*端计算时间发生了秒级增加。

本方案与文献[11-13]方案在运行时间上的对比见表2。如表2所示，即使在加入对大素数的素性判定与选取运算、未采用中国剩余定理快速算法的最坏情况下，本方案的效率相对于同类方案的效率仍然更高，实现简单，计算量小，性能更加稳定。

这主要是由于本方案将多个不同精度级别的位置信息打包成一个整体，在 $({t_i},n)$ 的门限访问结构上分别共享 ${L_{\max }}$ 组不同精度位置信息 ${G_{{L_1}}},{G_{{L_2}}}, \cdots ,{G_{{L_{\max }}}}$ ，分发过程只需通过中国剩余定理构造一个 $({r_{{L_{\max }}}} + {t_{{L_{\max }}}} - {t_1} - 1)$ 阶（ ${r_{{L_{\max }}}} \le {t_1}$ 时）或 $({t_{{L_{\max }}}} - 1)$ 阶（ ${r_{{L_{\max }}}} > {t_1}$ 时）拉格朗日多项式，即仅需要一个逻辑步骤和一次秘密分发过程，就可共享 ${L_{\max }}$ 组不同精度的位置信息。而其他方案中共享多组位置信息就需要进行多次秘密分发、重复计算量大的情况，相比而言，本方案计算量更小。 ${Q_o}$ 端的计算复杂度为 $o\left( {{r_{{L_{\max }}}}\log\;{r_{{L_{\max }}}}} \right)$ ， ${L_i}$ 级用户端的计算复杂度为 $o\left( {{{\left( {{r_{{L_{\max }}}} + {t_i} - {t_1} - 1} \right)}^2}} \right)$ （ ${r_{{L_{\max }}}} > {t_1}$ 时）或 $o\left( {{{\left( {{t_i} - 1} \right)}^2}} \right)$ （ ${r_{{L_{\max }}}} \le {t_1}$ 时），服务器端的计算量为 ${t_i}$ 次整数取模运算。并且，只要参数值在合理范围内变大时，本方案增加的计算开销可忽略不计，即不会发生剧增。实质上，基于中国剩余定理的同余类秘密共享门限方案早已被证明比Shamir的方案更加高效^[21]，因此，本方案比同类Shamir方案更高效。

若一定时间内 ${Q_o}$ 位置变化不大，仅仅是 ${G_{{L_{\max }}}}$ 发生变化而其他更低精度的数字坐标不变时，更新份额仅需对式（1）中最后几组同余方程组进行重新求解即可，而不需要重新执行整个秘密共享份额生成算法，进一步节省了计算量，提高了方案效率。此外，本方案的公共信息量仅为 ${L_{\max }}$ 或 $({r_{{L_{\max }}}} - {t_1} + {L_{\max }})$ 个，在同类方案中信息量较小。

3 结　论

相对于传统“全部或全不”的刚性位置隐私保护策略，弹性的分级隐私保护策略更加符合移动互联网中用户的个性化需求。本方案通过地理和语义位置转换模型保证用户能够灵活地自定义其共享位置的精度级别及可访问对象，并利用基于中国剩余定理的门限可变多秘密共享方法，将定义的多精度级的位置信息作为整体打包转换分割，实现了一次份额分发就能使不同共享对象重构出不同精度的位置信息，在不可信环境下完成了多用户位置共享的弹性隐私保护。仿真实验分析进一步表明，本方案计算复杂度低，通信开销小，鲁棒性好，与同类方案相比更为高效，即使在网络资源受限的环境中和计算能力受限的用户终端上也同样适用。此外，本方案除可应用于好友查找等基于位置共享的社交服务场景外，也可扩展使用至军队信息化层级指挥作战系统，在基于位置共享的群组协同作战领域有着广阔的应用前景。