基于單向函數的偽隨機產生器與通用單向哈希函數

郁　昱， 李祥學

(1.上海交通大學 計算機科學與工程系, 上海 200240;2.華東師范大學 計算機科學與技術系, 上海 200241;3.西安郵電大學 無線網絡安全技術國家工程實驗室, 陜西 西安 710121)

基于單向函數的偽隨機產生器與通用單向哈希函數

郁昱1， 李祥學2,3

(1.上海交通大學 計算機科學與工程系, 上海 200240;2.華東師范大學 計算機科學與技術系, 上海 200241;3.西安郵電大學 無線網絡安全技術國家工程實驗室, 陜西 西安 710121)

摘要:重點回顧基于單向函數的偽隨機產生器，以及通用單向哈希函數的研究現狀，介紹相關研究的最新進展，并對通用單向哈希函數設計方法給出系統性闡述。單向函數蘊涵偽隨機產生器是密碼學中的基礎問題，是現代密碼學的基礎。單向函數可以用來構造偽隨機產生器進而構成流密碼算法，或是在偽隨機產生器的基礎上進一步構造偽隨機函數和偽隨機置換從而用作分組加密算法。隨機迭代技術被提出并經精練后，可用于基于規則單向函數的偽隨機產生器設計。單向函數蘊涵通用單向哈希函數是現代密碼學最核心的基礎理論之一。 關于通用單向哈希函數可以基于任意單向函數構造而來。通用單向哈希函數的應用包括基于最小假設的數字簽名、Cramer-Shoup加密體制、統計隱藏承諾體制等。

關鍵詞:密碼學;單向函數;偽隨機產生器;通用單向哈希函數

在現代密碼學中，密碼方案的設計建立在合法參與者與敵手之間計算復雜度的差異之上:對于合法的參與者，算法是可以高效執行的;對于非法參與者，算法總是計算不可行的。單向函數(one-way function,OWF)正是一類如此定義的函數，它們易于求解，但難于求逆。單向函數與隨機性理論是現代密碼學的主要理論基礎之一，幾乎所有密碼機制的實現都需要許多“高質量的隨機性”。以較低代價生成、交換和共享大量的“高質量的隨機比特”是密碼學的重要研究內容。其典型研究可追溯至Goldreich、Goldwasser、Micali、Luby、Rackoff等著名學者的早期工作。

單向函數的存在性是密碼學的最基本假設，也是絕大多數對稱密碼學(symmetric-key cryptography)算法的充分必要條件。作為一個計算復雜性問題，單向函數可以用來構造偽隨機產生器(pseudorandom generator,PRG)進而構成流密碼(stream cipher)算法，或是在偽隨機產生器的基礎上進一步構造偽隨機函數(pseudorandom functions)和偽隨機置換(pseudorandom permutation),從而用作分組加密(block cipher)算法。現有的基于單向函數的偽隨機產生器構造存在著構造復雜、種子長度超線性和證明規約松散等問題，使得這些構造僅限于理論研究價值，不具備實際的應用價值。

單向函數蘊涵偽隨機產生器是密碼學中的核心問題之一[1]，在此基礎上發展了現代密碼學。該問題最早可以回溯到上世紀80年代早期Blum、Micali[2]和Yao[3]分別獨立發現的結論：一個PRG(通常稱之為BMY產生器)可以從一個單向置換高效地構造出來。換言之，給定一個關于n比特輸入的單向置換f和它的硬核謂詞(hardcore predicate)hc(比如Goldreich和Levin的構造[4]),只需要調用f一次就可以得到一個偽隨機產生器

g:x→ (f(x),hc(x))，

其延展度(stretch)為Ωlog(n)，并可通過重復迭代技術推廣至任意延展度。這可由一個混合論斷(hybrid argument)得到證明。然而,BMY產生器無法直接應用到一個任意的單向函數，因為f輸出的熵可能太小而無法安全地用于之后的迭代過程。

本文將回顧基于單向函數的偽隨機產生器研究現狀，介紹偽隨機產生器的最新研究進展。另外，單向函數蘊涵通用單向哈希函數(universal one-way Hash function, UOWHF)是現代密碼學最核心的基礎理論之一，關于通用單向哈希函數可以基于任意單向函數構造而來的最主要結論是由Rompel給出的。本文還將回顧通用單向哈希函數研究現狀，介紹通用單向哈希函數最新研究進展，對通用單向哈希函數設計方法給出系統性闡述。

1相關概念

定義1[通用哈希函數(universal Hash functions)][5-8]一個函數類(family)

稱為一個通用哈希類(universal Hash family),如果對于任意的x1≠x2∈{0,1}n,總有

Prh←H[h(x1)=h(x2)]≤2-l。

定義2[兩兩獨立哈希(pairwise independent hashing)]一個函數類

稱為兩兩獨立的, 如果對于任意的v∈{0,1}2m、任意的x1≠x2∈{0,1}n總有

等價地，(H(X1),H(X2))與U2m同分布，其中H是H上的均勻分布。眾所周知，存在可有效計算的描述長度為Θ(n+m)的兩兩獨立哈希函數類。

定義3[單向函數(universalHashfunctions)][9-10]一個函數

f: {0,1}n→ {0,1}l(n)

是(t(n),ε(n))單向的,如果f是多項式時間可計算的,且對運行時間為t(n)的任意概率算法A,總有

Pry←f(Un)[A(1n,y)∈f-1(y)]≤ε(n)。

如果ε(n)=1/t(n),則稱f是ε(n)困難的。f是一個單向函數如果存在某個可忽略函數ε(n)使得函數f是ε(n)困難的。

定義4[規則函數(regularfunctions)]一個函數f是α規則的，如果存在一個整數函數α(稱之為規則度函數)，使得對于每個n∈和x∈{0,1}n,總有|f-1(f(x))|=α(n)。特別地，f是已知規則的,如果α是多項式時間可計算的;反之,則稱為是未知規則的。f是已知規則(未知規則)單向函數如果f是具有已知規則度(未知規則度)的單向函數。

定義5[偽隨機產生器(pseudorandomgenerators)][2-3]一個函數

g: {0,1}n→ {0,1}l(n)(l(n)>n)

是一個(t(n),ε(n))安全的偽隨機產生器，如果g是多項式時間可計算的,且

CDt(n)(g(1n,Un),Ul(n))≤ε(n)。

其中(l(n)-n)是g的延展度,經常會將1n從g的參數列表中略去。稱g是一個偽隨機產生器,如果1/t(n)與ε(n)均是可忽略的。

定義6[弱規則(weakly-regular)單向函數][11]考慮任意單向函數

f: {0,1}n→ {0,1}l,

其值域分成集合Y1,Y2,…,Yn,其中每個Yi定義為

|f-1(y)|表示y的原像個數。稱f是弱規則的，如果存在一個整數函數max=max(n)使得Ymax是一個顯著部分(noticeableportion) n-c,其中c為一個常量,且Ymax+1,…,Yn之和所占比例是可忽略的(n)。注意到規則單向函數是弱規則單向函數的一個特例：c=0,(n)=0，max(·)為任意函數(不一定是可有效計算的)。

定義7[通用單向哈希函數][12]令

Gn={gu: {0,1}l(n)→ {0,1}l(n)-s(n),

u∈{0,1}q(n),l∈poly},

稱函數類序列G={Gn}是一個(t(n),ε(n))-通用單向哈希函數，如果對每個n∈,u∈{0,1}q(n),x∈{0,1}l(n),總是可以在多項式時間內計算gu(x)，且對于每個運行時間為t(n)的概率算法A,總有

gu(x)=gu(x′)]≤ε(n)。

為簡潔起見，經常使用

G={gu: {0,1}l→ {0,1}l-s,u∈{0,1}q}

表示{Gn}。

2偽隨機產生器研究現狀

2.1基于特殊單向函數的PRG構造

關于PRG構造的一個研究路線是使用具有特殊結構的單向函數來設計有效的PRG。早在1982年，Blum、Micali[2]與Yao[3]就分別獨立地引入了PRG的概念，他們還觀察到可以由單向置換(one-waypermutations,OWPs)高效地構造偽隨機產生器。換言之，給定一個單向置換f和它的硬核函數(hardcore function)hc(比如由Goldreich與Levin定義的硬核函數[4]), 調用函數f一次就可以得到一個偽隨機產生器g(x) = (f(x),hc(x))，其延展度(stretch，即該偽隨機產生器的輸入輸出長度之差)為Ωlog(n)比特。基于混合論斷(hybrid argument), 重復迭代技巧就可以得到任意長的延展度

gl(x)=(hc(x),hc(f1(x)),

…,hc(fl(x)),…)。

其中

我們經常將上述偽隨機產生器稱為BMY產生器,它具有簡單、最優種子長度、最小單向函數調用次數等優點。Levin[13]注意到這里的函數f不必要一定是單向置換,只需要在其自身迭代意義上是單向的就足夠了。然而，一個任意的單向函數并不具備這樣的性質。

我們把一個函數稱為是規則的(regular)，如果該函數的每個像都有相同個數(比如均為α)的原像。進一步，如果α是可從安全參數有效計算的話，則稱該函數為已知規則的(known-regular)；反之，如果α是不能從安全參數有效近似的話，則稱之為未知規則的(unknown-regular)。基于已知規則單向函數f，Goldreich、Krawczyk與Luby[14]推廣了BMY產生器：通過迭代使用該單向函數、并在每兩次迭代使用之間應用k-對獨立哈希的技巧得到了一個在已知規則單向函數情況下種子長度為O(n3)的偽隨機產生器。后來，Goldreich在他的著作[10]中給出了一個更為高效(事實上是接近最優)的基于已知規則單向函數的偽隨機產生器構造：在具體安全意義下，該構造只需要調用一次單向函數即可(在一般意義下為ω(1)次)。這一構造被隱式地包含在許多HILL型的PRG設計中[15-16]。 文獻[14]中使用的技巧通常被稱為隨機迭代方法(randomized iterate)。Haitner、Harnik與Reingold[17]對該技巧加以提煉，即

(1)

他們將該構造推廣到可以適用于未知規則單向函數，且相應的種子長度縮短為O(nlogn)。 通俗地講，隨機迭代方法沿襲了文獻[14]中的思路，并在每兩次調用f之間使用一個隨機的、兩兩獨立的哈希函數hi，即

f(hi-1(fi-1(x;h1,…,hi-2))),i≥2。

此處關鍵是“最后一個迭代是難于求逆的(hard-to-invert)”[18]。當應用到hi-1(fi-1;h1,…,hi-2)后，函數f是難于求逆的,即使h1,…,hi-2,hi-1是公開的。運行該迭代O(n/logn)次、對每個迭代輸出Ω(logn)個硬核比特就可以得到一個偽隨機產生器,這需要的種子長度為O(n2/logn),使用Nisan的有界空間產生器(bounded-space generator[19])等去隨機化技巧(derandomization techniques)可以進一步將該種子長度縮短至O(nlogn)。隨機迭代技術能夠達到單向函數調用次數的下界(文獻[10]指出，函數調用次數的下界Ω(n/logn)同樣適用于未知規則單向函數)。我們關心，是否任意高效PRG構造都能同時達到線性種子長度和Ω(n/logn)次單向函數調用呢？

文獻[18]進一步對這個偽隨機產生器采取了去隨機化操作：使用一個程度為O(nlogn)的種子從受限空間產生器(bounded space generator,比如Nisan產生器[20])生成所有哈希函數。隨機迭代技術被主要應用于基于規則單向函數的PRG構造，文獻[18]也介紹了其他應用，包括基于任意指數困難規則單向函數(exponentially hard regular)的線性種子長度PRG,基于任意指數困難規則單向函數(exponentially hard regular)的O(n2)種子長度PRG,基于任意單向函數的O(n7)種子長度PRG, 以及規則弱單向函數(regular weakly-OWF)的困難性放大(hardness amplification)。

Dedic、Harnik與Reyzin[21]證明了可以減小秘密隨機性的數量以得到更緊的規約,亦即,如果一個規則單向函數f有2k個像，那么，需要的秘密隨機性的數量就是k(而不是n比特)。 郁昱等[22]進一步將基于任意規則單向函數的PRG的種子長度減小到O(ω(1)n)，其中ω(1)是可有效計算的。

2.2基于任意單向函數的PRG構造

Hastad、Impagliazzo、Levin與Luby等學者(HILL)關于“基于任意單向函數的偽隨機產生器構造”學術工作[1]證明了“單向函數(OWFs)蘊涵偽隨機產生器(PRGs)”，這一結論是現代密碼學的基礎理論之一。他們在文獻[1]中提出的許多工具和概念,比如偽隨機熵(pseudo-entropy,[23-24])和剩余哈希引理(leftoverHashlemma)，在包括抗泄漏密碼(leakage-resilientcryptography)在內的其他密碼學研究領域均有廣泛應用。

2.3基于規則單向函數的PRG研究最新進展

郁昱等[22]重新考慮了基于規則單向函數構造偽隨機產生器的問題，并設計了下述偽隨機產生器。

2.3.1基于已知規則單向函數的PRG

郁昱等人使用三次提取技術[26]可以得到下述的典型偽隨機產生器構造。

(1) 基于f(X)的隨機性提取(randomnessextraction)。由于f(X)的最小熵為n-k,我們可以提取長度接近n-k的統計隨機比特串。

(2) 基于X的隨機提取。給定任意y=f(X),隨機變量X有最小熵k,一次我們又可提取長度為k的統計隨機比特串。

(3) 基于X的偽隨機提取。經過第二次隨機提取后，在給定f(X)條件下隨機變量X的不可預測偽熵最多減少k。換言之，熵鏈原理(entropychainrule)保證了剩余的log(1/ε)比特，因此，可以使用Goldreich-Levin硬核函數[4]提取O(log(1/ε))比特。

2.3.2基于未知規則單向函數的PRG

郁昱等人也給出了一個不依賴于單向函數f規則度的構造偽隨機產生器的新方法。該方法主要包括以下幾個步驟。

(1) 變換為已知規則度。這里的關鍵思想是把任意未知規則單向函數變換為另一個特定定義域上的已知規則單向函數，亦即,對于一個保持長度(length-preserving)的未知規則(t,ε)單向函數

f: {0,1}n→Y，

其中Y?{0,1}n是f的值域，定義函數

我們一般稱之為Z型PRG[25]。給定輸入分布Z，該偽隨機產生器輸出與(Z,Us)計算上不區分的(Z′,Us)，這里Z=(Y,R)，延展度s=O(log(1/ε))。注意到如果Z為U2n，則我們得到一個標準的PRG。

以上步驟可以改進Haitner、Harnik和Reingold[18]的使用種子長度O(nlogn)、函數調用次數O(n/logn)的隨機迭代方法 (Crypto 2006)。

2.4基于弱規則單向函數的偽隨機產生器

與HILL方法相比，隨機迭代技術具有更短甚至幾乎線性的種子長度和更緊的規約等優點，也能適用于幾乎規則(almost-regular)單向函數。關于這一個推廣是不難看出的(文獻[17,22]中有隱式描述)。類似地，文獻[11]介紹的構造也只需要“弱幾乎規則單向函數(weakly-almost-regular one-way function)”，而幾乎規則單向函數只是這個概念的一種特殊情況。

但是，隨機重復方法是否可以進一步推廣應用到比規則單向函數范圍更廣的單向函數呢？在此之前這還是一個公開問題，文獻[11]則給出了明確的答案。作者引入了一類更廣的單向函數，并使用隨機迭代技術基于這種函數構造了一個種子長度為O(nlogn)、具有更緊規則的偽隨機產生器。

文獻[11]提出了一個稱為弱規則單向函數的更為一般化的概念。具體講,考慮一個單向函數，其值域分成集合

Y1，Y2，…，Yn,

Yi={y:2i-1≤f-1(y)<2i}。

我們稱f是弱規則的如果存在一個(不必是可有效計算的)max使得Ymax構成一個顯著的部分(比如n-c,c為常數),且Ymax+1,…,Yn之和僅為可忽略的。規則單向函數是弱規則單向函數的一種特殊情況：c=0,(n)=0，max(·)為不必可有效計算的任意函數。

2.4.1一個引理

郁昱等人首先從文獻[18]中凝練了一個引理：如果一個算法以可忽略的概率針對均勻采樣的挑戰，贏得一個單項游戲(比如哈希函數的求逆),那么,當挑戰是服從對數Rényi熵缺陷(logarithmicRényientropydeficiency)分布采樣時，該算法的獲勝概率也不會比可忽略優勢更好。這里，集合W上的隨機變量W的Rényi熵缺陷指的是UW的熵與W的熵之差：log|W|-H2(W), 其中UW表示W上的均勻分布，H2(W)是W的Rényi熵。

事實上，這個引理在抗泄漏密碼中是隱式存在的。在其他的研究[27-29]中也有類似結論,比如針對不可區分性應用的雙向游戲或者隨機性是從略受污染的最小熵源采樣的研究。將這個引理應用到文獻[18]就可以得到該文中的關鍵引理的更為簡單的證明：作用在規則單向函數上的任意第k次迭代是求逆困難的。其主要原因在于：即使在給定哈希函數的條件下，yk有足夠大的Rényi熵，該熵只是在對數意義下略小于理想情況(即yk是f的值域上的均勻分布，并獨立于哈希函數,由于單向性的原因這是求逆困難的)。

2.4.2一類更廣的單向函數

郁昱等人引入了弱規則(weakly-regular)單向函數的概念。考慮任意單向函數

f: {0,1}n→ {0,1}l,

其值域分成集合Y1,…,Yn,其中每個Yi定義為

|f-1(y)|表示y的原像個數。稱f是弱規則的，如果存在一個整數函數max = max(n)使得Ymax是一個顯著部分(noticeable portion)n-c,其中c為一個常量, 且Ymax+1,…,Yn之和所占比例是可忽略的(n)。注意到規則單向函數是弱規則單向函數的一個特例：c=0,(n)=0，max(·)為任意函數(不一定是可有效計算的)。

2.4.3基于弱規則單向函數的PRG

文獻[11]構造了一個偽隨機產生器，構造過程中只需要使用到弱規則單向函數中c的知識，而不需要max和。

通俗地講，如式(1)所示,主要想法是在第k輪迭代中，在yk∈Ymax條件下，針對給定哈希函數隨機變量yk的Rényi熵接近于理想情況，即f(Un)以顯著的概率并獨立于哈希函數地撞入集合Ymax,而這是求逆困難的。

2.4.4幾乎線性種子長度PRG

總體上看，我們的技巧與文獻[18]引入的規則弱單向函數的困難性放大比較類似。讀者需要注意,不要混淆弱規則(weakly-regular)與弱單向(weakly-one-way)的概念：前者的“弱”描述的是規則度(即在一個顯著比例的意義上是規則的)，后者則用于單向性(即在一個顯著比例的意義上求逆困難的[3])。 通俗講,對于任意求逆算法A,一個弱單向函數有一個集合——A的失敗集(failing-set)，A在這個集合上總是失敗的。這樣，充分多次迭代就必定會撞入每個這樣的失敗集以產生一個強單向函數(strongly-one-way function)，使得在一個壓倒性的比例上是求逆困難的。

但是，在郁昱等人的構造中，缺少所使用函數的規則結構和那些可忽略部分Ymax+1,…,Yn進一步使分析變復雜了，他們給出了一個直觀的、結構化的證明。

2.4.5關于有效性、可行性和局限性

從應用的角度看, 已知規則單向函數從以下幾方面來說也許已經足夠了。

(1) 如果一個單向函數的表現像一個隨機函數的話,那么，它是已知(幾乎)規則的。換言之, 絕大多數函數是已知幾乎規則的。

(2) 在實際應用中,許多單向函數是已知規則的甚至是1-1的。 比如,Goldreich、Levin和Nisan[31]證明了1-1單向函數可以由諸如RSA和DLP這樣具體的困難問題設計出來。

眾所周知[10,22]，可以從已知(幾乎)規則單向函數幾乎最優地構造出PRG：種子長度O(nω(1))，非適應性地(non-adaptive)調用單向函數O(ω(1))次，這里ω(1)是任意可有效計算的超常數。

郁昱等人的研究切入點選擇在中間階段：引入了弱規則單向函數的概念，它位于規則單向函數和任意單向函數之間，給出了一個種子長度為O(nlogn)的PRG設計，并使用了更緊的安全規約。他們還給出關于弱單向函數與任意單向函數之間區別的討論。

3通用單向哈希函數研究

稱一個壓縮哈希函數類G是通用單向的(universalone-way)，如果給定一個隨機函數g∈G和一個隨機的(等價地,任意預先固定的)輸入x,對任意有效算法要找到任意x′≠x使得g(x)=g(x′)是不可行的[32]。單向函數蘊涵通用單向哈希函數(universal one-way Hash functions, UOWHFs)[33]是現代密碼學最核心的基礎理論之一。通用單向哈希函數的應用包括基于最小假設(單向函數)的數字簽名[34]、Cramer-Shoup加密體制[35]和統計隱藏承諾體制(statistically hiding commitment scheme)[36-37]等。

3.1基于任意單向函數的通用單向哈希函數

3.2基于特殊單向函數的通用單向哈希函數

關于通用單向哈希函數研究的另一條路線是利用具有特殊結構的單向函數來構造更為高效的(甚至接近實用)的通用單向哈希函數。Naor和Yung提出了一種非常靈活的先哈希再截斷(Hash-then-truncate)的UOWHF構造方法，其秘鑰和輸出長度為Θ(n)，且只需要一次調用所使用的單向置換(one-way permutation)。但是，對稍弱一些的1-1單向函數，他們只給出一個非常復雜的構造[12]。

De Santis和Yung[41]提出了一個基于任意1-1單向函數f: {0,1}n→ {0,1}l的改進設計,即

其中“°”表示函數合成運算, 每個H表示一個兩兩獨立的哈希函數(將i比特壓縮為i-1比特)構成的函數類。雖然G1-1具有線性輸出長度和僅需一次函數調用的優點，但它需要秘鑰長度O(ω(logn)n)(易見G1-1需要秘鑰長度O(l(l-n)),但由于每個1-1單向函數蘊涵另一個1-1(除了一個可忽略的輸入部分之外)的單向函數

f′: {0,1}n′∈Θ(n)→ {0,1}n′+ω(log n),

因此,文獻[12,41]中構造的秘鑰長度可以壓縮至O(ω(logn)n)。

表1　現有通用哈希函數構造總結對比

4.3通用單向哈希函數研究最新進展

文獻[44]研究了通用單向哈希函數設計，并給出了下述一系列構造。前兩個構造能夠同時達到最優參數且為安全性保持的(security-preserving)：第一個通用單向哈希函數安全性與相應的單向函數是完全一樣的，第二個構造的安全性是相應的單向函數的平方根。第三個構造的參數也是幾乎最優的(僅相差一個任意小的超常數因子ω(1),比如log log logn甚至更小)。因此,這3個構造均是對相應的已知構造的改進。第四個構造則考慮了規則單向函數之外的情況，即文獻[11]中引入的弱規則單向函數，并給出了最優輸出長度Θ(n)和秘鑰長度O(nlogn)的通用單向哈希函數構造。

(1) 對于任意1-1單向函數,我們構造了一個最優通用單向哈希函數類，秘鑰長度和輸出長度為Θ(n)且僅需一次單向函數調用。

(2) 對于任意已知困難度(known hardness)的已知規則單向函數，我們給出了另一個最優通用單向哈希函數構造，秘鑰長度和輸出長度為Θ(n)且僅需一次單向函數調用。

(3) 對任意已知規則單向函數，我們給出了一個通用單向哈希函數構造，秘鑰長度和輸出長度為O(ω(1)n)，以及ω(1)次非適應性函數調用。

(4) 對任意在定義域的顯著部分(noticeable fraction,比如n-c，這里c為常數)弱未知規則單向函數f[11],我們給出了一個通用單向哈希函數構造，秘鑰長度為O(nlogn)、輸出長度為Θ(n)。

文獻[44]的結論進一步展示了通用單向哈希函數與偽隨機產生器之間的黑盒對偶性(black-box duality)[37,40,45]。首先,文獻[44]抽象出了一個關于通用哈希的引理，該引理隱含在已有文獻[28-29,33,37,39]之中，它在通用單向哈希函數構造中的作用與剩余哈希引理(leftover Hash lemma)在偽隨機產生器構造中的作用是對等的。其次,這里的構造2和構造3匹配了基于已知規則單向函數的偽隨機產生器構造中的最好結果[22],即種子長度O(ω(1)n)(如果已知單向函數的困難度的話則為Θ(n))。此外,基于同一類單向函數，構造4與文獻[11]中偽隨機產生器構造相對應(種子長度、秘鑰長度為O(nlogn))。或許最為有趣的是,構造1與偽隨機產生器情況下的非對稱性：基于1-1單向函數，我們還不知道如何構造一個線性種子長度的偽隨機產生器。

參考文獻

[1]HASTAD J, IMPAGLIAZZO R, LEVIN L A, et al. Construction of a pseudo-random generator from any one-way function[J/OL]. SIAM Journal on Computing, 1995,28(4):12-24[2015-11-12].http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.7957.

[2]BLUM M, MICALI S. How to generate cryptographically strong sequences of pseudorandom bits[J/OL]. SIAM Journal on Computing, 1984,13(4):850-864[2015-11-12].http://epubs.siam.org/doi/pdf/10.1137/0213053.

[3]YAO A C C. Theory and applications of trapdoor functions (extended abstract)[C]//Proceedings of the 23rd IEEE Symposium on Foundation of Computer Science. Chicago:IEEE,1982:80-91.

[4]GOLDREICH O, LEVIN L A. A hard-core predicate for all one-way functions[C]//STOC’89 Proceedings of the twenty-first annual ACM symposium on Theory of computing. New York: ACM,1989:25-32.DOI:10.1145/73007.73010.

[5]DODIS Y, ELBAZ A, OLIVEIRA R, et al.. Improved randomness extraction from two independent sources[C]//Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Berlin:Springer-Verlag, 2004:334-344.DOI:10.1007/978-3-540-27821-4_30.

[6]CARTER J L, WEGMAN M N. Universal classes of Hash functions[J]. Journal of Computer and System Sciences, 1979,18(2):143-154.

[7]LEE C J, LU C J, TSAI S C, et al. Extracting randomness from multiple independent sources[J]. IEEE Transactions on Information Theory, 2005,51(6):2224-2227.

[8]STINSON D R. Universal Hash families and the leftover Hash lemma, and applications to cryptography and computing[J/OL]. Journal of Combinatorial Mathematics and Combinatorial Computing, 2002,42:3-31[2015-11-15].http://cacr.uwaterloo.ca/～dstinson/papers/leftoverhash.pdf.

[9]GOLDREICH O. Three XOR-lemmas: an exposition[C]//Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation.Berlin: Springer-Verlag, 2011:248-272.DOI:10.1007/978-3-642-22670-0_22.

[10] GOLDREICH O. Foundations of Cryptography: Basic Tools[M/OL]. New York: Cambridge University Press, 2001[2015-11-13].http://office-for.com/lib/etc/crypto_2001.pdf.

[11] YU Y, GU D, LI X, et al. The randomized iterate, revisited-almost linear seed length PRGs from a broader class of one-way functions[C/OL]//Theory of Cryptography:12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I. Berlin:International Association for Cryptologic Research, 2015:7-35[2015-11-26].http://link.springer.com/chapter/10.1007/978-3-662-46494-6_2.

[12] NAOR M, YUNG M. Universal one-way Hash functions and their cryptographic applications[C]//JOHNSON D S. STOC’89 Proceedings of the twenty-first annual ACM symposium on Theory of computing.New York: ACM, 1989:33-43. DOI:10.1145/73007.73011.

[13] LEVIN L A. One-way functions and pseudorandom generators[J]. Combinatorica, 1987:7(4):357-363.

[14] GOLDREICH O, KRAWCZYK H, LUBY M. On the existence of pseudorandom generators[C]//Advances in Cryptology: CRYPTO’88. New York: Springer-Verlag,1990:146-162.DOI:10.1007/0-387-34799-2_12.

[15] HAITNER I, REINGOLD O, VADHAN S P. Efficiency improvements in constructing pseudorandom generators from one-way functions[C]//STOC’10 Proceedings of the forty-second ACM symposium on Theory of computing. New York: ACM, 2010:437-446.DOI:10.1145/1806689.1806750.

[16] HOLENSTEIN T. Pseudorandom generators from one-way functions: A simple construction for any hardness[C]//Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings. Berlin:Springer-Verlag, 2006:443-461.DOI:10.1007/11681878_23

[17] HAITNER I, HARNIK D, REINGOLD O. On the power of the randomized iterate[J/OL]. SIAM Journal on Computing, 2011, 40(6):1486-1528[2015-11-20].http://epubs.siam.org/doi/abs/10.1137/080721820.

[18] HAITNER I, HARNIK D, REINGOLD O. On the power of the randomized iterate[C]//Advances in Cryptology-CRYPTO 2006: 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006. Proceedings. Berlin:Springer-Verlag, 2006: 22-40.DOI:10.1007/11818175_2.

[19] HOLENSTEIN T, SINHA M. Constructing a pseudorandom generator requires an almost linear number of calls[C]//2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS). New Brunswich, NJ: IEEE, 2012: 698-707. DOI:10.1109/FOCS.2012.51.

[20] NISAN N.Pseudorandom generators for space-bounded computation[J]. Combinatorica, 1992,12(4):449-461.DOI:10.1007/BF01305237.

[21] DEDIC N, HARNIK D, REYZIN L. Saving private randomness in one-way functions and pseudorandom generators[C]//Theory of Cryptography:Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008. Proceedings. Berlin: Springer-Verlag, 2008: 607-625.DOI:10.1007/978-3-540-78524-8_33.

[22] YU Y, LI X X, WENG J. Pseudorandom generators from regular one-way functions: new constructions with improved parameters[C]//Advances in Cryptology-ASIACRYPT 2013: 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part II. Berlin: Springer-Verlag, 2013:261-279.DOI:10.1007/978-3-642-42045-0_14.

[23] BARAK B, SHALTIEL R, WIGDERSON A. Computational analogues of entropy[C]//Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques: 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003. Proceedings. Berlin: Springer-Verlag, 2003:200-215.DOI:10.1007/978-3-540-45198-3_18.

[24] HSIAO C Y, LU C J, REYZIN L. Conditional computational entropy, or toward separating pseudoentropy from compressibility[C/OL]//Advances in Cryptology-EUROCRYPT 2007: 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007. Proceedings. Berlin: Springer-Verlag, 2007: 169-186[2015-11-20].http://link.springer.com/chapter/10.1007/978-3-540-72540-4_10.

[25] VADHAN S P, ZHENG C J. Characterizing pseudoentropy and simplifying pseudorandom generator constructions[C]//STOC’12 Proceedings of the forty-fourth annual ACM symposium on Theory of computing. New York: ACM, 2012:817-836. DOI:10.1145/2213977.2214051.

[26] NISAN N, ZUCKERMAN D. Randomness is linear in space[J]. Journal of Computer and System Sciences, 1996, 52(1):43-53.

[27] BARAK B, DODIS Y, KRAWCZYK H, et al. Leftover Hash lemma, revisited[C/OL]//Advances in Cryptology - CRYPTO 2011:31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings. Berlin: Springer-Verlag, 2011: 1-20[2015-11-20].http://link.springer.com/chapter/10.1007/978-3-642-22792-9_1.

[28] DODIS Y, PIETRZAK K, WICHS D. Key derivation without entropy waste[C/OL]//dvances in Cryptology - EUROCRYPT 2014:33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings. Berlin: Springer-Verlag, 2014:93-110[2015-11-20].http://link.springer.com/chapter/10.1007/978-3-642-55220-5_6.

[29] DODIS Y, YU Y. Overcoming weak expectations[C/OL]//Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings.Berlin: Springer-Verlag,2013:1-22[2015-11-23].http://link.springer.com/chapter/10.1007/978-3-642-36594-2_1.

[30] IMPAGLIAZZO R, NISAN N, WIGDERSON A. Pseudorandomness for network algorithms[C]//STOC’94 Proceedings of the twenty-sixth annual ACM symposium on Theory of computing.New York: ACM, 1994:356-364.DOI:10.1145/195058.195190

[31] GOLDREICH O, LEVIN L A, NISAN N. On constructing 1-1 one-way functions[C/OL]//Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Berlin: Springer-Verlag, 2011:13-25[2015-11-25].http://link.springer.com/chapter/10.1007/978-3-642-22670-0_3.

[32] BARHUM K, HOLENSTEIN T. A cookbook for black-box separations and a recipe for uowhfs[C/OL]//Theory of Cryptography:10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings.Berlin:International Association for Cryptologic Research, 2013:662-679[2015-11-22].http://link.springer.com/chapter/10.1007/978-3-642-36594-2_37.

[33] ROMPEL J. One-way functions are necessary and sufficient for secure signatures[C]//STOC’90 Proceedings of the twenty-second annual ACM symposium on Theory of computing. New York: ACM, 1990:387-394. DOI:10.1145/100216.100269.

[34] GOLDWASSER S, MICALI S, RIVEST R L. A digital signature scheme secure against adaptive chosen-message attacks[J]. SIAM Journal on Computing, 1988, 17(2), 281-308. DOI:10.1137/0217017.

[35] CRAMER R, SHOUP V. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack[J]. SIAM Journal on Computing, 2004, 33(1):167-226. DOI:10.1137/S0097539702403773.

[36] HAITNER I, NGUYEN M H, ONG S J, et al. Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function[J]. SIAM Journal on Computing, 2009, 39(3):1153-1218.DOI:10.1137/080725404.

[37] HAITNER I, REINGOLD O, VADHAN S P, et al. Inaccessible entropy[C]//STOC’09 Proceedings of the forty-first annual ACM symposium on Theory of computing. New York: ACM, 2009:611-620.DOI:10.1145/1536414.1536497.

[38] ROMPEL J T. Techniques for computing with low-independence randomness[D/OL]. USA MA Cambridge: Massachusetts Institute of Technology,1990[2015-11-26].http://dspace.mit.edu/handle/1721.1/7582.

[39] KATZ J, KOO C Y. On constructing universal one-way hash functions from arbitrary one-way functions[EB/OL].[2015-11-10].http://www.iacr.org/cryptodb/data/paper.php?pubkey=12662.

[40] HAITNER I, HOLENSTEIN T, REINGOLD O, et al. Universal one-way hash functions via inaccessible entropy[C]//Advances in Cryptology - EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 - June 3, 2010. Proceedings. Berlin:Springer-Verlag, 2010:616-637. DOI:10.1007/978-3-642-13190-5_31.

[41] SANTIS A D, YUNG M. On the design of provably secure cryptographic Hash functions[C]//Advances in Cryptology — EUROCRYPT ’90:Workshop on the Theory and Application of Cryptographic Techniques Aarhus, Denmark, May 21-24, 1990 Proceedings.Berlin:Springer-Verlag, 1991:412-431.DOI:10.1007/3-540-46877-3_37.

[42] BARHUM K, MAURER U. UOWHFs from OWFs: Trading regularity for efficiency[C]//Progress in Cryptology - LATINCRYPT 2012: 2nd International Conference on Cryptology and Information Security in Latin America, Santiago, Chile, October 7-10, 2012. Proceedings. Berlin:Springer-Verlag, 2012:234-253.DOI:10.1007/978-3-642-33481-8_13.

[43] AMES S, GENNARO R, VENKITASUBRAMANIAM M. The generalized randomized iterate and its application to new efficient constructions of UOWHFs from regular one-way functions[C]//Advances in Cryptology - ASIACRYPT 2012: 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings. Berlin: International Association for Cryptologic Research, 2012:154-171.DOI:10.1007/978-3-642-34961-4_11.

[44] YU Y, GU D, LI X X, et al. (Almost) Optimal Constructions of UOWHFs from 1-to-1, Regular One-way Functions and Beyond[C]//Advances in Cryptology-CRYPTO 2015:35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II. Berlin: International Association for Cryptologic Research, 2015:209-229.DOI:10.1007/978-3-662-48000-7_11.

[45] GENNARO R, GERTNER Y, KATZ J, et al. Bounds on the efficiency of generic cryptographic constructions[J]. SIAM Journal on Computing, 2005, 35(1), 217-246.DOI:10.1137/S0097539704443276.

[責任編輯:陳文學]

One-way function based pseudorandom generator and universal one-way hash function

YU Yu1,LI Xiangxue2,3

(1.Department of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai 200240;2.Department of Computer Science and Technology, East China Normal University, Shanghui 200241;3.National Engineering Laboratory for Wireless Security, Xi’an University of Posts and Telecommunications, Xi’an 710121)

Abstract:A survey is given to revisit the problem of basing pseudorandom generators on one-way functions, and the state of the art on universal one-way hash functions from one-way functions is reviewd.That one-way functions (OWFs) imply pseudorandom generators (PRGs) is one of the central results upon which modern cryptography is successfully founded. “The randomized iterate” technique is originally used and refined in constructing PRGs from regular OWFs. The seminal result that one-way functions (OWF) imply universal one-way hash functions (UOWHFs) constitutes one of the central pieces of modern cryptography. The principle possibility result is that UOWHFs can be based on any OWF. Applications of UOWHFs include basing digital signatures on minimal assumptions (one-way functions), Cramer-Shoup encryption scheme, statistically hiding commitment scheme, etc.

Keywords:cryptology, one-way function, pseudorandom generator, universal one-way Hash function

doi:10.13682/j.issn.2095-6533.2016.02.001

收稿日期：2015-12-25

基金項目：國家自然科學基金資助項目(61472249, 61572192, 61572149)

作者簡介：郁昱(1981-),男，博士，教授，從事密碼學與互聯網安全研究。E-mail:yyuu@sjtu.edu.cn 李祥學(1981-)，男，博士，教授，從事密碼學與互聯網安全研究。E-mail: xxli@cs.ecnu.edu.cn

中圖分類號：TN918.4;TP301.5

文獻標識碼：A

文章編號：2095-6533(2016)02-0001-11