差分隱私定義

差分隱私定義了一種機制的“隱私” $ A $ 作為兩個分佈的“接近度” $ Pr[A(D) \in S] $ 和 $ Pr[A(D’) \in S] $ 在哪裡 $ D,D’ $ 在一個元素上有所不同。並且這些分佈之間的距離是相乘的，即

$ \left| \frac{Pr[A(D) \in S]}{Pr[A(D’) \in S]} \right| \leq e^\epsilon $

我很難理解這種乘法距離測量的選擇，而不是密碼學（不可區分性）中的標準距離（統計差異），即

$ |Pr[A(D) \in S] - Pr[A(D’) \in S]| \leq neg(.) $

Dwork 等人的論文*“Calibrating Noise to Sensitivity in Private Data Analysis”*。提出使用乘法距離的兩個原因：

1. 它更嚴格，因為如果一個機率為 0，則另一個機率也必須為 0（使用統計差異的標準度量時不能保證）。這個，我明白了。
2. 對於機制的效用，洩漏（分佈之間的距離）必須是**不可忽略的。**這我真的很難理解。誰能舉個簡單的例子來說明這一點，好嗎？

我不能舉一個例子來說明為什麼洩漏對於機構的效用必須是不可忽略的，但我可以證明為什麼洩漏對於機構的效用必須是不可忽略的。

讓 $ ;; U : = : \left{\langle D,D’\rangle : D,D’ \text{ differ in one element}\right} ;;; $ .

由三角不等式，對於所有 $ D $ 和 $ D’ $ ， 對全部 $ S $ ,

$ |\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D’) \in S)| $

$ \leq $

number_of_elements $ \cdot \operatorname{sup}({|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D’) \in S)| : \langle D,D’\rangle \in U} $

如果 number_of_elements 是多項式並且 $ :\operatorname{sup}({|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D’) \in S)| : \langle D,D’\rangle \in U}): $ 可以忽略不計，那麼

對於所有人 $ D $ 和 $ D’ $ ， 對全部 $ S $ , $ :|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D’) \in S)|: $ 可以忽略不計。

如果 number_of_elements 是多項式並且

$ \operatorname{sup}({|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D’) \in S)| : \langle D,D’\rangle \in U}) $

可以忽略不計，那麼 $ A $ 在統計上接近於獨立於 $ D $ .

因此，如果 $ :\operatorname{sup}({|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D’) \in S)| : \langle D,D’\rangle \in U}) $

可以忽略不計，則該機制無用。

引用自：https://crypto.stackexchange.com/questions/8679