密碼學之PRP/PRF轉換引理

本文将介紹密碼學中的PRF、PRP等相關概念，并介紹 PRP/PRF 轉換引理及其證明，希望讀完本文後，你能對現代密碼學中這幾個基礎概念有所了解。

在開始本文前，希望你有如下預備知識：

• 現代密碼學是怎樣的一門學科？
• “Security Through Obscurity” 是什麼意思？
• 集合、極限、函數、随機變量、采樣等數學概念是什麼？

概述

在之前的一篇部落格中提到，僞随機性是現代密碼學的根基，每一個密碼算法都需要有這樣的僞随機性來源。而僞随機數發生器隻是一個承載僞随機性的初等原語，其數學性質和模型都太樸素，不足以幫助我們建構更複雜的算法結構。

而僞随機函數的出現，對「如何将随機性這個特點與函數的輸入輸出結合？」這一問題給出了嚴格的數學定義與描述方法。這為各位密碼學家們提供了一個很強的模型。進一步地，僞随機置換則在此基礎上，引入了「映射可逆」的概念，進而豐富和細化了PRF的抽象能力。

這篇部落格将依次介紹僞随機數發生器（PRNG）、僞随機函數（PRF）、僞随機置換（PRP），并給出大名鼎鼎的 PRF/PRP 轉換引理及其證明。

PRNG

僞随機性之于現代密碼學的重要性在之前的部落格中已經為大家介紹過了，而作為僞随機性的載體，僞随機數發生器（Pseudorandom Number Generator，PRNG）的定義重新陳述如下：

令\(G\)為一多項式時間算法，其輸入為\(s\in \{0, 1\}^{n}\)，即為一長度為\(n\)的01比特串，輸出的長度記作\(l(n)\)。其中，\(l(\cdot )\)也為一多項式時間算法，\(l(n)\)則表示是\(n\)的多項式界（如 \(n^{2}\)、\(n\)）下的一個數值。若\(G\)為一PRNG，則應同時滿足如下兩個條件：

• 對于任意的\(n\)，都有\(l(n) > n\)；
• 若此時對于任意一具有多項式資源的敵手\(\mathcal{A}\)，都存在一個可忽略（negligible）的機率 $\epsilon $，使得下式成立：

\[|\mathrm{Pr}[\mathcal{A}(r)=1] - \mathrm{Pr}[\mathcal{A}(G(s))=1]| \le \epsilon \tag{1}

\]

PRNG作為僞随機性最直覺的抽象模型，示意圖如下圖所示。

可以看到，PRNG在算法建構上的表現力似乎還不是很強。例如，\(G(s)\)作為PRNG的輸出，但這和一個密碼算法到底有啥關系？生成密鑰？可一個算法又不隻有密鑰，還有輸入輸出呢！是以，PRNG作為一個初等原語，其抽象能力還是有些弱，這就需要表達能力更強的原語了。

PRF與PRP

PRF

僞随機函數（即 Pseudorandom Function, PRF）與PRNG相比，多了對輸入輸出的描述，而這正是「函數」的意義。在介紹PRF之前，首先介紹随機函數。

随機函數

對于将\(n\)位比特串\(\{0, 1 \}^{n}\)映射到\(n\)位比特串\(\{0, 1 \}^{n}\)的所有函數組成的函數族\(\mathcal{F}\)，一個随機函數\(f\)是指在\(\mathcal{F}\)中以均勻随機采樣的方法選擇得到的一個函數，即有\(f \stackrel{rnd} \in \mathcal{F}\).

在該函數族中，一個函數相當于給出了一種\(2^{n}\)個\(n\)比特長的串的排列，那麼整個函數族的大小即為\(2^{n\cdot 2^{n}}\)。這是一個指數級别的計算規模，是以即使存在一個多項式資源的敵手或區分器，他也無法在多項式時間内模組化某個随機函數\(f\)的映射方式。

僞随機函數

PRF的正式定義如下：

對于一類帶密鑰的函數\(F\)，有\(F: \{0,1\}^{*} \times \{0, 1\}^{*} \rightarrow \{0, 1\}^{*}\)，即\(y \leftarrow F(k, x)\)，其中\(x\)為輸入，\(k\)為密鑰，\(y\)為輸出。若稱\(F\)為PRF，則可滿足以下條件：

• 高效計算：給定\(k\)與\(x\)，存在高效的多項式時間算法能計算\(y=F(k, x)\)；
• 不可區分：随機標明密鑰\(k\)，僞随機函數\(F(k, \cdot)\)與一随機函數\(f(\cdot)\)是不可區分的；
• 長度保留：\(y、x、k\)的長度均為\(n\)；該性質是非必需的。

可以看到，PRF的性質和很多密碼算法都有共性了：接收一個輸入，傳回一個看起來是随機輸出的函數，而這種僞随機性來自于密鑰，隻要密鑰\(k\)不被敵手擷取，\(F(k, x)\)的映射性質就無法被模組化或攻破。是以，在有些地方，PRF會被定義成「在函數族\(\mathcal{F}中\)，由密鑰\(k\)作為索引的随機函數」，記作\(F_{k}(\cdot)\)。

綜上，兩種PRF定義都可以用上面的示意圖來表示。而不論哪種定義，PRF都會涉及密鑰、輸入、輸出三個要素，這正好可以與常見的密碼算法是相同的，消息認證算法就是一種PRF，對稱加密算法在廣義上也是一種PRF。在PRF的模型下，我們似乎可以刻畫出更多的安全性質，例如輸出的不可區分性，輸出的單向性等等。PRF豐富了僞随機性的範圍和尺度，讓其能更好地貼合人們的直覺。

盡管PRF能幫助我們抽象不同的密碼算法，但是卻不能很好地刻畫輸入與輸出之間的映射關系。沒錯，借助PRF的确能建構出\(x\)到\(y\)的映射關系，但對加解密算法而言，\(x\)與\(y\)之間需要是嚴格的雙射。是以，為進一步加強PRF對這類「可逆」密碼算法的表現能力，一種新的原語出現了。

PRP

僞随機置換（即 Pseudorandom Permutation，PRP）與PRF相比，多了對\(x\)到\(y\)映射關系可逆的要求，而這也是「置換」的意義。同樣地，此處将先介紹随機置換。

随機置換

對于将\(n\)位比特串\(\{0, 1 \}^{n}\)映射到自身的所有置換組成的置換族\(\mathcal{P}\)，一個随機置換\(p\)是指在\(\mathcal{P}\)中以均勻随機采樣的方法選擇得到的一個置換，即有\(p \stackrel{rnd} \in \mathcal{P}\).

同理，由于置換一定是雙射的，是以該置換族的大小等價于所有輸出的全排列數量，即為\((2^{n})!\)；但這同樣是一個遠大于多項式（super poly）級别的計算規模，是以即使存在一個多項式資源的敵手或區分器，他也無法在猜出或模組化出某個随機置換\(p\)的映射方式。

僞随機置換

PRP的正式定義如下：

對于一類帶密鑰的置換\(P\)，有\(P: \{0,1\}^{*} \times \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}\)，即\(y \leftarrow P(k, x)\)，其中\(x\)為輸入，\(k\)為密鑰，\(y\)為\(x\)對應的置換後結果。若稱\(P\)為PRP，則可滿足以下條件：

• 高效計算：給定\(k\)與\(x\)，存在高效的多項式時間算法能計算\(y=P(k, x)\)；給定\(k\)與\(y\)，存在高效的多項式時間可逆算法能計算\(x=P^{-1}(k, y)\)
• 不可區分：随機標明密鑰\(k\)，僞随機置換\(P(k, \cdot)\)與一随機置換\(p（\cdot)\)是不可區分的；
• 長度保留：\(y、x\)的長度均為\(n\)。

可以看到，與PRF相比，PRP的定義實質上就是将原來的「函數」變為「置換」，即\(x\)與\(y\)此時位于同一機率空間中，之間的映射關系為雙射，示意圖如下圖所示。PRP對于那些具備逆運算的密碼算法而言，能更好地描述輸入和輸出之間的可逆映射關系，是以更适合用于刻畫加解密算法時。至此，現代密碼學中三個非常重要的原語已經全部介紹完畢。

不可區分性

上文介紹PRF與PRP時，未闡述究竟是如何不可區分的，但這一性質實際上是密碼學計算安全性的核心，本節将予以重點介紹。

PRF的不可區分性

一個長度保留的、可高效計算的PRF \(F_{k}(\cdot)\)的不可區分性表示為，對于任意的具有多項式規模資源的敵手\(\mathcal{A}\)，都存在一個可忽略的極小機率\(\epsilon(n)\)，使得下式成立：

\[|\mathrm{Pr}[\mathcal{A}^{F_{k}(\cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1]| \le \epsilon(n) \tag{2}

其中\(\epsilon(n)\)是指與長度參數\(n\)相關的一個可忽略機率，例如\(\frac{1}{2^{n}}\)；\(\mathcal{A}^{F_{k}(\cdot)}(1^{n})=1\)以及\(\mathcal{A}^{f(\cdot)}(1^{n})=1\)分别表示敵手\(\mathcal{A}\)在未知目前函數是\(F_{k}(\cdot)\)或\(f(\cdot)\)的條件下，正确猜出了這個函數是什麼。\(1^{n}\)表示函數參數規模為\(n\)。是以，式(2)可以寫作：

\[|\mathrm{Pr}[\mathcal{A} 認為目前函數是僞随機函數|目前函數是僞随機函數] \\

- \mathrm{Pr}[\mathcal{A} 認為目前函數是随機函數|目前函數是随機函數]| \le \epsilon

實際上，敵手\(\mathcal{A}\)在辨識目前函數是誰的這種情景，在現代密碼學的語義下，通常稱敵手\(\mathcal{A}\)與一個寓言機（Oracle）\(\mathcal{O}\)進行詢問（query）遊戲（Game），\(\mathcal{O}\)的内部可能是\(F_{k}(\cdot)\)或\(f(\cdot)\)。而根據每次詢問\(\mathcal{O}\)傳回的輸出，\(\mathcal{A}\)最終輸出對\(\mathcal{O}\)的猜測結果。示意圖如下所示。

如圖所示，敵手\(\mathcal{A}\)在與\(\mathcal{O}\)詢問若幹次後，若能正确判定自己面前的這個\(\mathcal{O}\)的内部究竟是一個僞随機函數還是一個随機函數，那就稱\(\mathcal{A}\)攻破了PRF的不可區分性。換言之：

• 當敵手能輕易區分何時是PRF，何時是随機函數時，說明敵手攻破PRF的優勢足夠大；
• 當敵手對這二者是不可區分時，說明敵手攻破PRF的優勢很小。

是以，敵手的這種區分能力其實就是敵手攻破PRF的優勢，那麼式(2)還可以寫作：

\[\mathrm{Adv}_{\mathcal{O}}^{PRF}(\mathcal{A})=|\mathrm{Pr}[\mathcal{A}^{F_{k}(\cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1]| \le \epsilon(n)

其中，\(\mathrm{Adv}_{\mathcal{O}}^{PRF}(\mathcal{A})\)即為敵手\(\mathcal{A}\)面對寓言機\(\mathcal{O}\)時進行不可區分實驗的優勢。

PRP的不可區分性

一個長度保留的、可高效計算的PRP \(P_{k}(\cdot)\)的不可區分性表示為，對于任意的具有多項式規模資源的敵手 \(\mathcal{A}\)，都存在一個可忽略的極小機率 \(\epsilon(n)\)，使得下式成立：

\[|\mathrm{Pr}[\mathcal{A}^{P_{k}(\cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{p(\cdot)}(1^{n})=1]| \le \epsilon(n) \tag{3}

同理，\(\mathcal{A}^{P_{k}(\cdot)}(1^{n})=1\)以及\(\mathcal{A}^{p(\cdot)}(1^{n})=1\)分别表示敵手\(\mathcal{A}\)在目前的寓言機\(\mathcal{O}\)的确是\(P_{k}(\cdot)\)或\(p(\cdot)\)的條件下，正确猜出了這個置換是什麼。示意圖如下圖所示。

在PRP不可區分實驗中，引入敵手的優勢改寫式(3)如下：

\[\mathrm{Adv}_{\mathcal{O}}^{PRP}(\mathcal{A})=|\mathrm{Pr}[\mathcal{A}^{P_{k}(\cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{p(\cdot)}(1^{n})=1]| \le \epsilon(n)

PRP/PRF轉換引理與證明

這個引理能做什麼？

一個安全的加解密算法\(\mathcal{E}=(E, D)\)可以抽象成一個實作了PRP的寓言機。由于在對稱算法的設計中，\(E\)與\(D\)的算法結構通常是對合的（Involution）。是以在證明\(\mathcal{E}\)的安全性時，隻考慮加密算法\(E\)即可。這時，如果\(E\)是安全的，則既可被證明是一個PRP寓言機，也可被證明是一個PRF寓言機。證明\(E\)的安全性，也就是回答下面兩個問題之一：

• 能否證明\(E\)是一個PRP（即\(\mathrm{Adv}_{E}^{PRP}(\mathcal{A})\)是否為可忽略的？）
• 能否證明\(E\)是一個PRF（即\(\mathrm{Adv}_{E}^{PRF}(\mathcal{A})\)是否為可忽略的？）

而許多時候，PRP所代表的這種「置換」模型的安全性并不利于證明工作的推進，如果将其歸約到PRF這種更符合一般數學直覺的「函數」模型上，機率空間的定義、碰撞事件等問題都可以在函數的架構下進行計算和讨論，這為證明的抽象和表示帶來了友善。

是以，在加解密算法尤其是分組密碼的安全性證明中，該引理能将證明工作的重心轉換到更為熟悉和直覺的「函數」模型上。

PRP/PRF轉換引理

鋪墊了這麼多，終于該介紹這個轉換引理的内容了。

令\(\mathcal{A}\)為一具有多項式資源的敵手，\(\mathcal{A}\)對寓言機\(\mathcal{O}\)最多能進行\(q\)次詢問，\(\mathcal{O}\)内部可能實作了一個随機函數\(f\)，也可能實作了一個随機置換\(p\)。對于整數\(n \ge 1\)，則下式[1]成立：

\[|\mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{p(\cdot)}(1^{n})=1]| \le \frac{q(q - 1)}{2^{n+1}} \tag{4}

通常，我們認為敵手不會發送兩次相同的詢問。若考慮到敵手優勢的定義，則有：

\[\begin{align*}

|\mathrm{Adv}_{E}^{PRP}(\mathcal{A})- \mathrm{Adv}_{E}^{PRF}(\mathcal{A})|

&= \left| |\mathrm{Pr}[\mathcal{A}^{E(k,\cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1]|-|\mathrm{Pr}[\mathcal{A}^{E(k, \cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{p(\cdot)}(1^{n})=1]|\right| \\

&\le |\mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{p(\cdot)}(1^{n})=1]| \\

\end{align*}

是以該引理還有另外一種寫法[2]：

\[|\mathrm{Adv}_{E}^{PRP}(\mathcal{A})- \mathrm{Adv}_{E}^{PRF}(\mathcal{A})| \le \frac{q(q-1)}{2^{n+1}} \tag{5}

這兩種形式均是正确的，使用時可根據上下文需求選擇。可以看到， 式(4)表示敵手區分随機函數和随機置換的優勢是一與詢問次數\(q\)和\(n\)有關的值；當\(n\)取較大值如128時，這一上界\(\frac{q(q-1)}{2^{n+1}}\)變成為了可忽略的值，即當算法規模相對詢問次數足夠大時，敵手的區分能力将會很快減弱。

引理證明

為證明這一引理，我們定義事件 \(\mathrm{Coll}\) 為：當敵手\(\mathcal{A}\)送出不同的輸出\(x_{i},x_{j}\)給寓言機\(\mathcal{O}\)後，\(\mathcal{O}\)傳回了相同的輸出\(y\)。而事件 \(\mathrm{Dist}\) 為\(\mathrm{Coll}\)的補集，即 \(\mathrm{Pr[Dist]}=1-\mathrm{Pr[Coll]}\). 首先，我們說明這一結論：

\[\mathrm{Pr}[\mathcal{A}^{p(\cdot)}(1^{n})=1] = \mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1 | \mathrm{Dist} ] \tag{6}

式(6)說明，當敵手的查詢結果未發生碰撞時，敵手是無法區分一個随機函數和一個随機置換的。回顧PRF與PRP的定義，二者最大的差別就在于輸入與輸出所定義的機率空間不同。在PRP這種「置換」定義下，輸入與輸出為同一機率空間，這也就暗含了輸入元素和輸出元素必然為一一對應的雙射關系；而在PRF這種「函數」定義下，輸入與輸出為不同空間，此時多個輸入可能對應同一輸出。

是以，如果已經先驗地确定了輸出不會發生碰撞，那麼函數寓言機将「看起來」與置換寓言機完全一樣，進而式(6)成立。這一結論的其他更嚴格的證明可參照[1]。

當式(6)成立時，令\(x=\mathrm{Pr}[\mathcal{A}^{p(\cdot)}(1^{n})=1] = \mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1 | \mathrm{Dist} ]\)，令\(y=\mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1 | \mathrm{Coll}]\)，根據全機率公式，可得以下結論：

|\mathrm{Pr}[\mathcal{A}^{p(\cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1]|&=\left|x-\mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1|\mathrm{Dist}]\mathrm{Pr[Dist]}-\mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1|\mathrm{Coll}]\mathrm{Pr[Coll]}\right| \\

&=|x-x\mathrm{Pr[Dist]}-y\mathrm{Pr[Coll]}|\\

&=|x-x+x\mathrm{Pr[Coll]}-y\mathrm{Pr[Coll]}| \\

&=|(x-y)\mathrm{Pr[Coll]}|\\

&\le \mathrm{Pr[Coll]} \tag{7}

式(7)的推導說明了此時敵手\(\mathcal{A}\)的區分能力不會超過 \(\mathrm{Coll}\) 事件的發生機率，也就意味着「除非讓\(\mathcal{A}\)在不同的詢問中獲得了相同的結果，否則\(\mathcal{A}\)是不可能知道這是一個随機函數還是一個随機置換的」。這個結論在直覺上也是符合「函數」與「置換」的定義的。

是以，\(\mathrm{Coll}\) 事件若發生，則說明\(\mathcal{A}\)在送出的\(q\)次詢問中，\(\mathcal{O}\)有兩次選取了同一個\(y\)進行傳回，由于函數模型下的\(\mathcal{O}\)是沒有記憶性的（類似古典概型中的小球取出會放回），是以傳回同一個\(y\)發生的機率是\(\frac{1}{2^{n}}\)。另一方面，\(q\)次詢問一共會産生\(\binom{q}{2}\)個\((x_{i}, x_{j})\)組合對。綜上可知，\(\mathrm{Pr[Coll]}\le \binom{q}{2}\frac{1}{2^{n}}=\frac{q(q-1)}{2^{n+1}}\). 證畢。

不同的界

其實，在許多地方，式(4)(5)的不等式上界會寫為\(\frac{q^{2}}{2^{n+1}}\)，即為[3]：

\[|\mathrm{Adv}_{E}^{PRP}(\mathcal{A})- \mathrm{Adv}_{E}^{PRF}(\mathcal{A})| \le |\mathrm{Pr}[\mathcal{A}^{f(\cdot)}(1^{n})=1] - \mathrm{Pr}[\mathcal{A}^{p(\cdot)}(1^{n})=1]| \le \frac{q^{2}}{2^{n+1}} \tag{8}

由先前的證明過程可知，上界\(\frac{q(q-1)}{2^{n+1}}\)若能成立，則自然蘊含\(\frac{q^{2}}{2^{n+1}}\)也是成立的。是以兩種版本的引理公式均是正确的。在許多論文中，式(8)其實是更常見的寫法，這是因為平方式的形式更利于表達和記憶。兩種上界之是以能共存，是由于前者更嚴密（tight），後者更好記，在使用時按需選擇即可。

關于這一不同的上界，更多資訊可以參見這一解答

總結

PRP/PRF轉換引理其實隻是許多複雜證明的第一步，但其「隻要沒碰撞，敵手就分不出來」這一核心思想在對稱算法的證明中卻十分重要。該引理說明了如果一個加密算法是PRP，那它必然也是一個PRF，這一基礎推論應能在證明中靈活應用。此外，如果見到上界不同的兩個引理版本，請不要驚慌，兩個版本都是正确的，可按需使用。最後，本文的所有重點總結如下：

• PRF與PRP的定義和性質
• 不可區分性的本質
• PRP/PRF轉換引理内容
• 碰撞事件的内涵及其機率計算

感謝你的閱讀，歡迎給出建議，以一句歌詞作為結束。

“勞斯難面對，卻跟她勾過手指；萊斯，偏偏那樣癡” —— 黃偉文《勞斯·萊斯》

參考

[1] https://eprint.iacr.org/2004/331.pdf

[2] https://crypto.stanford.edu/~dabo/cs255/lectures/PRP-PRF.pdf

[3] https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_5.pdf