1. 多角度个性化的本地差分隐私

1 .多角度个性化的本地差分隐私： 问题与挑战 朱友文 zhuyw@nuaa.edu.cn 2021.9 

2 . 目 录 •本地差分隐私(LDP)简介 •多角度个性化隐私保护需求 •现有个性化LDP机制分析 •总结 

3 . 目 录 •本地差分隐私(LDP)简介 •多角度个性化隐私保护需求 •现有个性化LDP机制分析 •总结 

4 .本地差分隐私简介 Ø 隐私泄漏事件层出不穷，受到危害影响的人越 来越多 Ø 国内外相关法律法规的陆续出台 Ø 隐私计算（隐私保护计算、隐私增强计算）： 数据隐私保护需求与数据可用性之间的矛盾 

5 .本地差分隐私简介：隐私保护的两种场景 Ø 终端用户隐私数据采集 Ø 隐私数据集跨系统发布/共享 服务器 隐私数据发布/ 联合隐私计算 用户 

6 . 本地差分隐私简介：差分隐私与本地差分隐私 Traditional Differential Privacy（差分隐私） d1 +noise d2 … 模块 dn 数据服务器 可信的 [1] C. Dwork, K. Kenthapadi, F.McSherry, I.Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486–503, 2006. 

7 . 本地差分隐私简介：差分隐私与本地差分隐私 用户本地扰动 Local Differential Privacy（本地差分隐私, 简称LDP） d1 LDP d1’ ′ d2 LDP d2’ ’ … … ′ dn LDP dn’ 用户 数据服务器 可以是恶意的 [2] S. Kasiviswanathan, H. Lee, et al, What can we learn privately?, SIAM Journal on Computing, 40(3): 793–826, 2011. [3] S. Kasiviswanathan, H. Lee, et al. What can we learn privately? FOCS, 2008. 

8 . 本地差分隐私简介 • 定义（ɛ-本地化差分隐私, ɛ-local differential privacy , ɛ-LDP） 算法 : → 是ɛ-本地化差分隐私的（ɛ≥0）当且仅当 对于任意两个输入 , ∈ , 任意输出 ∈ ，满足 = ≤ ∗ = 其中Pr[·]表示事件发生的概率. ɛ-本地差分隐私（ ɛ-LDP） Ø ɛ 衡量了隐私损失的程度； ɛ 越小，隐私损失越小 Ø ɛ 被称为“隐私预算”（privacy budget） 

9 . 本地差分隐私简介 松散的形式: (Ɛ, δ)-本地差分隐私 = ≤ ∗ = + 0≤δ < 1，一般不超过10^{-4} 

10 . 本地差分隐私简介 • 定义（ɛ-本地差分隐私, ɛ-local differential privacy, ɛ-LDP） 算法 : → 是满足ɛ-本地差分隐私（ɛ≥0）当且仅当 对于任意两个输入 , ∈ , 任意输出 ∈ ，满足以下公式 = ≤ ∗ = 其中Pr[·]表示事件发生的概率. 组合特性 已知存在 个满足ɛ −LDP的随机算法 ， ∈ {1, …, }，数据D经S 个随机 算法处理之后的输出结果序列： , …, ，满足 =1 ɛ −LDP 

11 .本地差分隐私简介 Ɛ-本地差分隐私机制主要包含两个模块： 每个用户单独完成 Ø 编码+扰动: xi = Encode(di) di’ = Perturb(xi) 服务器完成 Ø 聚合+后处理： (d1, d2,…, dn) = Aggregate(d1’, d2’,…, dn’) 

12 . 本地差分隐私简介：二值频率估计 二值频数统计 随机响应(Randomised Response, RR) • 被调查者可能被问到隐私问题，如：“你是否曾经考试作弊？” • 被调查者回复: ‘是’ / ‘否’; Server希望得到真实回答为‘是’的比例 ρ [4] S. L. Warner, Randomized response: a survey technique for eliminating evasive answer bias, Journal of the American Statistical Association, 1965 [5] N. Holohan, D. Leith, O. Mason. Optimal Differentially Private Mechanisms for Randomised Response. IEEE TIFS, 2017. 

13 . 本地差分隐私简介：二值频率估计 二值频数统计 随机响应(Randomised Response, RR) Ø编码: 真实回复表示为 ∈ {1, 0}, 其中Ai=1表示 ‘是’, =0表示‘否’ , 以 的概率 Ø扰动: 提交的回复 = 1− , 以1 − 的概率 p 是 1 1 是 作弊与否 1-p 否 0 0 否 p 真实 实际 答案 回答 

14 . 本地差分隐私简介：二值频率估计 随机响应(Randomised Response, RR) • 被调查者可能被问到隐私问题，如：“你是否曾经考试作弊？” • 被调查者回复: ‘是’ / ‘否’; Collector希望得到真实回答为‘是’的比例 ρ Ø编码: 真实回答表示为 ∈ {1, 0}, 其中Ai=1表示 ‘是’, Ai=0表示‘否’ , 以 的概率 概率p是公开的参数 Ø扰动: 提交的回复 = 1− , 以1 − 的概率 如果 ≤ 1− ≤ ，那么上述RR扰动满足ɛ-本地差分隐私 = +1 

15 .本地差分隐私简介：二值频率估计 假设真实回答为“是”的比例： 实际回答为“是”的比例为： −1 = + 1− 1− = + 2 −1 2 −1 的无偏估计 

16 . 本地差分隐私简介 Ø 多值频数统计/直方图估计：k-RR、RAPPOR、子集选择、 Wheel、…… Ø Heavy hitter查找：LDPMiner、Wheel、PEM、…… Ø 连续数据的分布估计：SW with EMS/EM、…… Ø 均值估计：SR、PM、…… Ø Key-Value数据：PrivKV、PCKV、PriKVM*、…… Ø …… 

17 . 本地差分隐私简介 Local Differential Privacy（本地差分隐私） d1 LDP d1’ ′ d2 LDP … d2’ ’ … ′ dn LDP dn’ 用户 数据服务器 Ø LDP模型的问题与不足：准确度？、输入造假、每个数据等同对待、…… 

18 . 目 录 •本地差分隐私(LDP)简介 •多角度个性化隐私保护需求 •现有个性化LDP机制分析 •总结 

19 . 多角度个性化的隐私保护需求 Ø 视角1：不同用户的隐私保护关切程度存在差异 服务器 • 不同文化背景 • 不同宗教 • 不同年龄段 • 不同性别 • …… 用户 

20 . 多角度个性化的隐私保护需求 Ø 视角2：数据取值范围内不同数值的敏感度存在差异 作弊与否 否 是 疾病 HIV 胃炎 脂肪肝 高血压 …… 购物订单 牙膏 牙刷 零食 药品 成人用品 …… 第1个孩子的出生时间 婚前 婚后9个月内 婚后9个月后 位置 X学校 X商场 X餐馆 X酒店 X酒吧 …… 

21 . 多角度个性化的隐私保护需求 Ø 视角3：对于多维数据，不同维度的敏感度存在差异 （ 出生年份 出生月份 民族 籍贯 出生地 性别 职业 ） （ 购物平台 购物时间 IP地址 物品名称 金额 物品数量 …… ） 

22 . 多角度个性化的隐私保护需求 Ø 多角度：“用户-取值-属性”多角度隐私敏感度差异 用户A位置 X学校 X商场 X餐 X酒店 X酒吧 X小区 X大厦 …… 馆 用户B位置 X商场 X餐馆 X酒店 X酒吧 Y小区 X写字楼 …… 

23 . 多角度个性化的隐私保护需求 Ø 多角度：“用户-取值-属性”多角度隐私敏感度差异 第1个孩子的出生时间 婚前 婚后9个月内 婚后9个月后 用户1 m11 m12 m13 用户2 m21 m22 m23 … … … … 用户n mn1 mn2 mn3 隐私敏感度 

24 . 目 录 •本地差分隐私(LDP)简介 •多角度个性化隐私保护需求 •现有个性化LDP机制分析 •总结 

25 . 现有的个性化LDP机制分析 Ø 视角1：不同用户的隐私保护关切程度存在差异 ɛ3 数据 服务器 使用者 类别型数据频率估计. 主要思路： ɛ1 ɛ5 每个隐私层级用户，分别完成估计 ɛ6 ɛ2 不同层级的估计结果最优化组合 ɛ1 用户 数据重用机制（二次扰动） [6] Y. Nie, et al. A Utility-optimized Framework for Personalized Private Histogram Estimation, IEEE Trans. on Knowledge and Data Engineering, 2019. 

26 . 现有的个性化LDP机制分析 Ø 视角1：不同用户的隐私保护关切程度存在差异 (ɛi , τi)- LDP模型下的均值估计 服务器 主要思路 ɛ5 , τ1 ɛ1, τ1 每个用户任意选择隐私预算和隐私 区域 ɛ6 , τ1 ɛ1 , τ1 ɛ2 , τ1 先平移隐私区域，再进行扰动处理 用户 每个用户单独估计，然后再组合 [7] Q. Xue, et al. Mean Estimation over Numeric Data with Personalized Local Differential Privacy, Frontiers of Computer Science, 2021. 

27 . 现有的个性化LDP机制分析 Ø 视角2：数据取值范围内不同数值的敏感度存在差异 如果用户的真实答案为“是”， 真实 实际 总是回答“是” 答案 回答 如果用户的真实答案为“否”， 是 1 1 是 以p的概率回答“是”，以1-p的 作弊与否 p 概率回答“否” 否 0 0 否 实际回答“否”的，真实答案就 1-p 是“否” 相对RR，可以提高估算准确度 [8] N. S. Mangat. An improved randomized response strategy, Journal of the Royal Statistical Society: Series B (Methodological), 1994. 

28 . 现有的个性化LDP机制分析 Ø 视角2：数据取值范围内不同数值的敏感度存在差异 ULDP 真实值 提交值 1. Y 仅会泄漏 X 的信息； I N 敏 2. 对于任意两个输入 , ∈ （这里 感 隐 XS 值 私 Y = ∪ ），任意输出 ∈ ，满足 区 值 P 域 = ≤ ∗ = 域 非 无法区分两个敏感输入； 可 敏 逆 Y 无法区分敏感输入和非敏感输入（不 XN 感 值 I 会泄漏敏感输入的“敏感属性”）； 区 域 域 可以利用非敏感区域提高估计准确度 [9] T. Murakami, et al. Utility-Optimized Local Differential Privacy Mechanisms for Distribution Estimation, USENIX Security Symposium, 2019. 

29 . 现有的个性化LDP机制分析 Ø 视角2：数据取值范围内不同数值的敏感度存在差异 ID-LDP Ø输入域的每个值di有特定的隐私预算要求ɛi ≥0. Ø算法 : → 是满足Ɛ-ID-LDP（即Input-Discriminative LDP, 其中 Ɛ={ɛi | ∈ }）当且仅当，对于任意两个输入 , ∈ ，任意输出 ∈ ，满足 = ≤ ɛ ,ɛ ∗ = Ø当 ɛ ,ɛ =min{ɛ , ɛ }时，称为 min-ID-LDP [10] X. Gu, et al. Providing Input-Discriminative Protection for Local Differential Privacy, ICDE, 2020.