L-SRR Local Differential Privacy for Location-Based Services with Staircase Randomized Response
PDF: [2209.15091] L-SRR: Local Differential Privacy for Location-Based Services with Staircase Randomized Response, 代码：hwangcsiit/Location-Local-Differential-Privacy
Backgroud and Motivation
基于位置的服务（LBS）广泛应用，但 local differential privacy， 作为一种强大的隐私模型，由于现存的 LDP 机制效用不高，无法应用到 LBS 中。
Contribution
第一个提出 LDP 框架 L-SRR for 各样的 LBS 应用，可以高效地隐私地收集和分析用户位置。
设计了新的随机响应机制，阶梯随机响应，Staircase Randomized Response, 并扩展了 empirical estimation，以提高 SRR 在不同 LBS 应用中的效用（例如交通密度估计，k-最近邻）。
Randomized Response (RR) based schemes, such as generalized randomized response (GRR) and unary encoding (UE). However, only two different perturbation probabilities are defined in the existing LDP mechanisms (e.g., GRR, UE, and HR), not sufficiently fine-grained to optimize the utility (since the perturbation probabilities simply treat all the other output locations in the domain equally). 因此提出 Staircase Randomized Response (SRR)
Intuition: if the probabilities for locations that are closer to the input location 𝑥 can be higher, it is more possible for users that the query results of the LBS are the same. To this end, SRR will first consider the location distances to the input location 𝑥.
具体实现：
Hierarchical Location Encoding. To encode the location data, we use a hierarchical encoding scheme based on the Bing Map Tiles System
Location Groups
With hierarchical encoding for the location domain D, the distance between any two locations \(x,x^{'} \in D\) can be directly measured by the longest common prefixes (LCP) of their encoded bit strings.
Define the LCP of the group (GLCP): the shortest LCP between the input location 𝑥 and \(\forall y \in G_j(x)\)
Then, we can partition all the output locations into groups using the GLCP lengths
Location Partitioning
partition the locations into \(m\) groups for each input \(x \in D\), and assign the same perturbation probability to all the locations in the same group.
\[ \begin{equation} \mathrm{SRR}: \forall x \in \mathcal{D}, q(y \mid x)=\left\{\begin{array}{ccc} \alpha_1(x), & \text { if } y \in G_1(x) \\ \vdots & \vdots \\ \alpha_m(x), & \text { if } y \in G_m(x) \end{array}\right. \end{equation} \]
since SRR discretizes the perturbation probabilities for all the grouped possible output locations, the PDF of SRR has a similar shape to the staircase mechanism in differential privacy, which also has a staircase PDF for different groups to satisfy 𝜖-DP. That's the reason why the paper name our new randomization mechanism as the “Staircase Randomized Response” (SRR) in local differential privacy.
offline computation
Offline Computation. Since the optimization and partitioning are solely based on the domain D, they can be executed offline and periodically updated with D by the server in L-SRR.
通过在 LBS 应用中与其他 LDP 机制对比，证明了在 LBS 场景应用中，L-SRR 的效用优于现有的 LDP 机制。
