【中文翻譯】第9章-The Algorithmic Foundations of Differential Privacy

由于GitHub項目僅翻譯到前5章，我們從第6章開始通過大語言模型翻譯，并導出markdown格式。
大模型難免存在錯漏，請讀者指正。

教材原文地址：https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf

在這里插入圖片描述

9 差分隱私與計算復雜度

到目前為止，我們對差分隱私的討論忽略了計算復雜度問題，允許數據管理者和攻擊者的計算能力不受限制。實際上，數據管理者和攻擊者的計算能力可能都是受限的。

將我們自己限制在計算能力受限的數據管理者范圍內，會限制數據管理者的操作，使得實現差分隱私變得更加困難。實際上，我們將展示一類計數查詢的示例，在標準的復雜度理論假設下，即使已知低效算法，如SmallDB和私有乘法權重算法，也無法高效生成合成數據庫。大致來說，數據庫行是數字簽名，使用數據管理者無法訪問的密鑰進行簽名。直觀地說，合成數據庫中的任何一行要么是從原始數據庫復制而來（違反隱私），要么必須是對新消息的簽名，即偽造簽名（違反數字簽名方案的不可偽造性）。不幸的是，這種情況并不局限于基于數字簽名的（可能是人為構造的）示例：即使創建一個能保持相對準確的雙向邊際的合成數據庫也很困難。從積極的方面來看，給定一組 $\mathcal{Q}$ 查詢和一個從全域 $\mathcal{X}$ 中抽取行的 $n$ 行數據庫，可以在關于 $n,\left| \mathcal{X}\right|$ 和 $\left| \mathcal{Q}\right|$ 的多項式時間內生成一個合成數據庫。

如果我們放棄合成數據庫的目標，滿足于一種數據結構，從中我們可以獲得每個查詢答案的相對準確近似值，那么情況會有趣得多。事實證明，這個問題與追蹤叛徒問題密切相關，在追蹤叛徒問題中，目標是在向付費客戶分發數字內容的同時阻止盜版。

如果對手被限制在多項式時間內，那么實現差分隱私就會變得更容易。事實上，安全函數評估這一極其強大的概念提供了一種自然的方法來避免使用可信的數據管理者（同時比隨機響應方法具有更高的準確性），也提供了一種自然的方法來允許多個出于法律原因不能共享其數據集的可信數據管理者，對實際上是合并后的數據集進行查詢響應。簡而言之，安全函數評估是一種密碼學原語，它允許一組 $n$ 個參與方 ${p}_{1},{p}_{2},\ldots ,{p}_{n}$ （其中故障參與方的比例小于某個固定分數，該分數根據故障類型而異；對于“誠實但好奇”的故障，該分數為 1）合作計算任何函數 $f\left( {{x}_{1},\ldots ,{x}_{n}}\right)$ ，其中 ${x}_{i}$ 是參與方 ${p}_{i}$ 的輸入或值，以這樣一種方式進行計算，即任何故障參與方聯盟都無法破壞計算過程，也無法了解非故障參與方的值，除非這些值可以從函數輸出和聯盟成員的值中推導出來。這兩個屬性傳統上被稱為正確性和隱私性。這種隱私概念，我們稱之為安全函數評估隱私（SFE 隱私），與差分隱私有很大不同。設 $V$ 是故障參與方持有的值的集合，設 ${p}_{i}$ 是一個非故障參與方。如果 ${x}_{i}$ 可以從 $\cup \left\{ {f\left( {{x}_{1},\ldots ,{x}_{n}}\right) }\right\}$ 中推導出來，SFE 隱私允許故障參與方了解 ${x}_{i}$ ；因此，差分隱私不允許精確發布 $f\left( {{x}_{1},\ldots ,{x}_{n}}\right)$ 。然而，用于計算函數 $f$ 的安全函數評估協議可以很容易地修改為 $f$ 的差分隱私協議，只需定義一個新函數 $g$ ，它是在 $f$ 的值上添加拉普拉斯噪聲 $\operatorname{Lap}\left( {{\Delta f}/\varepsilon }\right)$ 的結果。原則上，安全函數評估允許對 $g$ 進行評估。由于 $g$ 是差分隱私的，并且將 SFE 隱私屬性應用于 $g$ 時表明，除了從 $g\left( {{x}_{1},\ldots ,{x}_{n}}\right)$ 的值和 $V$ 中可以了解到的信息之外，無法了解到關于輸入的任何其他信息，因此，只要故障參與者被限制在多項式時間內，就可以確保差分隱私。因此，安全函數評估允許在不使用可信數據管理者的情況下實現差分隱私的計算概念，并且與使用可信數據管理者時所能達到的準確性相比沒有損失。特別是，在確保計算差分隱私的同時，可以以恒定的預期誤差回答計數查詢，而無需可信數據管理者。我們將看到，在不使用密碼學的情況下，誤差必須為 $\Omega \left( {n}^{1/2}\right)$ ，這證明了在多方情況下，計算假設確實可以提高準確性。

${}^{1}$ 回想一下，雙向邊際是指對于每一對屬性值，數據庫中具有該屬性值對的行數的計數。

${}^{2}$ 在“誠實但好奇”的情況下，我們可以為任何參與方 ${P}_{j}$ 設定 $\left\{ {x}_{j}\right\}$ 。

9.1 多項式時間的數據管理者

在本節中，我們表明，在標準的密碼學假設下，要創建一個合成數據庫，使其能夠對適當選擇的一類計數查詢給出準確答案，同時確保哪怕是最基本的隱私概念，在計算上也是困難的。

這一結果有幾個擴展；例如，查詢集較小（但數據域仍然很大）的情況，以及數據域較小（但查詢集很大）的情況。此外，對于某些自然的查詢族，如對應于合取的查詢族，也得到了類似的負面結果。

我們將使用“合成（syntheticize）”這一術語來表示以保護隱私的方式生成合成數據庫的過程 ${}^{3}$ 。因此，本節的結果涉及合成過程的計算難度。我們所定義的隱私概念將遠弱于差分隱私，因此合成的難度意味著以差分隱私的方式生成合成數據庫也具有難度。具體而言，如果即使避免完整泄露輸入項都很困難，我們就稱合成是困難的。也就是說，總會有某些項完全暴露。

${}^{3}$ 在第6節中，合成器的輸入是一個概要；這里我們從一個數據庫開始，它是一個簡單的概要。

請注意，如果相反，泄露少量輸入項不被視為隱私泄露，那么通過發布輸入項的一個隨機子集就可以輕松實現合成。這個“合成數據庫”的實用性來自采樣邊界：在很大概率上，即使對于大量計數查詢，這個子集也能保留實用性。

在引入復雜性假設時，我們需要一個安全參數來表示大小；例如，集合的大小、消息的長度、解密密鑰的比特數等等，以及表示計算難度。安全參數用 $\kappa$ 表示，代表“合理”的大小和工作量。例如，假設對一個大小為安全參數的（任意固定）多項式的集合進行窮舉搜索是可行的。

計算復雜性是一個漸近概念——我們關注的是隨著對象（數據全域、數據庫、查詢族）的大小增長，任務的難度如何增加。因此，例如，我們不僅需要考慮單一大小數據庫的分布（在本專著的其余部分我們稱之為 $n$ ），還需要考慮由安全參數索引的分布族。與此相關，當我們引入復雜性時，我們傾向于“弱化”斷言：偽造簽名并非不可能——也許會有運氣！相反，我們假設沒有高效算法能以不可忽略的概率成功，其中“高效”和“不可忽略”是根據安全參數定義的。在我們的直觀討論中，我們將忽略這些細節，但在正式的定理陳述中會保留它們。

非正式地說，如果對于任何高效的（所謂的）合成器，從該分布中抽取的數據庫在很大概率上，至少有一個數據庫項可以從所謂的合成器的輸出中提取出來，那么數據庫的一個分布就很難合成（相對于某個查詢族 $\mathcal{Q}$ ）。當然，為了避免平凡情況，我們還要求當這個泄露的項從輸入數據庫中排除（例如，用一個隨機的不同項替換）時，它能從輸出中提取出來的概率非常小。這意味著任何高效的（所謂的）合成器確實在很強的意義上損害了輸入項的隱私。

下面的定義9.1將形式化我們對合成器的實用性要求。有三個參數： $\alpha$ 描述了準確性要求（在 $\alpha$ 范圍內被認為是準確的）； $\gamma$ 描述了成功合成允許不準確的查詢比例， $\beta$ 將是失敗的概率。

對于一個產生合成數據庫的算法 $A$ ，如果對于 $\gamma$ 比例的查詢 $\in \mathcal{Q}$ 有 $\left| {q\left( {A\left( x\right) }\right) - q\left( x\right) }\right| \leq \alpha$ ，我們就說輸出 $A\left( x\right)$ 對于查詢集 $\mathcal{Q}$ 是 $\left( {\alpha ,\gamma }\right)$ - 準確的。

定義9.1 $\left( {\left( {\alpha ,\beta ,\gamma }\right) \text{-Utility}}\right)$ 。設 $\mathcal{Q}$ 是一個查詢集， $\mathcal{X}$ 是一個數據全域。如果對于任何 $n$ 項數據庫 $x$ ，合成器 $A$ 對于 $\mathcal{Q}$ 和 $\mathcal{X}$ 具有 $\left( {\alpha ,\beta ,\gamma }\right)$ - 實用性：

$\Pr \left\lbrack {A\left( x\right) \text{ is }\left( {\alpha ,\gamma }\right) \text{-accurate for }\mathcal{Q}}\right\rbrack \geq 1 - \beta$

其中概率是基于 $A$ 的隨機選擇。

設 $\mathcal{Q} = {\left\{ {\mathcal{Q}}_{n}\right\} }_{n = 1,2,\ldots }$ 為查詢族集合， $\mathcal{X} = {\left\{ {\mathcal{X}}_{n}\right\} }_{n = 1,2,\ldots }$ 為數據全域集合。若一個算法的運行時間為關于 $\left( {n,\log \left( \left| {\mathcal{Q}}_{n}\right| \right) ,\log \left( \left| {\mathcal{X}}_{n}\right| \right) }\right)$ 的多項式，則稱該算法是高效的。

在接下來的定義中，我們將描述一族分布難以合成意味著什么。更具體地說，我們將說明生成提供 $\left( {\alpha ,\gamma }\right)$ - 精度的合成數據庫困難意味著什么。和往常一樣，我們必須將其表述為一個漸近性陳述。

定義9.2（ $(\left( {\mu ,\alpha ,\beta ,\gamma ,\mathcal{Q}}\right)$ - 難以合成的數據庫分布）。設 $\mathcal{Q} = {\left\{ {\mathcal{Q}}_{n}\right\} }_{n = 1,2,\ldots }$ 為查詢族集合， $\mathcal{X} =$ ${\left\{ {\mathcal{X}}_{n}\right\} }_{n = 1,2,\ldots }$ 為數據全域集合，且設 $\mu ,\alpha ,\beta ,\gamma \in \left\lbrack {0,1}\right\rbrack$ 。設 $n$ 為數據庫大小， $\mathcal{D}$ 為分布集合，其中 ${\mathcal{D}}_{n}$ 是關于從 ${X}_{n}$ 中選取的 $n + 1$ 個項的集合。

我們用 $\left( {x,i,{x}_{i}^{\prime }}\right) \sim {\mathcal{D}}_{n}$ 表示這樣一個實驗：選擇一個 $n$ - 元素數據庫，從 $\left\lbrack n\right\rbrack$ 中均勻選取一個索引 $i$ ，并從 ${\mathcal{X}}_{n}$ 中選取一個額外元素 ${x}_{i}^{\prime }$ 。從 ${\mathcal{D}}_{n}$ 中抽取的一個樣本會得到一對數據庫： $x$ 以及將 $x$ 的第 $i$ 個元素（在規范排序下）替換為 ${x}_{i}^{\prime }$ 后的結果。因此，我們認為 ${\mathcal{D}}_{n}$ 指定了一個關于 $n$ - 項數據庫（及其相鄰數據庫）的分布。

我們稱 $\mathcal{D}$ 是 $\left( {\mu ,\alpha ,\beta ,\gamma ,\mathcal{Q}}\right)$ - 難以合成的，如果存在一個高效算法 $T$ ，使得對于任何所謂的高效合成器 $A$ ，以下兩個條件成立：

在數據庫 $\sim \mathcal{D}$ 的選擇以及 $A$ 和 $T$ 的隨機硬幣拋擲結果上，以概率 $\mu$ 而言，如果 $A\left( x\right)$ 對 $\gamma$ 比例的查詢保持 $\alpha$ -效用，那么 $T$ 可以從 $A\left( x\right)$ 中恢復 $x$ 的某一行：

概率

$\left( {x,i,{x}_{i}^{\prime }}\right) \sim {D}_{n}$

$A, T$ 的硬幣拋擲結果

$\left\lbrack {\left( {A\left( x\right) \text{ maintains }\left( {\alpha ,\beta ,\gamma }\right) \text{-utility}}\right) \text{ and }\left( {x \cap T\left( {A\left( x\right) }\right) = \varnothing }\right) }\right\rbrack \leq \mu$

對于每一個高效算法 $A$ ，以及每一個 $\in \left\lbrack n\right\rbrack$ ，如果我們從 $D$ 中抽取 $\left( {x,i,{x}_{i}^{\prime }}\right)$ ，并將 ${x}_{i}$ 替換為 ${x}_{i}^{\prime }$ 以形成 ${x}^{\prime },T$ ，那么除了以極小的概率外，無法從 $A\left( {x}^{\prime }\right)$ 中提取 ${x}_{i}$ ：

$\begin{array}{l} \;\mathop{\Pr }\limits_{{\left( {x,i,{x}_{i}^{\prime }}\right) \sim {D}_{n}}}\left\lbrack {{x}_{i} \in T\left( {A\left( {x}^{\prime }\right) }\right) }\right\rbrack \leq \mu . \\ \text{ coin flips of }A,T \\ \end{array}$

稍后，我們將關注能生成任意概要（不一定是合成數據庫）的離線機制。在這種情況下，我們將關注難以清理（而非難以合成）的相關概念，為此我們只需去掉 $A$ 生成合成數據庫這一要求。

9.2 一些難以合成的分布

我們現在構造三種難以合成的分布。

一個簽名方案由三元組（可能是隨機化的）算法（Gen、Sign、Verify）給出：

Gen： ${1}^{\mathbb{N}} \rightarrow {\left\{ {\left( \mathrm{{SK}},\mathrm{{VK}}\right) }_{n}\right\} }_{n = 1,2,\ldots }$ 用于生成一個由（秘密）簽名密鑰和（公開）驗證密鑰組成的對。它僅以一元形式表示的安全參數 $\kappa \in \mathbb{N}$ 作為輸入，并生成一個從 ${\left( \mathrm{{SK}},\mathrm{{VK}}\right) }_{\kappa }$ 中抽取的對， ${\left( \mathrm{{SK}},\mathrm{{VK}}\right) }_{\kappa }$ 是由 $\kappa$ 索引的（簽名、驗證）密鑰對的分布；我們分別用 ${p}_{s}\left( \kappa \right) ,{p}_{v}\left( \kappa \right) ,\ell s\left( \kappa \right)$ 表示簽名密鑰、驗證密鑰和簽名的長度。
Sign： ${\mathrm{{SK}}}_{\kappa } \times \{ 0,1{\} }^{\ell \left( \kappa \right) } \rightarrow \{ 0,1{\} }^{\ell s\left( \kappa \right) }$ 以從 ${\left( \mathrm{{SK}},\mathrm{{VK}}\right) }_{\kappa }$ 中抽取的密鑰對中的簽名密鑰和長度為 $\ell \left( \kappa \right)$ 的消息 $m$ 作為輸入，并生成 $m$ 的簽名；
Verify： ${\mathrm{{VK}}}_{\kappa } \times \{ 0,1{\} }^{ * } \times \{ 0,1{\} }^{\ell \left( \kappa \right) } \rightarrow \{ 0,1\}$ 以驗證密鑰、字符串 $\sigma$ 和長度為 $\ell \left( \kappa \right)$ 的消息 $m$ 作為輸入，并檢查 $\sigma$ 是否確實是在給定驗證密鑰下 $m$ 的有效簽名。

密鑰、消息長度和簽名長度在 $\kappa$ 上均為多項式。

所需的安全性概念是，給定任意多項式（關于 $\kappa$ ）數量的有效（消息，簽名）對，偽造任何新的簽名是困難的，即使是對先前已簽名消息的新簽名（請回想一下，簽名算法可能是隨機化的，因此在相同的簽名密鑰下，同一消息可能存在多個有效簽名）。這樣的簽名方案可以從任何單向函數構造出來。通俗地說，單向函數是易于計算的函數—— $f\left( x\right)$ 可以在關于 $x$ 的長度（比特數）的多項式時間內計算出來，但難以求逆：對于每個概率多項式時間算法，在安全參數 $\kappa$ 的多項式時間內運行，在 $f$ 的定義域中隨機選擇 $x$ 時，找到 $f\left( x\right)$ 的任何有效原像的概率，增長速度比 $\kappa$ 的任何多項式的倒數都慢。

難以合成分布 I：固定一個任意的簽名方案。計數查詢集合 ${\mathcal{Q}}_{\kappa }$ 為每個驗證密鑰 $\in {\mathrm{{VK}}}_{\kappa }$ 包含一個計數查詢 ${q}_{vk}$ 。數據全域 ${\mathcal{X}}_{\kappa }$ 由所有可能的（消息，簽名）對組成，這些對的形式是使用 ${\mathrm{{VK}}}_{\kappa }$ 中的密鑰對長度為 $\ell \left( \kappa \right)$ 的消息進行簽名得到的。

數據庫上的分布 ${\mathcal{D}}_{\kappa }$ 由以下采樣過程定義。運行簽名方案生成器 $\operatorname{Gen}\left( {1}^{\kappa }\right)$ 以獲得（私鑰，公鑰）。在 $\{ 0,1{\} }^{\ell \left( \kappa \right) }$ 中隨機選擇 $\kappa$ 條消息，并對每條消息運行簽名過程，得到一組由密鑰 ${sk}$ 簽名的 $n$ 個（消息，簽名）對。這就是數據庫 $x$ 。請注意，數據庫中的所有消息都使用相同的簽名密鑰進行簽名。

數據全域項 $\left( {m,\sigma }\right)$ 滿足謂詞 ${q}_{vk}$ 當且僅當 $\operatorname{Verify}\left( {{vk},m,\sigma }\right) = 1$ ，即根據驗證密鑰 ${vk}$ ， $\sigma$ 是 $m$ 的有效簽名。

設 $\in }_{R}{\mathcal{D}}_{\kappa }$ 為一個數據庫，設 ${sk}$ 為所使用的簽名密鑰，對應的驗證密鑰為 ${vk}$ 。假設合成器生成了 $y$ ，那么 $y$ 的幾乎所有行在 ${vk}$ 下都必須是有效簽名（因為查詢 ${vk}$ 中 $x$ 的分數計數為 1）。根據簽名方案的不可偽造性，所有這些簽名都必須來自輸入數據庫 $x ?$ ，因為多項式時間受限的管理者在時間 poly $\left( \kappa \right)$ 內無法生成新的有效（消息，簽名）對。更正式地（只是稍微更正式），一個高效算法能夠生成一個可以用密鑰 ${vk}$ 驗證但不在 $x$ 中的（消息，簽名）對的概率是可以忽略不計的，因此，一個高效合成器生成的任何 $y$ 極有可能只包含 $x\frac{4}{3}$ 的行。這與（任何合理的）隱私概念相矛盾。

在這種構造中， ${\mathcal{Q}}_{\kappa }$ （驗證密鑰集合）和 ${\mathcal{X}}_{\kappa }$ （(消息,簽名)對集合）都很大（相對于 $\kappa$ 是超多項式的）。當這兩個集合都較小時，就可以高效地進行合成數據集的差分隱私生成。也就是說，存在一個差分隱私合成器，其運行時間相對于 $\kappa ,\left| {\mathcal{Q}}_{\kappa }\right|$ 和 $\left| {\mathcal{X}}_{\kappa }\right|$ 是多項式的：使用拉普拉斯機制計算帶噪聲的計數以獲得概要，然后運行第6節中的合成器。因此，當這兩個集合的大小相對于 $\kappa$ 是多項式時，合成器的運行時間相對于 $\kappa$ 也是多項式的。

我們現在簡要討論將第一個困難性結果推廣到其中一個集合較小（但另一個仍然很大）的情況。

難以合成的分布II：在上述數據庫分布中，我們選擇了一個單一的(sk,vk)密鑰對，并生成了一個消息數據庫，所有消息都使用 ${sk}$ 進行簽名；通過要求合成器在 ${sk}$ 下生成一個新簽名，使得合成后的數據庫能夠為查詢 ${q}_{vk}$ 提供準確答案，從而得到了困難性。為了在查詢集合的大小僅相對于安全參數是多項式時獲得合成的困難性，我們再次使用數字簽名，用唯一的密鑰進行簽名，但我們無法為每個可能的驗證密鑰 ${vk}$ 設置一個查詢，因為這些密鑰數量太多。

${}^{4}$ 量化順序很重要，否則合成器可能會將簽名密鑰硬編碼進去。我們首先固定合成器，然后運行生成器并構建數據庫。概率是基于實驗中的所有隨機性：密鑰對的選擇、數據庫的構建以及合成器使用的隨機性。

為了解決這個問題，我們做了兩個改變：

數據庫行現在的形式為(驗證密鑰, 消息, 簽名)。更準確地說，數據全域由(key,message,signature)三元組 $\mathcal{X} = \left\{ {\left( {{vk},m,s}\right) : {vk} \in {\mathrm{{VK}}}_{\kappa },m \in }\right.$ $\{ 0,1{\} }^{\ell \left( \kappa \right) },s \in \{ 0,1{\} }^{\ell s\left( \kappa \right) }\}$ 組成。
我們向查詢類中精確添加 $2{p}_{v}\left( \kappa \right)$ 個查詢，其中 ${p}_{v}\left( \kappa \right)$ 是運行生成算法 $\operatorname{Gen}\left( {1}^{\kappa }\right)$ 產生的驗證密鑰的長度。查詢的形式為(i,b)，其中 $\leq i \leq {p}_{v}\left( \kappa \right)$ 且 $\in \{ 0,1\}$ 。查詢“(i,b)”的含義是，“數據庫行中形式為(vk,m,s)且 $\operatorname{Verify}\left( {{vk},m,s}\right) = 1$ 并且 ${vk}$ 的第 $i$ 位是 $b$ 的行所占的比例是多少？” 通過用根據單個密鑰 ${vk}$ 簽名的消息填充數據庫，我們確保當 $v{k}_{i} = b$ 時，對于所有 $\leq i \leq p\left( \kappa \right)$ ，這些查詢的響應應該接近1，而當 $v{k}_{i} = 1 - b$ 時，應該接近0。

考慮到這一點，數據庫上難以合成的分布是通過以下采樣過程構建的：生成一個簽名 - 驗證密鑰對 $\left( {{sk},{vk}}\right) \leftarrow \operatorname{Gen}\left( {1}^{\kappa }\right)$ ，并從 $\{ 0,1{\} }^{\ell \left( \kappa \right) }$ 中均勻選擇 $\kappa$ 條消息 ${m}_{1},\ldots ,{m}_{n}$ 。數據庫 $x$ 將有 $n$ 行；對于 $\in \left\lbrack n\right\rbrack$ ，第 $j$ 行是驗證密鑰、第 $j$ 條消息及其有效簽名，即元組 $\left( {{vk},{m}_{j},\operatorname{Sign}\left( {{m}_{j},{sk}}\right) }\right)$ 。接下來，從 $\left\lbrack n\right\rbrack$ 中均勻選擇 $i$ 。為了生成第 $\left( {n + 1}\right)$ 項 ${x}_{i}^{\prime }$ ，只需生成一個新的消息 - 簽名對（使用相同的密鑰 ${sk}$ ）。

難以合成的分布III：為了證明多項式（關于 $\kappa$ ）大小的消息空間（但超多項式大小的查詢集）情況下的難度，我們使用偽隨機函數。粗略地說，這些是具有簡短描述的多項式時間可計算函數，僅根據其輸入 - 輸出行為，無法有效地將它們與真正的隨機函數（其描述很長）區分開來。只有當我們堅持為所有查詢保持實用性時，這個結果才表明合成的難度。實際上，如果我們只關心確保平均實用性，那么第6節中描述的計數查詢的基本生成器在全域 $\mathcal{X}$ 是多項式大小時，即使 $\mathcal{Q}$ 是指數大的，也能產生一種有效的合成算法。

設 ${\left\{ {f}_{s}\right\} }_{s \in \{ 0,1{\} }^{\kappa }}$ 是一個從 $\left\lbrack \ell \right\rbrack$ 到 $\left\lbrack \ell \right\rbrack$ 的偽隨機函數族，其中 $\ell \in \operatorname{poly}\left( \kappa \right)$ 。更具體地說，我們需要 $\left\lbrack \ell \right\rbrack$ 中所有元素對的集合“小”，但大于 $\kappa$ ；這樣，描述該函數族中一個函數的 $\kappa$ 位字符串比描述一個將 $\left\lbrack \ell \right\rbrack$ 映射到 $\left\lbrack \ell \right\rbrack$ 的隨機函數所需的 ${\log }_{2}\ell$ 位要短。這樣的偽隨機函數族可以從任何單向函數構造出來。

我們的數據全域將是 $\left\lbrack \ell \right\rbrack$ 中所有元素對的集合： $\mathcal{X} = \{ \left( {a,b}\right) : a,b \in \left\lbrack \ell \right\rbrack \} .{\mathcal{Q}}_{\kappa }$ 將包含兩種類型的查詢：

對于該函數族中的每個函數 ${\left\{ {f}_{s}\right\} }_{s \in \{ 0,1{\} }^{\kappa }}$ ，都會有一個查詢。全域元素 $\left( {a,b}\right) \in \mathcal{X}$ 滿足查詢 $s$ 當且僅當 ${f}_{s}\left( a\right) = b$ 。
將有相對較少數量（比如 $\kappa$ ）的真正隨機查詢。這樣的查詢可以通過為每個 $\left( {a,b}\right) \in \mathcal{X}$ 隨機選擇(a,b)是否滿足該查詢來構造。

難以合成的分布生成方式如下。首先，我們隨機選擇一個字符串 $\in \{ 0,1{\} }^{\kappa }$ ，它指定了我們函數族中的一個函數。接下來，對于從 $\left\lbrack \ell \right\rbrack$ 中無放回隨機選取的 $\kappa$ 個不同值 ${a}_{1},\ldots ,{a}_{n}$ ，我們生成宇宙元素 $\left( {a,{f}_{s}\left( a\right) }\right)$ 。

其直覺很簡單，僅依賴于第一種類型的查詢，并且不利用 ${a}_{i}$ 的獨特性。給定一個根據我們的分布生成的數據庫 $x$ ，其中偽隨機函數由 $s$ 給出，合成器必須創建一個合成數據庫，（幾乎）其所有行都必須滿足查詢 $s$ 。直覺是它無法可靠地找到不出現在 $x$ 中的輸入 - 輸出對。更準確地說，對于任意元素 $\in \left\lbrack \ell \right\rbrack$ ，使得 $x$ 中沒有形式為 $\left( {a,{f}_{s}\left( a\right) }\right)$ 的行， ${f}_{s}$ 的偽隨機性表明，一個高效的合成器找到 ${f}_{s}\left( a\right)$ 的概率最多只比 $1/\ell$ 略大一點。從這個意義上說，偽隨機性給我們帶來的性質與我們從數字簽名中獲得的性質類似，盡管稍弱一些。

當然，對于任何給定的 $\in \left\lbrack \ell \right\rbrack$ ，合成器確實可以以概率 $1/\ell$ 猜出值 ${f}_{s}\left( a\right)$ ，因此如果沒有第二種類型的查詢，顯然沒有什么能阻止它忽略 $x$ ，選擇任意的 $a$ ，并輸出一個包含 $n$ 個 (a, b) 副本的數據庫，其中 $b$ 是從 $\left\lbrack \ell \right\rbrack$ 中均勻隨機選取的。現在的直覺是，這樣的合成數據庫會給出錯誤的比例 - 要么是零，要么是一，而真正隨機查詢的正確答案應該約為 $1/2 ?$ 。

形式上，我們有：

定理 9.1。設 $\{ 0,1{\} }^{\kappa } \rightarrow \{ 0,1{\} }^{\kappa }$ 是一個單向函數。對于每個 $a > 0$ ，以及每個整數 $\operatorname{poly}\left( \kappa \right)$ ，存在一個大小為 $\exp \left( {\operatorname{poly}\left( \kappa \right) }\right)$ 的查詢族 $\mathcal{Q}$ 、一個大小為 $O\left( {n}^{2 + {2a}}\right)$ 的數據宇宙 $\mathcal{X}$ ，以及一個大小為 $n$ 的數據庫上的分布，該分布對于 $\alpha \leq$ $1/3,\beta \leq 1/{10}$ 和 $\mu = 1/{40}{n}^{1 + a}$ 是 $\left( {\mu ,\alpha ,\beta ,0,\mathcal{Q}}\right)$ - 難以合成的（即，對于最壞情況的查詢難以合成）。

上述定理表明了使用合成數據進行數據清理的難度。然而，請注意，當查詢集較小時，人們總是可以簡單地為每個查詢發布帶噪聲的計數。我們得出結論，對于小查詢類（具有大數據宇宙）進行數據清理是一項將高效合成與高效概要生成（具有任意輸出的數據清理）區分開來的任務。

9.2.1 一般概要的難度結果

上一節的難度結果僅適用于合成器——創建合成數據庫的離線機制。更通用形式的隱私保護離線機制（我們一直稱之為離線查詢發布機制或概要生成器）的難度與叛徒追蹤方案的存在之間存在著緊密的聯系。叛徒追蹤方案是一種內容分發方法，在該方法中，（短）密鑰字符串以某種方式分發給訂閱者，使得發送者可以廣播加密消息，任何訂閱者都可以解密這些消息，并且由惡意訂閱者聯盟構建的任何有用的“盜版”解碼器都可以追溯到至少一個合謀者。

一個（私鑰、無狀態）叛徒追蹤方案由算法設置（Setup）、加密（Encrypt）、解密（Decrypt）和追蹤（Trace）組成。設置算法為廣播者生成一個密鑰 ${bk}$ 和 $N$ 個訂閱者密鑰 ${k}_{1},\ldots ,{k}_{N}$ 。加密算法使用廣播者的密鑰 ${bk}$ 對給定的比特進行加密。解密算法使用任何一個訂閱者密鑰對給定的密文進行解密。追蹤算法獲取密鑰 ${bk}$ 并以預言機方式訪問一個（盜版、無狀態）解密盒，然后輸出用于創建盜版盒的密鑰 ${k}_{i}$ 的索引 $\in \{ 1,\ldots ,N\}$ 。

叛徒追蹤方案的一個重要參數是其抗合謀性：如果只要用于創建盜版解碼器的密鑰不超過 $t$ 個，追蹤就保證有效，那么該方案就是 $t$ - 抗合謀的。當 $t = N$ 時，即使所有訂閱者聯合起來試圖創建一個盜版解碼器，追蹤仍然有效。下面是一個更完整的定義。

定義9.3。如上所述的方案（設置、加密、解密、追蹤）是一個t - 抗合謀叛徒追蹤方案，如果（i）它生成的密文是語義安全的（粗略地說，多項式時間算法無法區分0的加密和1的加密），并且（ii）沒有多項式時間敵手 $A$ 能以不可忽略的概率（在設置、 $A$ 和追蹤的隨機硬幣上）在以下游戲中“獲勝”：

$A$ 接收用戶數量 $N$ 和一個安全參數 $\kappa$ ，并（自適應地）請求最多 $t$ 個用戶 $\left\{ {{i}_{1},\ldots ,{i}_{t}}\right\}$ 的密鑰。然后敵手輸出一個盜版解碼器Dec。使用密鑰 ${bk}$ 并以黑盒方式 ${}^{5}$ 訪問Dec來運行追蹤算法；它輸出一個用戶的名稱 $\in \left\lbrack N\right\rbrack$ 或錯誤符號 $\bot$ 。我們說敵手 $A$ “獲勝”，如果Dec在解密密文方面有不可忽略的優勢（甚至比創建一個可用的盜版解密設備的條件更弱），并且追蹤的輸出不在 $\left\{ {{i}_{1},\ldots ,{i}_{t}}\right\}$ 中，這意味著敵手避免了被檢測。

${}^{5}$ 以黑盒方式訪問一個算法意味著無法訪問該算法的內部結構；只能向算法提供輸入并觀察其輸出。

叛徒追蹤方案為何意味著計數查詢發布存在難度結果的直觀解釋如下。固定一個叛徒追蹤方案。我們必須描述那些查詢發布在計算上困難的數據庫和計數查詢。

對于任何給定的 $\kappa$ ，數據庫 $\in {\left\{ \{ 0,1{\} }^{d}\right\} }^{n}$ 將包含來自 $n$ 個合謀用戶的叛逆者追蹤方案的用戶密鑰；這里 $d$ 是在輸入 ${1}^{\kappa }$ 上運行設置算法時獲得的解密密鑰的長度。查詢族 ${\mathcal{Q}}_{\kappa }$ 將針對每個可能的密文 $c$ 有一個查詢 ${q}_{c}$ ，詢問“對于多少比例的行 $\in \left\lbrack n\right\rbrack$ ，密文 $c$ 在第 $i$ 行的密鑰下解密為1？” 請注意，由于每個用戶都可以解密，如果發送者分發比特1的加密 $c$ ，答案將是1：所有行都將 $c$ 解密為1，因此這樣的行的比例為1。相反，如果發送者分發比特0的加密 ${c}^{\prime }$ ，答案將是0：因為沒有行將 ${c}^{\prime }$ 解密為1，所以將 ${c}^{\prime }$ 解密為1的行的比例為0。因此，對于查詢 ${q}_{c}$ （其中 $c$ 是1比特消息 $b$ 的加密）的準確答案就是 $b$ 本身。

現在，假設存在一種針對 $\mathcal{Q}$ 中的查詢的高效離線差分隱私查詢發布機制。合謀者可以使用該算法高效地生成數據庫的概要，使數據分析師能夠高效地計算查詢 ${q}_{c}$ 的近似答案。如果這些近似值并非無意義，那么分析師可以使用它們進行正確解密。也就是說，合謀者可以利用這一點來制造一個盜版解碼器盒。但叛逆者追蹤確保了，對于任何這樣的盒子，追蹤算法可以恢復至少一個用戶的密鑰，即數據庫的一行。這違反了差分隱私，與存在一種用于發布 $\mathcal{Q}$ 的高效差分隱私算法的假設相矛盾。

這一方向已被用于排除針對特定類別的 ${2}^{\widetilde{O}\left( \sqrt{n}\right) }$ 計數查詢的高效離線清理器的存在；這可以擴展到排除針對從第二個（大）類中自適應抽取的 $\widetilde{\Theta }\left( {n}^{2}\right)$ 計數查詢的高效在線清理器的存在。

計數查詢的離線查詢發布困難意味著叛逆者追蹤的直覺在于，未能保護隱私會立即產生某種形式的可追蹤性；也就是說，在為一組行（解密密鑰）提供（近似）功能等價物的同時保護每一行（解密密鑰）的隱私的難度——即制造一個不可追蹤的解碼器的難度——正是我們在叛逆者追蹤方案中所尋求的。

更詳細地說，給定一個難以清理的數據庫分布和計數查詢族，隨機抽取的 $n$ 項數據庫可以充當“主密鑰”，其中用于解密消息的秘密是該數據庫上隨機查詢的計數。對于隨機選擇的多對數(n)個查詢的子集 $S$ ，從數據庫中隨機抽取的多對數(n)行的集合（很可能）能很好地近似 $S$ 中的所有查詢。因此，可以通過將數據庫隨機劃分為 $n /$ 個多對數(n)行的多對數(n)集合，并將每個集合分配給不同的用戶來獲得各個用戶的密鑰。這些集合足夠大，以至于在壓倒性概率下，它們在例如多對數(n)個隨機查詢集合上的計數都接近原始數據庫的計數。

為了完成這個論證，我們設計了一種加密方案，其中解密等同于計算小的隨機查詢集合上的近似計數。由于根據定義，盜版解密盒可以進行解密，因此盜版盒可以用于計算近似計數。如果我們將這個盒子視為數據庫的清理結果，我們可以得出結論（因為清理是困難的），解密盒可以“追溯”到用于創建它的密鑰（數據庫項）。

9.3 多項式時間敵手

定義9.4（計算差分隱私）。當且僅當對于所有僅相差一行的數據庫 $x, y$ ，以及所有非均勻多項式（關于 $\kappa$ ）算法 $T$ ，隨機算法 ${C}_{\kappa } : {\mathcal{X}}^{n} \rightarrow Y$ 是 $\varepsilon$ -計算差分隱私的。

$\Pr \left\lbrack {T\left( {{C}_{\kappa }\left( x\right) }\right) = 1}\right\rbrack \leq {e}^{\varepsilon }\Pr \left\lbrack {T\left( {{C}_{\kappa }\left( y\right) }\right) = 1}\right\rbrack + \nu \left( \kappa \right) ,$

其中 $\nu \left( \cdot \right)$ 是任何增長速度比任何多項式的倒數都慢的函數，并且算法 ${C}_{\kappa }$ 在 $n$ 、 $\log \left| \mathcal{X}\right|$ 和 $\kappa$ 的多項式時間內運行。

直觀地說，這意味著如果對手被限制在多項式時間內，那么計算差分隱私機制提供的隱私程度與 $\left( {\varepsilon ,\nu \left( \kappa \right) }\right)$ -差分隱私算法相同。一般來說，消除 $\nu \left( \kappa \right)$ 項是沒有希望的；例如，當涉及加密時，總是有一些（極小的）機會猜出解密密鑰。

一旦我們假設對手被限制在多項式時間內，我們就可以使用安全多方計算的強大技術來提供分布式在線查詢發布算法，用模擬可信策展人的分布式協議取代可信服務器。因此，例如，一組醫院，每家醫院都持有許多患者的數據，可以協作對其患者的聯合數據進行統計分析，同時確保每個患者的差分隱私。一個更激進的影響是，個人可以維護自己的數據，選擇參與或不參與每個特定的統計查詢或研究，同時確保自己數據的差分隱私。

我們已經看到了一種分布式解決方案，至少對于計算 $n$ 位之和的問題：隨機響應。這種解決方案不需要計算假設，并且預期誤差為 $\Theta \left( \sqrt{n}\right)$ 。相比之下，使用密碼學假設允許進行更準確和廣泛的分析，因為通過模擬策展人，它可以運行拉普拉斯機制的分布式實現，該機制具有恒定的預期誤差。

這就引出了一個自然的問題，即是否存在某種不依賴于密碼學假設的其他方法，在分布式環境中比隨機響應具有更高的準確性。或者更一般地說，計算差分隱私所能實現的與“傳統”差分隱私所能實現的之間是否存在差異？也就是說，密碼學是否確實為我們帶來了一些好處？

在多方環境中，答案是肯定的。仍然將我們的注意力限制在對 $n$ 位求和上，我們有：

定理9.2。對于 $\varepsilon < 1$ ，每個用于計算 $n$ 位（每方一位）之和的 $n$ -方 $\left( {\varepsilon ,0}\right)$ -差分隱私協議在高概率下會產生誤差 $\Omega \left( {n}^{1/2}\right)$ 。

如果 $\delta \in$ $o\left( {1/n}\right)$ ，對于 $\left( {\varepsilon ,\delta }\right)$ -差分隱私也有類似的定理成立。

證明。（概要）設 ${X}_{1},\ldots ,{X}_{n}$ 是均勻獨立的位。協議的記錄 $T$ 是一個隨機變量 $T\left( {{P}_{1}\left( {X}_{1}\right) ,\ldots ,}\right.$ ${P}_{n}\left( {X}_{n}\right)$ ，其中對于 $\in \left\lbrack n\right\rbrack$ ，玩家 $i$ 的協議表示為 ${P}_{i}$ 。在 $T = t$ 的條件下，位 ${X}_{1},\ldots ,{X}_{n}$ 仍然是獨立的位，每個位的偏差為 $O\left( \varepsilon \right)$ 。此外，通過差分隱私、 ${X}_{i}$ 的均勻性和貝葉斯定律，我們有：

$\frac{\Pr \left\lbrack {{X}_{i} = 1 \mid T = t}\right\rbrack }{\Pr \left\lbrack {{X}_{i} = 0 \mid T = t}\right\rbrack } = \frac{\Pr \left\lbrack {T = t \mid {X}_{i} = 1}\right\rbrack }{\Pr \left\lbrack {T = t \mid {X}_{i} = 0}\right\rbrack } \leq {e}^{\varepsilon } < 1 + {2\varepsilon }.$

為完成證明，我們注意到 $n$ 個獨立比特（每個比特都有恒定偏差）的和，以很高的概率落在任何大小為 $o\left( \sqrt{n}\right)$ 的區間之外。因此，以很高的概率，和 $\mathop{\sum }\limits_{i}{X}_{i}$ 不在區間 $\left\lbrack {\operatorname{output}\left( \mathrm{T}\right) - o\left( {n}^{1/2}\right) ,\operatorname{output}\left( \mathrm{T}\right) + o\left( {n}^{1/2}\right) }\right\rbrack$ 內。

一個更復雜的證明表明，即使在兩方的情況下，計算差分隱私（computational differential privacy）和普通差分隱私（ordinary differential privacy）之間也存在差異。在可信策展人（trusted curator）的情況下，計算假設是否能為我們帶來任何好處，這是一個引人入勝的開放性問題。初步結果是否定的：對于少量實值查詢，即查詢數量不隨安全參數增長的情況，存在一類自然的效用度量，包括 ${L}_{p}$ 距離和均方誤差，對于這些度量，任何計算上私密的機制都可以轉換為一個統計上私密的機制，該機制大致同樣高效，并且能實現幾乎相同的效用。

9.4 參考文獻注釋

多項式時間有界策展人的負面結果以及與叛徒追蹤（traitor tracing）的聯系歸功于 Dwork 等人 [28]。Ullman [82] 進一步研究了與叛徒追蹤的聯系，他表明，假設單向函數存在，以差分隱私回答 ${n}^{2 + o\left( 1\right) }$ 個任意線性查詢在計算上是困難的（即使在不考慮隱私的情況下，答案很容易計算）。在《我們的數據，我們自己》（“Our Data, Ourselves”）中，Dwork、Kenthapadi、McSherry、Mironov 和 Naor 使用安全函數評估技術代替可信策展人，考慮了差分隱私前身的分布式版本 [21]。[64] 中開始了對計算差分隱私的正式研究，定理 9.2 中多方和單策展人情況下 $\left( {\varepsilon ,0}\right)$ -差分隱私所能達到的準確性之間的差異歸功于 McGregor 等人 [58]。關于在可信策展人情況下，對對手的計算假設是否能帶來任何好處的初步結果歸功于 Groce 等人 [37]。

從任何單向函數構造偽隨機函數（pseudorandom functions）歸功于 H?stad 等人 [40]。

目錄導航

第1章：https://blog.csdn.net/AdamCY888/article/details/146454841
第2章:https://blog.csdn.net/AdamCY888/article/details/146455093
第3章(1/3):https://blog.csdn.net/AdamCY888/article/details/146455756
第3章(2/3):https://blog.csdn.net/AdamCY888/article/details/146455796
第3章(3/3):https://blog.csdn.net/AdamCY888/article/details/146455328
第4章:https://blog.csdn.net/AdamCY888/article/details/146455882
第5章:https://blog.csdn.net/AdamCY888/article/details/146456100
第6章(1/2):https://blog.csdn.net/AdamCY888/article/details/146456712
第6章(2/2):https://blog.csdn.net/AdamCY888/article/details/146456972
第7章:https://blog.csdn.net/AdamCY888/article/details/146457037
第8章:https://blog.csdn.net/AdamCY888/article/details/146457172
第9章:https://blog.csdn.net/AdamCY888/article/details/146457257
第10章:https://blog.csdn.net/AdamCY888/article/details/146457331
第11章:https://blog.csdn.net/AdamCY888/article/details/146457418
第12章:https://blog.csdn.net/AdamCY888/article/details/146457489
第13章(含附錄):https://blog.csdn.net/AdamCY888/article/details/146457601