郁　昱， 李祥學(xué)

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

基于單向函數(shù)的偽隨機產(chǎn)生器與通用單向哈希函數(shù)

郁昱1， 李祥學(xué)2,3

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

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

關(guān)鍵詞:密碼學(xué);單向函數(shù);偽隨機產(chǎn)生器;通用單向哈希函數(shù)

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

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

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

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

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

本文將回顧基于單向函數(shù)的偽隨機產(chǎn)生器研究現(xiàn)狀，介紹偽隨機產(chǎn)生器的最新研究進(jìn)展。另外，單向函數(shù)蘊涵通用單向哈希函數(shù)(universal one-way Hash function, UOWHF)是現(xiàn)代密碼學(xué)最核心的基礎(chǔ)理論之一，關(guān)于通用單向哈希函數(shù)可以基于任意單向函數(shù)構(gòu)造而來的最主要結(jié)論是由Rompel給出的。本文還將回顧通用單向哈希函數(shù)研究現(xiàn)狀，介紹通用單向哈希函數(shù)最新研究進(jìn)展，對通用單向哈希函數(shù)設(shè)計方法給出系統(tǒng)性闡述。

1相關(guān)概念

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

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

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

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

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

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

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

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是一個單向函數(shù)如果存在某個可忽略函數(shù)ε(n)使得函數(shù)f是ε(n)困難的。

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

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

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

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

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

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

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

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

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

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

定義7[通用單向哈希函數(shù)][12]令

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

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

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

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

為簡潔起見，經(jīng)常使用

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

表示{Gn}。

2偽隨機產(chǎn)生器研究現(xiàn)狀

2.1基于特殊單向函數(shù)的PRG構(gòu)造

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

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

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

其中

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

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

(1)

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

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

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

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

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

2.2基于任意單向函數(shù)的PRG構(gòu)造

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

2.3基于規(guī)則單向函數(shù)的PRG研究最新進(jìn)展

郁昱等[22]重新考慮了基于規(guī)則單向函數(shù)構(gòu)造偽隨機產(chǎn)生器的問題，并設(shè)計了下述偽隨機產(chǎn)生器。

2.3.1基于已知規(guī)則單向函數(shù)的PRG

郁昱等人使用三次提取技術(shù)[26]可以得到下述的典型偽隨機產(chǎn)生器構(gòu)造。

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

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

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

2.3.2基于未知規(guī)則單向函數(shù)的PRG

郁昱等人也給出了一個不依賴于單向函數(shù)f規(guī)則度的構(gòu)造偽隨機產(chǎn)生器的新方法。該方法主要包括以下幾個步驟。

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

f: {0,1}n→Y，

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

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

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

2.4基于弱規(guī)則單向函數(shù)的偽隨機產(chǎn)生器

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

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

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

Y1，Y2，…，Yn,

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

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

2.4.1一個引理

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

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

2.4.2一類更廣的單向函數(shù)

郁昱等人引入了弱規(guī)則(weakly-regular)單向函數(shù)的概念?？紤]任意單向函數(shù)

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

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

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

2.4.3基于弱規(guī)則單向函數(shù)的PRG

文獻(xiàn)[11]構(gòu)造了一個偽隨機產(chǎn)生器，構(gòu)造過程中只需要使用到弱規(guī)則單向函數(shù)中c的知識，而不需要max和。

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

2.4.4幾乎線性種子長度PRG

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

但是，在郁昱等人的構(gòu)造中，缺少所使用函數(shù)的規(guī)則結(jié)構(gòu)和那些可忽略部分Ymax+1,…,Yn進(jìn)一步使分析變復(fù)雜了，他們給出了一個直觀的、結(jié)構(gòu)化的證明。

2.4.5關(guān)于有效性、可行性和局限性

從應(yīng)用的角度看, 已知規(guī)則單向函數(shù)從以下幾方面來說也許已經(jīng)足夠了。

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

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

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

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

3通用單向哈希函數(shù)研究

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

3.1基于任意單向函數(shù)的通用單向哈希函數(shù)

3.2基于特殊單向函數(shù)的通用單向哈希函數(shù)

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

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

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

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

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

表1　現(xiàn)有通用哈希函數(shù)構(gòu)造總結(jié)對比

4.3通用單向哈希函數(shù)研究最新進(jìn)展

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

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

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

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

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

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

參考文獻(xiàn)

[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.

[責(zé)任編輯:陳文學(xué)]

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

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

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

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

文獻(xiàn)標(biāo)識碼：A

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