ESC的RO區分有利條件上界

摘 要：文獻[1]給出了一個新的密碼建構ESC，但其未給出ESC的RO區分有利條件上界的詳細證明，本文給出了當對ESC的一系列詢問沒有導致內部碰撞時其輸出位是均勻和獨立的，并由此進而再得到：當f是一個隨機變換函數時，ESC的RO區分有利條件的上界是：；當f是一個隨機置換函數時，ESC的RO區分有利條件上界是：。

關鍵詞：密碼建構；隨機預言機；RO區分有利條件；隨機變換函數；隨機置換函數

DOI：10.16640/j.cnki.37-1222/t.2016.08.200

1 ESC的RO區分有利條件

1.1 基本概念

定義1：一個超級節點指內部狀態相同的節點集。

定義2：ESC吸收字符串P后的前狀態是指那個對字符串P的最后一塊消息只進行了一次異或后得到的整體狀態，我們將用來表示。

定義3：ESC吸收字符串P后的后首狀態是指的是那個用變換（或置換）處理相應前狀態后得到的整體狀態，我們將用表示。

定義4：ESC吸收字符串P后的后尾狀態指的是那個對相應后首狀態進行了消息反饋異或后得到的整體狀態，我們將用來表示。

我們將用，，和來分別表示ESC吸收字符串P后后首狀態的內部狀態，外部狀態和整體狀態；將用，，和來分別表示ESC吸收字符串P后后尾狀態的內部狀態，外部狀態和整體狀態，我們知道ESC吸收同一個字符串P后后首狀態和相應的后尾狀態的內部狀態相同，而且擠壓階段可視為吸收零塊消息，因此后首狀態和相應的后尾狀態相同（調用變換（或置換）函數后）；將用、和來分別表示吸收過程中相鄰的且內部狀態相同的后首狀態、后尾狀態和前狀態，由此可知ESC吸收字符串過程中的整體狀態由這三種整體狀態組成。

定義5：ESC的一對內部碰撞指的是一對不同的字符串P和P，它們被吸收后后尾狀態的內部狀態相等，即。

定義6：一個隨機預言機RO是指接受任意長度的二進制字符串作為輸入然后對每個輸入返回一個無限長度的二進制字符串，即它是一個從到的映射，通過對每個輸入M，均勻和獨立地選取返回值RO（M）中的每個比特值來產生。

我們將用來表示一次調用RO后被截成比特的輸出。ESC對一個輸入消息M的輸出的第j塊為，其中。上面的基礎性質暗示著填充規則必須是海綿遵從[2]的。

1.2 ESC輸出的均勻性和獨立性

定理 1. 若f表示一個隨機變換（或置換）函數和pad表示一個海綿遵從的填充規則，當沒有發生內部碰撞時由對一系列詢問返回的輸出比特是均勻和獨立分布的。

證明. 我們用Q來表示向系統的一系列詢問，用來表示系統對Q的一系列回復。在這情況下，Q是一系列對，并且是一個正整數，（Q）是一系列對 。對于給定的一系列詢問Q，隨機ESC當吸收輸入串和被擠壓時經歷過一些整體狀態 。 我們用表示到實驗過程中的路徑集，即有={X是的一個前綴且X的長度是r的整數倍}，其中。詢問過程不發生內部碰撞意味著 。考慮第i次詢問的第j塊輸出塊，我們將用來表示從第一次詢問到第i-1次詢問和當次詢問先前經歷過（除掉和）的整體狀態集，將用，， 和來分別表示關于的前狀態集合，后首狀態集合，后尾狀態集合和內部狀態集合，要求在輸出塊的產生過程中不發生內部碰撞意味著限制內部狀態的值與內部狀態集合里的值都不相同。當f是一個隨機變換函數時，輸出塊的值必須在狀態集合里，這些值是等概率的。當f是一個隨機置換函數時，由f的可逆性要求必須與所有先前經歷過的后首狀態不同 （除了），即要求是從整體狀態集中來選擇。又因為，所以可以簡化為。因此在兩種情況下對輸出塊在中所有可能的值都是等概率的而且獨立于先前經歷過的外部狀態（消息塊的反饋異或并不影響輸出塊的均勻和獨立分布），所以輸出比特也是均勻和獨立分布的。

1.3 攻擊者的情況

我們考慮一個將區分兩個系統的攻擊者，如圖1所示，左邊的系統是隨機變換（或置換）函數f與ESC E的組合，攻擊者不能直接詢問f但可以詢問E，E將會調用f來構造它的回復，這表示為E[f]，我們用H來表示E[f]的交互交互界面，交互界面H取一個二進制字符串串和一個整數作為輸入，返回一個二進制串， 就是ESC被截成比特的輸出。右邊的系統由一個隨機預言機組成，隨機預言機提供與E[f]相同的交互界面H。當接受輸入后，它返回被截成比特的輸出 。攻擊者交互界面背后的系統不是E[f]就是RO，系統是E[f]還是RO的優先概率均為1/2，攻擊者會向的交互界面H發送詢問，甚至是適應性的，通過連續的詢問的輸出的前比特，在發送完所有詢問后，攻擊者使用系統對詢問的回復來猜測是E[f]還是RO。我們假設攻擊者的計算能力無界限，她可以最大限度的挖掘呈現在詢問回復中的信息。然后我們來限定作為總詢問成本[2]的函數的ESC RO區分有利條件的上界。

1.4 ESC的RO區分有利條件

又由于ESC與文獻[2]中海綿建構不同的是在每次調用完變換（或置換）函數后對外部狀態進行的消息反饋異或，相應后尾狀態和后首狀態的內部狀態相同，屬于同一個超級節點，因此通過最優策略時ESC產生內部碰撞的概率與海綿建構的相同，所以再根據文獻[2]中產生內部碰撞的概率就可推導出以下兩個定理。

參考文獻：

[1]陳偉彬.一個阻止內部碰撞轉狀態碰撞的海綿建構變體[J].科技傳播，2014（06）：149-150.

[2]G.Bertoni，J.Daemen，M.Peeters，and G.Van Assche，Cryptographic sponge functions[OL]，（2012/02/15）[2013/11/30]http：//sponge.noekeon.org/.

[3]Gauravaram，P.，Kelsey，J.，Knudsen，L.R.， Thomsen，S.S.：On hash functions using checksums[J].Int.J.Inf.Secur.vol.9（2），pp.137-151（2010）.

[4]U.Maurer.Indistinguishability of random systems. In Advances in Cryptology—EUROCRYPT 02， volume 2332 of Lecture Notes in Computer Science， pages 110-132. Springer-Verlag，2002.

作者簡介：陳偉彬（1987—），男，廣東汕頭人，碩士研究生，助教，研究方向：密碼學和數論等。