差分隐私总览--The Overview of Differential Privacy

逃离我推掉我的手 2023-07-25 11:19 61阅读 0赞

1.安全计算. 1

1.1 基于噪声的方法. 1

1.2 非噪声方法. 2

1.3 K-匿名化算法. 2

2. 差分隐私. 3

1.1 定义. 3

2.2 噪声机制. 6

2.2.1 基础知识介绍. 6

2.2.2 三种分布. 7

2.2.3 Laplace mechanism 8

2.2.4 Gaussian mechanism 9

2.2.5 Exponential Mechanism 12

2.2.6 random response 13

2.3 交互式数据发布. 14

2.3.1 场景差分隐私. 15

2.4 非交互式数据发布. 16

#  #

# **1.安全计算** #

实现安全计算的方法: 一类是基于噪音的，另一类不是基于噪音的。

## **1.1 基于噪声的方法** ##

基于噪音的安全计算方法，最主要代表是目前很火的差分隐私（differential privacy）。这类方法的思想是，对计算过程用噪音干扰，让原始数据淹没在噪音中，使别有用心者无法从得到的结果反推原始数据。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70][]

这种方法的优点是效率高（毕竟只需要生成服从特定分布的随机数即可），缺点是最后得到的结果不够准确，而且在复杂的计算任务中结果会和无噪音的结果相差很大导致结果无法使用。

## **1.2 非噪声方法** ##

非噪音方法一般是通过密码学方法将数据编码或加密。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 1][]

## **1.3 K-匿名化算法** ##

To avoid linkage attack

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 3][]

# **2. 差分隐私** #

A privacy mechanism must be able to protect individual’s privacy from attackers who may possess background knowledge.

## **1.1 定义** ##

![20200414175331972.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 6][]

**敏感度（sensitivity):**

差分隐私保护可以通过在查询函数的返回值中加入噪声来实现，但是噪声的大小同样会影响数据的安全性和可用性。通常使用**敏感性作为噪声量大小的参数**，表示删除数据集中某一记录对查询结果造成的影响。**敏感度分为全局敏感度和局部敏感度，通常情况下采用全局敏感度会加入过大的噪音，使数据失真，但若使用局部敏感度，在一定程度上就会泄露数据分布信息，这个时候就有了平滑敏感度**

**隐私保护预算**

从差分隐私保护的定义可知，隐私保护预算ε用于控制算法M在邻近数据集上获得相同输出的概率比值，反映了算法M所的隐私保护水平，ε越小，隐私保护水平越高。在极端情况下，当ε取值为0时，即表示算法M针对D与D’的输出的概率分布完全相同，由于D与D’为邻近数据集，根据数学归纳法可以很显然地得出结论，即当ε=0时，算法M的输出结果不能反映任何关于数据集的有用的信息。因此，从另一方面，ε的取值同时也反映了数据的可用性，在相同情况下，ε越小，数据可用性越低。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 7][]

## **2.2 噪声机制** ##

### **2.2.1 基础知识介绍** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 9][]

### **2.2.2 三种分布** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 10][]

### **2.2.3 Laplace Mechanism** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 11][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 12][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 13][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 14][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 15][]

### **2.2.4 Gaussian mechanism** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 14][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 16][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 17][]

问题转化为

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 18][]

![2020041417533238.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 19][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 20][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 21][]

### **2.2.5 Exponential Mechanism** ###

For functions that do not return a real number：“what is the most common nationality in this room”: Chinese/Indian/American…

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 22][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 23][]

第一项

![20200414175331481.png][]

第二项

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 24][]

### **2.2.6 random response** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 25][]

**2.2.7****可用性评估**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 26][]

## **2.3 交互式数据发布** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 27][]

![2020041417533287.png][]

### **2.3.1 场景差分隐私** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 28][]

![20200414175331979.png][]

![20200414175331878.png][]

## **2.4 非交互式数据发布** ##

![20200414175331950.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 29][]

![20200414175332166.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 30][]

更多深入学习差分隐私在我的github：[https://github.com/Billy1900/Awesome-Differential-Privacy][https_github.com_Billy1900_Awesome-Differential-Privacy]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70]: /images/20230528/1dc83144a4d1464f84b263392fb5ca16.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 1]: /images/20230528/bac7e2f1d514497bbb6cdc4e575cb425.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 2]: /images/20230528/5de9c2e5a8b64979aa18df574ca8d1eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 3]: /images/20230528/3582316c18bd42449ca713e74ecce8f9.png
[20200414175331972.png]: /images/20230528/0ff25e24705945c9829234e9761864d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 4]: /images/20230528/71d0fd8bf1714af6a2edfbf36bb3e8d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 5]: /images/20230528/dce52245167e43759c8adae2d12f1185.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 6]: /images/20230528/742a4bcb0ad24eed89a7bc456fcfc7eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 7]: /images/20230528/5e77cbe460034a219052033005cb9b05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 8]: /images/20230528/a2d20f71ff304d039961c5b4c30c20ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 9]: /images/20230528/fdc7b91e3e6140308dbcb50920f840f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 10]: /images/20230528/4fda9b6891e54f979837c6a741668228.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 11]: /images/20230528/a27b3758d95c477898c80b17a3a5c038.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 12]: /images/20230528/a580746acd034c4dbdec3bb6ac5a3d44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 13]: /images/20230528/fa7282955e974446b28e50d77a3c311c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 14]: /images/20230528/d3338292a7264f0b9e7f526fd4045fe5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 15]: /images/20230528/eaf68f52317747cf81e576d6529078f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 16]: /images/20230528/d33ddda126764d55928175a2dac5dc80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 17]: /images/20230528/b9e01155107649358cf2516945ea5374.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 18]: /images/20230528/01dfd423eccf4f2c9bb5106519a63fc3.png
[2020041417533238.png]: /images/20230528/00ee283974ad48d6bb1020d3e2ab77b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 19]: /images/20230528/3bd8145c537041e7a7327d770c20f70f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 20]: /images/20230528/4a5310ae4edf474fb405ac0c660d447c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 21]: /images/20230528/b403dd8c44a748d59b231a42dc50ec45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 22]: /images/20230528/d7866444e7e94b8bb3d011f7cce8fedf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 23]: /images/20230528/4eb94b917d78491c80e6aa45494145fb.png
[20200414175331481.png]: /images/20230528/1f6c51f94e9045688457396af1f81aa6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 24]: /images/20230528/e7b055a05897466bbf74ad8861121611.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 25]: /images/20230528/d3b70e8ec75047978519828c0ff2220e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 26]: /images/20230528/d5b20cfbfb6f4eb1a4ece6aabaa2de11.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 27]: /images/20230528/4d35bff750bc4dcf9899f7b2b7af1081.png
[2020041417533287.png]: /images/20230528/14617282ab2642e0a81a8b6560507404.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 28]: /images/20230528/e3f79d3f3fda478aa4401bfd2f1e5dae.png
[20200414175331979.png]: /images/20230528/ea3415dc4bf1410c8688b5f8ff22741f.png
[20200414175331878.png]: /images/20230528/168d84a7d05b43bc807e9f0c61d773a4.png
[20200414175331950.png]: /images/20230528/2e81d7234ec741f3b0886bc473d5824f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 29]: /images/20230528/eda5026c4dd7461da29f8d0df55a63b3.png
[20200414175332166.png]: /images/20230528/3fb22990dfbe4058a52c955eb372072d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JpbGx5MTkwMA_size_16_color_FFFFFF_t_70 30]: /images/20230528/9b4d62ac487a49329a2fad610c5a4d8c.png
[https_github.com_Billy1900_Awesome-Differential-Privacy]: https://github.com/Billy1900/Awesome-Differential-Privacy