李一鳴, 劉勝利

1.上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系, 上海 200240

2.密碼科學(xué)技術(shù)全國(guó)重點(diǎn)實(shí)驗(yàn)室, 北京 100878

1 前言

偽隨機(jī)函數(shù)(pseudorandom function,PRF)的概念是由Goldreich、Goldwasser 和Micali 在文獻(xiàn)[1]中首次提出的.偽隨機(jī)函數(shù)F:K×X →Y是多項(xiàng)式時(shí)間可計(jì)算且具有偽隨機(jī)特性的確定性函數(shù), 其偽隨機(jī)性要求: 對(duì)于均勻隨機(jī)選取的密鑰k$←?K, 函數(shù)F(k,·) 的計(jì)算結(jié)果與真隨機(jī)函數(shù)的計(jì)算結(jié)果之間計(jì)算不可區(qū)分.我們稱(chēng)描述偽隨機(jī)函數(shù)F的集合K、X和Y分別為偽隨機(jī)函數(shù)的密鑰空間、消息空間和輸出空間, 本文中, 考慮X={0,1}?是長(zhǎng)度為?的比特串集合.部分偽隨機(jī)函數(shù)在計(jì)算時(shí)還需使用到公開(kāi)參數(shù)及相應(yīng)的公開(kāi)參數(shù)生成算法.

作為密碼學(xué)領(lǐng)域的基礎(chǔ)原語(yǔ)之一, 偽隨機(jī)函數(shù)有著非常廣泛的應(yīng)用.偽隨機(jī)函數(shù)結(jié)合Feistel 結(jié)構(gòu)可以構(gòu)造偽隨機(jī)置換.基本的對(duì)稱(chēng)密碼機(jī)制, 如對(duì)稱(chēng)加密、消息認(rèn)證和身份識(shí)別, 都可以基于偽隨機(jī)函數(shù)簡(jiǎn)潔地實(shí)現(xiàn)[1,2].進(jìn)一步地, 偽隨機(jī)函數(shù)也可作為組件構(gòu)造對(duì)稱(chēng)版本的代理重加密和可更新加密[3,4]等高級(jí)對(duì)稱(chēng)密碼方案.在公鑰密碼領(lǐng)域, 偽隨機(jī)函數(shù)被創(chuàng)造性地應(yīng)用于構(gòu)造基于身份的加密、基于屬性的加密、支持任意電路的功能加密以及數(shù)字簽名方案[5–9].在協(xié)議設(shè)計(jì)中, 偽隨機(jī)函數(shù)常用作密鑰導(dǎo)出函數(shù), 從相對(duì)短的密鑰中方便地派生出足夠數(shù)量的高質(zhì)量密鑰.具有擴(kuò)展功能(如可驗(yàn)證、水印) 的偽隨機(jī)函數(shù)還可用于設(shè)計(jì)區(qū)塊鏈協(xié)議、設(shè)計(jì)電子貨幣系統(tǒng)、提供版權(quán)保護(hù)和盜版追蹤等[10–14].除應(yīng)用于密碼方案的設(shè)計(jì)外,偽隨機(jī)函數(shù)還被用于證明計(jì)算復(fù)雜性理論以及學(xué)習(xí)理論的重要結(jié)論[15,16].

偽隨機(jī)函數(shù)具有定義簡(jiǎn)潔、可擴(kuò)展性強(qiáng)、應(yīng)用廣泛等良好特點(diǎn), 自提出至今一直都是對(duì)稱(chēng)密碼領(lǐng)域內(nèi)的一項(xiàng)重要研究?jī)?nèi)容.理論上, 偽隨機(jī)函數(shù)可以基于偽隨機(jī)數(shù)生成器(pseudorandom generator, PRG) 通用構(gòu)造[1,17], 進(jìn)而基于單向函數(shù)構(gòu)造.但是這一黑盒構(gòu)造通常效率較低, 而且通過(guò)這一方法構(gòu)造的偽隨機(jī)函數(shù)方案固有串行結(jié)構(gòu), 很難在淺電路內(nèi)實(shí)現(xiàn)(例如, 文獻(xiàn)[8] 中的偽隨機(jī)函數(shù)的輸入若為n比特, 則其相應(yīng)的電路深度就與n呈線(xiàn)性關(guān)系).一般而言, 串行PRF 無(wú)法在淺電路內(nèi)實(shí)現(xiàn)并不影響其實(shí)用性, 但是如果PRF 可以在淺電路內(nèi)并行實(shí)現(xiàn), 就可以充分利用多處理單元, 以更少的計(jì)算時(shí)間得到計(jì)算結(jié)果.如果PRF 被集成在專(zhuān)門(mén)設(shè)計(jì)的硬件設(shè)備中, 淺電路并行實(shí)現(xiàn)這一特點(diǎn)將會(huì)在實(shí)際應(yīng)用中發(fā)揮極大優(yōu)勢(shì).此外,PRF 經(jīng)常和全同態(tài)運(yùn)算結(jié)合, 應(yīng)用于一些復(fù)雜密碼算法的設(shè)計(jì)中, 如文獻(xiàn)[5–7], 在這種情況下如果PRF電路深度過(guò)大, 會(huì)導(dǎo)致全同態(tài)運(yùn)算的噪聲迅速累積, 影響全同態(tài)運(yùn)算的效率, 進(jìn)而降低所設(shè)計(jì)的密碼算法的效率.因此, 從某些特定應(yīng)用的角度考慮, 在保證安全性的前提下, 設(shè)計(jì)效率更高、并行性更好的偽隨機(jī)函數(shù)方案有著非常重要的意義.

格理論起源于1611 年開(kāi)普勒提出的關(guān)于三維空間中等半徑小球最大堆積密度的猜想, 歷經(jīng)諸多數(shù)學(xué)家的深入研究不斷發(fā)展成熟, 并于上世紀(jì)末被創(chuàng)造性地應(yīng)用于密碼領(lǐng)域.格上有很多問(wèn)題, 如最短向量問(wèn)題、最近向量問(wèn)題等, 被證明是難以求解的, 而且被普遍認(rèn)為具備抵抗量子攻擊的特性, 這使得格困難問(wèn)題廣泛用于后量子密碼方案的設(shè)計(jì).在量子計(jì)算理論以及實(shí)現(xiàn)技術(shù)快速發(fā)展的今天, 基于大整數(shù)分解和離散對(duì)數(shù)求解等傳統(tǒng)數(shù)論困難問(wèn)題的密碼系統(tǒng)的安全性正遭受?chē)?yán)重威脅, 對(duì)于后量子密碼算法研究的重要性和緊迫性更加凸顯.在這一背景下, 對(duì)格密碼的研究有其重要價(jià)值和意義.

基于格困難問(wèn)題設(shè)計(jì)偽隨機(jī)函數(shù)的研究正式開(kāi)啟于2012 年歐密會(huì)上Banerjee、Peikert 和Rosen 發(fā)表的研究成果[18].Banerjeer 等[18]基于容錯(cuò)學(xué)習(xí)(learning with errors, LWE) 這一格困難問(wèn)題構(gòu)造了多個(gè)可證明安全的偽隨機(jī)函數(shù)方案.受啟發(fā)于這一工作, 密碼學(xué)家們基于格困難問(wèn)題設(shè)計(jì)了諸多偽隨機(jī)函數(shù)方案, 并圍繞PRF 的安全性、效率以及并行性等方面進(jìn)行了改進(jìn)[3,8,19–24].此外, 基于格困難問(wèn)題設(shè)計(jì)具備擴(kuò)展功能的偽隨機(jī)函數(shù)也取得了諸多成果, 如具有密鑰同態(tài)性質(zhì)的偽隨機(jī)函數(shù)[3,20,23,25]、約束偽隨機(jī)函數(shù)[26–32]、水印偽隨機(jī)函數(shù)[33–36]、可驗(yàn)證偽隨機(jī)函數(shù)[37–39]等.盡管如此, 對(duì)于格上偽隨機(jī)函數(shù)的研究仍然存在發(fā)展和完善的空間, 無(wú)論是針對(duì)PRF 構(gòu)造方案屬性進(jìn)行優(yōu)化, 還是豐富其功能以及應(yīng)用場(chǎng)景, 都有進(jìn)一步研究的價(jià)值.

本文主要針對(duì)格上偽隨機(jī)函數(shù)的研究現(xiàn)狀進(jìn)行綜述, 剩余部分安排如下: 第2 節(jié)回顧偽隨機(jī)函數(shù)設(shè)計(jì)中經(jīng)常使用的通用構(gòu)造方案; 第3 節(jié)回顧現(xiàn)有格上偽隨機(jī)函數(shù)方案所依賴(lài)的底層安全假設(shè)(困難問(wèn)題);第4 節(jié)梳理現(xiàn)有基于格困難問(wèn)題設(shè)計(jì)的偽隨機(jī)函數(shù)方案, 重點(diǎn)關(guān)注這些方案在降低底層安全假設(shè)強(qiáng)度以及提升并行性方面采用的技術(shù)以及取得的成果; 第5 節(jié)簡(jiǎn)單介紹基于格困難問(wèn)題設(shè)計(jì)具備擴(kuò)展功能的偽隨機(jī)函數(shù)的研究進(jìn)展; 最后, 第6 節(jié)總結(jié)全文.

2 偽隨機(jī)函數(shù)的通用構(gòu)造方法

本節(jié)介紹兩種經(jīng)典的偽隨機(jī)函數(shù)通用構(gòu)造方法: 一種是Goldreich、Goldwasser 和Micali[1]提出的基于偽隨機(jī)數(shù)生成器的通用構(gòu)造方法, 將其簡(jiǎn)記作GGM-PRF; 另一種是Naor 和Reingold[40]提出的基于偽隨機(jī)合成器(pseudorandom synthesizer,SYN)的通用構(gòu)造方法,將其簡(jiǎn)記作SYN-PRF.這兩種通用構(gòu)造方法各具優(yōu)劣: GGM-PRF 對(duì)組件的要求低, 一般來(lái)說(shuō)對(duì)密鑰的需求量小, 但是并行性差; SYN-PRF具有更好的并行性, 但是往往對(duì)密鑰的需求量大.前述兩種通用構(gòu)造方法在偽隨機(jī)函數(shù)方案的設(shè)計(jì)中有很多應(yīng)用, 如文獻(xiàn)[8,18,22,23,41].

2.1 GGM-PRF 通用構(gòu)造方法

GGM-PRF 的組件是倍長(zhǎng)偽隨機(jī)數(shù)生成器(length-doubling PRG, ld-PRG).我們稱(chēng)確定性函數(shù)G:{0,1}s →{0,1}y是偽隨機(jī)數(shù)生成器, 如果y>s, 且對(duì)于均勻隨機(jī)采樣的種子s$←?{0,1}s, 函數(shù)計(jì)算結(jié)果G(s) 與其輸出空間{0,1}y上的均勻隨機(jī)采樣之間計(jì)算不可區(qū)分.特別地, 如果y= 2s, 那么G是一個(gè)倍長(zhǎng)偽隨機(jī)數(shù)生成器.GGM-PRF 的構(gòu)造非常簡(jiǎn)潔: 對(duì)于輸入? ∈N 比特長(zhǎng)消息的GGM-PRF, 其運(yùn)算包含?輪串行的ld-PRG 組件調(diào)用; 根據(jù)GGM-PRF 輸入消息的第i ∈{1,2,···,?}個(gè)比特從第i輪ld-PRG 的運(yùn)算結(jié)果中選擇一半作為第i+1 輪ld-PRG 輸入的種子; GGM-PRF 的密鑰作為初始ld-PRG 的種子; 第?輪ld-PRG 的運(yùn)算結(jié)果即為GGM-PRF 的輸出.更正式地, 給定倍長(zhǎng)偽隨機(jī)數(shù)生成器G:{0,1}s →{0,1}2s, GGM-PRFFGGM:{0,1}s×{0,1}? →{0,1}s的定義如下:

其中密鑰s ∈{0,1}s, 輸入x=(x1,x2,···,x?)∈{0,1}?; 對(duì)任意種子s ∈{0,1}s, 符號(hào)G0(s)∈{0,1}s和G1(s)∈{0,1}s分別表示G(s) 計(jì)算結(jié)果的左半部分和右半部分.圖1 給出了一個(gè)輸入3 比特長(zhǎng)消息的GGM-PRF 構(gòu)造示例.

圖1 GGM-PRF 構(gòu)造示例, 其中輸入消息為x=(101)Figure 1 An example of GGM-PRF with the message x=(101)

GGM-PRF 具有串行結(jié)構(gòu), 其運(yùn)算電路的深度至少是輸入消息長(zhǎng)度的線(xiàn)性函數(shù), 因此GGM-PRF 的實(shí)例化方案一般在并行性上會(huì)稍顯遜色.另一方面, GGM-PRF 對(duì)于密鑰的需求較小, 其密鑰規(guī)模是固定的, 并不會(huì)隨輸入消息長(zhǎng)度的變化而變化.

2.2 SYN-PRF 通用構(gòu)造方法

SYN-PRF 通用構(gòu)造方法使用了一種更強(qiáng)的組件, 即偽隨機(jī)合成器.我們稱(chēng)確定性函數(shù)S:D×D →D是偽隨機(jī)合成器, 如果對(duì)任意參數(shù)u,v(u,v= poly(κ) 是安全參數(shù)κ ∈N 的多項(xiàng)式函數(shù)), 任意u個(gè)左輸入(x1,x2,···,xu)∈Du以及v個(gè)右輸入(y1,y2,···,yv)∈Dv,u×v個(gè)所有可能的函數(shù)計(jì)算結(jié)果si,j=S(xi,yj)∈D都是偽隨機(jī)的.SYN-PRF 采用了一種遞歸的設(shè)計(jì)思路: 給定偽隨機(jī)合成器S以及兩個(gè)輸入消息長(zhǎng)度為t的獨(dú)立的偽隨機(jī)函數(shù)F0,F1, 可以構(gòu)造輸入消息長(zhǎng)度為2t的偽隨機(jī)函數(shù)F(x1,x2,···,x2t) =S(F0(x1,x2,···,xt),F1(xt+1,xt+2,···,x2t)); 當(dāng)t= 1, 函數(shù)F可簡(jiǎn)單實(shí)例化為根據(jù)輸入的單比特消息從兩個(gè)獨(dú)立均勻隨機(jī)的密鑰中選擇一個(gè)輸出.基于前述遞歸思路, SYN-PRFFSYN,?:D2?×{0,1}? →D的正式定義如下:

其中,k0和k1分別表示密鑰k的左半部分和右半部分,x0和x1分別表示消息x的左半部分和右半部分.圖2 給出了一個(gè)輸入8 比特長(zhǎng)消息的SYN-PRF 構(gòu)造示例.

圖2 SYN-PRF 構(gòu)造示例, 其中密鑰為k =(k10,k11,··· ,k80,k81), 輸入消息為x=(10001101)Figure 2 An example of SYN-PRF with the key k =(k10,k11,··· ,k80,k81) and the message x=(10001101)

由圖可知, SYN-PRF 對(duì)應(yīng)著一棵深度為log(?) 的滿(mǎn)二叉樹(shù), 具有很好的并行結(jié)構(gòu).設(shè)偽隨機(jī)合成器S的運(yùn)算電路深度為dS, 那么FSYN,?的運(yùn)算電路深度為log(?)·dS.但是注意到, SYN-PRF 的密鑰數(shù)量是其輸入長(zhǎng)度的兩倍, 其對(duì)于密鑰的需求量相較于GGM-PRF 往往會(huì)更大1對(duì)于SYN-PRF 密鑰需求量大這一問(wèn)題有一個(gè)簡(jiǎn)單的解決方案: 可以借助偽隨機(jī)數(shù)生成器, 由一個(gè)短密鑰生成足夠數(shù)量的密鑰供偽隨機(jī)函數(shù)使用..

3 格上困難問(wèn)題介紹

格理論起源于1611 年開(kāi)普勒提出的關(guān)于三維空間中等半徑小球最大堆積密度的猜想, 后經(jīng)諸多數(shù)學(xué)家的深入研究, 格理論不斷發(fā)展成熟, 并于上世紀(jì)末被創(chuàng)造性地應(yīng)用于密碼領(lǐng)域.格上的很多問(wèn)題被證明是困難的, 且被普遍認(rèn)為具備抵抗量子攻擊的特性.目前, 在設(shè)計(jì)偽隨機(jī)函數(shù)時(shí)使用最多的格困難問(wèn)題是LWE 問(wèn)題[42]以及LWE 問(wèn)題的一個(gè)確定性變型—舍入學(xué)習(xí)[18](learning with rounding, LWR) 問(wèn)題.舍入容錯(cuò)學(xué)習(xí)問(wèn)題[23](learning with rounding and errors, LWRE)在偽隨機(jī)函數(shù)方案的設(shè)計(jì)中也有使用.此外, 還有子空間LWE 問(wèn)題[43]等, 可以應(yīng)用于消息認(rèn)證碼的構(gòu)造[44].本節(jié)將對(duì)前述格上偽隨機(jī)函數(shù)方案設(shè)計(jì)中使用的底層困難問(wèn)題進(jìn)行介紹.

3.1 LWE 困難問(wèn)題

2005 年, Regev 在文獻(xiàn)[42] 中首次定義了LWE 問(wèn)題, 并給出了最壞情況格上困難問(wèn)題到LWE 問(wèn)題的量子歸約; 后續(xù), 文獻(xiàn)[45,46] 又給出了格困難問(wèn)題到LWE 問(wèn)題的經(jīng)典歸約.這些研究成果為基于LWE 困難問(wèn)題設(shè)計(jì)的密碼方案提供了可證明安全的保障.判定版本的LWEn,q,χ,m問(wèn)題指的是輸入均勻隨機(jī)矩陣A ∈Zn×mq和向量v ∈Zmq, 判斷v是通過(guò)v?=s?A+e?(modq) 計(jì)算得到的還是從Zmq上均勻隨機(jī)采樣得到的, 其中, 參數(shù)n,q,χ,m分別對(duì)應(yīng)LWE 問(wèn)題的維度、模數(shù)、噪聲分布以及實(shí)例數(shù),公開(kāi)矩陣A$←?Zn×mq和秘密信息s$←?Znq是均勻隨機(jī)采樣的, 噪聲向量e ←χm是按照噪聲分布χ采樣的.相對(duì)應(yīng)的, 判定性L(fǎng)WEn,q,χ,m假設(shè)指的是對(duì)任意概率多項(xiàng)式時(shí)間(probabilistic polynomial time,PPT) 的敵手, LWEn,q,χ,m問(wèn)題都是難解的.

求解LWE 問(wèn)題的難度與LWE 問(wèn)題的維度n、噪聲分布χ以及模數(shù)q有著密切關(guān)系.當(dāng)噪聲分布χ是以σ為參數(shù)的離散高斯分布且時(shí), 求解LWEn,q,χ,m問(wèn)題的難度至少與量子求解任意n維格上的判定版本近似最短向量問(wèn)題GapSVPγ或近似最短線(xiàn)性無(wú)關(guān)向量問(wèn)題SIVPγ的難度相當(dāng), 其中近似參數(shù)γ ≈O(nq/σ)[42].根據(jù)相關(guān)文獻(xiàn)[47–51], 目前能夠在多項(xiàng)式時(shí)間內(nèi)求解的GapSVPγ或者SIVPγ問(wèn)題需要具有指數(shù)數(shù)量級(jí)的近似參數(shù), 即γ= 2Θ(nloglogn/logn); 如果近似參數(shù)γ= poly(n) 是維度n的多項(xiàng)式函數(shù), 那么求解這些問(wèn)題需要2Θ(nlogn)數(shù)量級(jí)的時(shí)間或者2Θ(n)數(shù)量級(jí)的時(shí)間及空間; 更一般化地, 如果漸進(jìn)參數(shù)γ= 2k, 求解這些問(wèn)題大約需要2?Θ(n/k)數(shù)量級(jí)的時(shí)間2符號(hào)?Θ(·) 表示括號(hào)內(nèi)省略了一些小量, 如logO(1)κ; 符號(hào) ?O(·) 定義類(lèi)似..而且即便是應(yīng)用量子算法, 求解這些問(wèn)題的時(shí)間復(fù)雜度或空間復(fù)雜度也不會(huì)有很大提升[52].

除上述標(biāo)準(zhǔn)的定義方式外, LWE 問(wèn)題還有一些特殊變種, 這些變種LWE 問(wèn)題同樣被證明是難解的.文獻(xiàn)[53] 證明了秘密信息s可以采樣自噪聲分布(或其他一些小模數(shù)的分布); 文獻(xiàn)[3] 證明了公開(kāi)矩陣A可以采樣自一些特殊分布, 即“Coset Sampleable” 分布(相應(yīng)LWE 問(wèn)題稱(chēng)為non-uniform LWE, 簡(jiǎn)記作NLWE); 文獻(xiàn)[22] 證明了秘密信息s和噪聲向量e可以采樣自Zmp上的均勻隨機(jī)分布,要求p< 2q且p=nω(1).給定Q= poly(κ) 為安全參數(shù)κ的多項(xiàng)式,Q重LWE 問(wèn)題指的是區(qū)分(A,s?1A+e?1,s?2A+e?2,···,s?QA+e?Q) 和(A,u?1,u?2,···,u?Q), 其中秘密信息s1,s2,···,sQ是獨(dú)立均勻隨機(jī)選取的, 噪聲向量e1,e2,···,eQ是按照噪聲分布獨(dú)立采樣的.借助混合論證技術(shù)可以證明, 求解Q重LWE 問(wèn)題至少與求解LWE 問(wèn)題一樣難, 只是在歸約損失上需要增加一個(gè)Q因子.

3.2 LWR 困難問(wèn)題

2012 年, Banerjee 等[18]提出了一個(gè)LWE 問(wèn)題的確定性變型, 即LWR 問(wèn)題.具體地, LWRn,q,p,m問(wèn)題指的是輸入均勻隨機(jī)矩陣A ∈Zn×mq以及向量v ∈Zmp, 判斷v是通過(guò)v?=?s?A?p計(jì)算得到的,還是從Zmp上均勻隨機(jī)采樣得到的.其中, 參數(shù)n,q,p,m分別對(duì)應(yīng)LWR 問(wèn)題的維度、模數(shù)、舍入?yún)?shù)以及實(shí)例數(shù), 公開(kāi)矩陣A$←?Zn×mq和秘密向量s$←?Znq是均勻隨機(jī)采樣得到的, 舍入函數(shù)?·?p: Zq →Zp將Zq上的元素x映射為Zp上的?xp/q?modp3舍入函數(shù)運(yùn)算可以擴(kuò)展到n 維向量空間上, 設(shè)x = (x1,x2,··· ,xn)? ∈ Znq, 令?x?p := (?x1?p,?x2?p,··· ,?xn?p)?..相應(yīng)地, LWRn,q,p,m假設(shè)指的是LWRn,q,p,m問(wèn)題是難解的, 即分布(A,?s?A?p) 與分布(A,?u??p) 之間計(jì)算不可區(qū)分, 其中u$←?Zmq是均勻隨機(jī)采樣得到的4特殊地, 當(dāng)p 整除q 時(shí), ?u?p 就是Zmp 上的均勻隨機(jī)分布..

Banerjee 等給出了一個(gè)LWEn,q,χ,m到LWRn,q,p,m的簡(jiǎn)潔歸約, 其思路為: (1) 當(dāng)模數(shù)q和舍入?yún)?shù)p滿(mǎn)足q ≥nω(1)σp(或q ≥2κσp) 時(shí), 分布(A,?s?A?p) 與(A,?s?A+e??p) 之間的統(tǒng)計(jì)距離為n?ω(1)(或2?O(κ)), 是可忽略的; (2) 由LWEn,q,χ,m假設(shè)可證明, 分布(A,?s?A+e??p) 與(A,?u??p)之間計(jì)算不可區(qū)分.基于前述歸約可知求解LWR 問(wèn)題至少與求解LWE 問(wèn)題一樣難, 進(jìn)一步結(jié)合LWE問(wèn)題的困難性可知求解LWR 問(wèn)題是困難的.

注意到, 上述歸約成立要求LWR 問(wèn)題的模數(shù)q至少是超多項(xiàng)式規(guī)模的; 如果追求分布(A,?s?A?p)與(A,?s?A+e??p)之間的統(tǒng)計(jì)距離是指數(shù)級(jí)小, 那么q需要是指數(shù)規(guī)模的.為了放松LWE 到LWR 的歸約對(duì)于模數(shù)q規(guī)模的約束,密碼學(xué)家們進(jìn)行了諸多探索.在提前給定實(shí)例數(shù)m的條件下,文獻(xiàn)[8,54–57]基于LWE 假設(shè)證明了具有多項(xiàng)式模數(shù)的LWR 問(wèn)題的困難性.文獻(xiàn)[58] 提出了一個(gè)LWR 問(wèn)題的特殊變型, 并基于LWE 假設(shè)證明了具有任意實(shí)例數(shù)以及多項(xiàng)式模數(shù)的變種LWR 問(wèn)題的困難性.文獻(xiàn)[59] 證明了LWE 到LWR 歸約的不可能結(jié)論: 如果LWE 假設(shè)成立, 那么不存在LWE 問(wèn)題到具有任意實(shí)例數(shù)以及多項(xiàng)式模數(shù)的LWR 問(wèn)題的逐點(diǎn)歸約(即歸約中LWE 問(wèn)題實(shí)例獨(dú)立映射到LWR 實(shí)例).

3.3 LWRE 困難問(wèn)題

2020 年,Kim[23]通過(guò)將LWE 問(wèn)題和LWR 問(wèn)題“鏈接”起來(lái),提出了LWRE 問(wèn)題.除描述LWE 問(wèn)題以及LWR 問(wèn)題的參數(shù)n,m,q,χ,p外, LWRE 問(wèn)題還涉及一個(gè)鏈接參數(shù)τ ∈N.LWRE 實(shí)例是通過(guò)串聯(lián)τ層LWE 實(shí)例和LWR 實(shí)例來(lái)定義的: 對(duì)所有i ∈{1,2,···,τ},第i層計(jì)算ri ←?s?i A+e?i ?p ∈Zmp;第τ層的計(jì)算結(jié)果即為最終輸出.其中, 公開(kāi)矩陣A$←?Zn×mq和每層計(jì)算時(shí)使用的秘密信息si$←?Znq都是獨(dú)立均勻隨機(jī)采樣的; 除初始計(jì)算時(shí)使用的噪聲向量e0設(shè)置為全0 向量外, 噪聲向量ei ←Dχ(ri?1)是以第i ?1 層的計(jì)算結(jié)果ri?1為輸入, 調(diào)用分布χ上的采樣算法采樣得到的.LWREn,q,p,χ,τ,m假設(shè)指的是LWRE 實(shí)例與Zmp上的均勻隨機(jī)采樣之間計(jì)算不可區(qū)分.

Kim[23]給出了一個(gè)LWE 到LWRE 的歸約證明, 從而將求解LWRE 問(wèn)題的困難性歸結(jié)到求解格困難問(wèn)題之上.更具體地, 假設(shè)χ是以σ為參數(shù)的離散高斯分布且p|q, 如果存在敵手A可以以?LWRE的優(yōu)勢(shì)解決LWREn,q,p,χ,τ,m問(wèn)題, 那么存在歸約算法B, 可以借助A的能力以?LWE的優(yōu)勢(shì)解決LWEn,q,χ,m問(wèn)題, 且有:

3.4 環(huán)上LWE 困難問(wèn)題

Lyubashevsky 等在文獻(xiàn)[60] 中提出了環(huán)LWE (ring-LWE, RLWE) 的概念.環(huán)LWE 的描述與標(biāo)準(zhǔn)的LWE 基本一致, 只是實(shí)例(公開(kāi)參數(shù)矩陣、秘密信息以及噪聲向量) 采樣自一些特殊的環(huán), 典型的如度為n的分圓環(huán).Lyubashevsky 等證明了求解環(huán)LWE 問(wèn)題至少與量子求解任意理想格上的近似最短向量問(wèn)題一樣困難, 從而證明了環(huán)LWE 問(wèn)題的困難性.與LWE 相比, 環(huán)LWE 具備更好的緊湊性: 一個(gè)環(huán)LWE 實(shí)例相當(dāng)于n個(gè)LWE 實(shí)例.因此, 基于環(huán)LWE 設(shè)計(jì)的密碼方案往往具備更好的參數(shù)規(guī)模以及效率.此外, 文獻(xiàn)[18] 和[23] 也分別提出了環(huán)版本的LWR 問(wèn)題以及LWRE 問(wèn)題, 并基于環(huán)LWE 假設(shè)證明了它們的困難性.

4 基于格的偽隨機(jī)函數(shù)

格上偽隨機(jī)函數(shù)的研究起始于Banerjee 等發(fā)表在2012 年歐密會(huì)上的工作[18], 他們給出了三個(gè)基于格困難問(wèn)題的偽隨機(jī)函數(shù)方案.第一個(gè)方案是基于LWR 困難問(wèn)題實(shí)例化倍長(zhǎng)偽隨機(jī)數(shù)發(fā)生器, 進(jìn)而實(shí)例化GGM-PRF 通用構(gòu)造得到的, 記作FBPR,GGM.結(jié)合Banerjee 等[18]給出的LWE 到LWR 的歸約, 該方案可基于超多項(xiàng)式模數(shù)的LWE 假設(shè)證明安全.但是受限于GGM-PRF 固有的串行結(jié)構(gòu), 該方案的運(yùn)行電路深度是其輸入長(zhǎng)度的線(xiàn)性函數(shù).

Banerjee 等[18]的第二個(gè)方案是基于LWR 困難問(wèn)題實(shí)例化偽隨機(jī)合成器, 進(jìn)而實(shí)例化SYN-PRF通用構(gòu)造方案得到的, 記作FBPR,SYN.這一偽隨機(jī)函數(shù)方案具有更好的并行性.Banerjee 等給出的偽隨機(jī)合成器實(shí)例化為SBPR: Zn×nq×Zn×nq→Zn×np, 其中SBPR(A,S) =?A·S?p.該偽隨機(jī)合成器的計(jì)算僅涉及矩陣乘法以及舍入函數(shù)運(yùn)算, 可在NC1電路內(nèi)實(shí)現(xiàn).故而方案FBPR,SYN是NC2電路可實(shí)現(xiàn)的.但是FBPR,SYN對(duì)底層困難問(wèn)題的模數(shù)q有很高的要求, 其存在所謂的“模數(shù)堆疊” (power of moduli) 問(wèn)題.注意到, 在SYN-PRF 通用構(gòu)造中, 偽隨機(jī)合成器組件的輸出空間應(yīng)與其左、右輸入空間一致, 但是SBPR并不滿(mǎn)足這一點(diǎn).Banerjee 等給出的解決方案是為每一層的偽隨機(jī)合成器設(shè)置不同的參數(shù)q,p, 即第i層偽隨機(jī)合成器的參數(shù)分別為qi和pi, 而且pi=qi?1.根據(jù)SYN-PRF 的安全性證明, 每一層偽隨機(jī)合成器的參數(shù)需滿(mǎn)足qi ≥κω(1)pi=κω(1)qi?1.如此一來(lái), 最底層偽隨機(jī)合成器對(duì)應(yīng)的參數(shù)qlog?(?=poly(κ)是輸入消息的比特長(zhǎng)度) 在經(jīng)過(guò)log?層的堆疊后, 其規(guī)模大約為κω(log?).也就是說(shuō), 方案FBPR,SYN的安全性最終依賴(lài)于超多項(xiàng)式模數(shù)的LWE 問(wèn)題.

Banerjee 等[18]的第三個(gè)偽隨機(jī)函數(shù)方案是一個(gè)(密鑰) 子集合乘積結(jié)構(gòu)的直接構(gòu)造, 記作FBPR,Dir.設(shè)FBPR,Dir的輸入消息比特長(zhǎng)度為?= poly(κ), 方案運(yùn)算最多需要進(jìn)行?次矩陣或向量乘法, 因此可在NC2電路內(nèi)實(shí)現(xiàn).特別地, 該方案的環(huán)版本理論上具有更好的并行性, 可以在NC1電路內(nèi)實(shí)現(xiàn).方案FBPR,Dir的安全性可基于LWE 假設(shè)直接證明, 但是要求LWE 的模數(shù)q是安全參數(shù)的超指數(shù)函數(shù).

2013 年, Boneh 等[3]基于LWE 假設(shè)給出了首個(gè)標(biāo)準(zhǔn)模型下的具有(幾乎) 密鑰同態(tài)性質(zhì)的偽隨機(jī)函數(shù)方案, 記作FBLMR.該方案采用了(公開(kāi)參數(shù)矩陣) 子集合乘積的構(gòu)造方法, 可以在NC2電路內(nèi)實(shí)現(xiàn).方案可基于NLWE 假設(shè), 進(jìn)而基于LWE 假設(shè)證明安全, 但要求模數(shù)q=κκ是安全參數(shù)的超指數(shù)函數(shù).

注意到, 前述偽隨機(jī)函數(shù)方案都要求底層LWE 困難問(wèn)題的模數(shù)q是超多項(xiàng)式甚至是指數(shù)大小.然而,底層LWE 問(wèn)題的模數(shù)太大會(huì)帶來(lái)一些弊端.一方面, 如前所述, LWE 問(wèn)題的困難程度與其模數(shù)的規(guī)模密切相關(guān): 當(dāng)模數(shù)q= poly(κ) 為安全參數(shù)的多項(xiàng)式大小時(shí)(對(duì)應(yīng)格困難問(wèn)題的近似參數(shù)γ為多項(xiàng)式), 即使是量子算法求解這樣的LWE 問(wèn)題也要指數(shù)級(jí)的時(shí)間或空間; 當(dāng)模數(shù)q的規(guī)模增大, 特別是增大到安全參數(shù)的指數(shù)數(shù)量級(jí)(近似參數(shù)γ為指數(shù)數(shù)量級(jí)), LWE 問(wèn)題的求解難度就會(huì)大大降低.因此, 基于大模數(shù)LWE 問(wèn)題設(shè)計(jì)的偽隨機(jī)函數(shù)方案, 其安全性要建立在更強(qiáng)的安全假設(shè)之上.另一方面, 底層問(wèn)題的規(guī)模還會(huì)影響頂層方案的效率, 一般來(lái)說(shuō), 偽隨機(jī)函數(shù)方案的參數(shù)規(guī)模、時(shí)間復(fù)雜度、空間復(fù)雜度等都會(huì)與其底層困難問(wèn)題的規(guī)模相關(guān), 因此, 當(dāng)?shù)讓覮WE 問(wèn)題模數(shù)變大, 偽隨機(jī)函數(shù)的參數(shù)規(guī)模和效率也會(huì)隨之變差.

為了降低底層LWE 問(wèn)題的模數(shù)規(guī)模, 提升偽隨機(jī)函數(shù)方案的安全性以及效率, 密碼學(xué)家們開(kāi)展了大量研究工作并取得了諸多成果.現(xiàn)有工作中, 降低模數(shù)規(guī)模使用的方法大致有: 改進(jìn)SYN-PRF 通用構(gòu)造方案, 以解決模數(shù)堆疊問(wèn)題; 借助特殊結(jié)構(gòu), 如樹(shù)形結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)降低模數(shù)規(guī)模; 改進(jìn)LWE 到LWR 的歸約結(jié)果; 使用消息空間擴(kuò)展技術(shù).

改進(jìn)SYN-PRF 通用構(gòu)造方案.文獻(xiàn)[24,61] 提出了不同的方法來(lái)解決FBPR,SYN方案中存在的模數(shù)堆疊問(wèn)題.Banerjee 在他的學(xué)位論文[61]中, 對(duì)方案FBPR,SYN中原偽隨機(jī)合成器的設(shè)計(jì)進(jìn)行了改進(jìn).他將原先方案中的方陣都變?yōu)榱诵辛袛?shù)不同的矩陣, 更具體地, 修改后的偽隨機(jī)合成器定義為SBan:Zn×mq×Zn×mq→Zm×mp, 其中SBan(A,S) :=?A?·S?p, 且參數(shù)滿(mǎn)足pm=qn.然后, 他在每層偽隨機(jī)合成器之上增加了一個(gè)可有效計(jì)算的雙射K: Zm×mp→Zn×mq, 從而實(shí)現(xiàn)了上、下層偽隨機(jī)合成器之間輸入和輸出的對(duì)齊.改進(jìn)后的方案, 記作FBan,SYN, 其模數(shù)q的規(guī)?？蓛?yōu)化為κω(1).Li 等[24]則通過(guò)在SYN-PRF 中引入偽隨機(jī)數(shù)發(fā)生器, 同時(shí)結(jié)合中國(guó)剩余定理來(lái)解決模數(shù)堆疊問(wèn)題.

樹(shù)形結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu).Banerjee 和Peikert[20]提出了一類(lèi)具有樹(shù)形結(jié)構(gòu)的、具有密鑰同態(tài)性質(zhì)的偽隨機(jī)函數(shù)構(gòu)造方案, 我們將其稱(chēng)為BP-PRF.BP-PRF 可以看作文獻(xiàn)[3] 中偽隨機(jī)函數(shù)方案的擴(kuò)展和推廣:它們都是通過(guò)在偽隨機(jī)函數(shù)的計(jì)算中插入一些“比特分解” 操作, 來(lái)避免安全證明中底層困難問(wèn)題的噪聲累積過(guò)快.而B(niǎo)P-PRF 支持(基于二叉樹(shù)結(jié)構(gòu)的)更精細(xì)化的“比特分解”嵌入模式,從而能支持更靈活的參數(shù)選擇.根據(jù)文獻(xiàn)[20], 任意一棵完全二叉樹(shù)都可以對(duì)應(yīng)構(gòu)造一個(gè)BP-PRF.如文獻(xiàn)[3]中的方案就對(duì)應(yīng)著一種特殊的完全二叉樹(shù), 即樹(shù)中所有的右孩子節(jié)點(diǎn)均為葉子節(jié)點(diǎn)(“Left-Spin” 完全二叉樹(shù)).圖3(a)和圖3(b)分別給出了對(duì)應(yīng)滿(mǎn)二叉樹(shù)以及對(duì)應(yīng)“Left-Spin” 完全二叉樹(shù)的BP-PRF 構(gòu)造.

圖3 BP-PRF 構(gòu)造示例: 基于滿(mǎn)二叉樹(shù)的BP-PRF 方案(a); 基于“Left-Spin” 樹(shù)的BP-PRF 方案(b)Figure 3 Examples of BP-PRF based on a full binary tree (a) and a left-spine tree (b)

BP-PRF[20]的模數(shù)規(guī)模以及并行性均取決于其對(duì)應(yīng)的完全二叉樹(shù)T的形狀.模數(shù)q的規(guī)模主要由二叉樹(shù)的左深度(left depth) 決定.左深度, 記作e(T), 即從根節(jié)點(diǎn)到任意葉子節(jié)點(diǎn)路徑上左孩子節(jié)點(diǎn)的最大數(shù)目, 也稱(chēng)作擴(kuò)張因子(expansion factor).更具體地,q應(yīng)滿(mǎn)足q ≈σ·p·|T|·(nlogq)e(T)·κω(1),其中,n,q,σ為底層LWE 困難問(wèn)題的參數(shù),|T| 表示T中葉子節(jié)點(diǎn)的數(shù)目(也是BP-PRF 的輸入消息比特長(zhǎng)度, 設(shè)|T| = poly(κ)).BP-PRF 方案的并行性由T的右深度(right depth) 決定.右深度, 記作s(T), 即從根節(jié)點(diǎn)到任意葉子節(jié)點(diǎn)路徑上右孩子節(jié)點(diǎn)的最大數(shù)目, 也稱(chēng)作串行因子(sequentiality factor).更具體地, BP-PRF 方案的電路深度約為max{s(T),log(e(T))}·O(logκ).總的來(lái)說(shuō), 當(dāng)e(T) 變小, 底層LWE 問(wèn)題的模數(shù)規(guī)模也可隨之變小; 當(dāng)s(T) 變小, 方案的并行性一般會(huì)隨之提升.給定BP-PRF 的輸入消息長(zhǎng)度(即|T|)、e(T) 的上限e以及s(T) 的上限s, 可以通過(guò)動(dòng)態(tài)規(guī)劃構(gòu)造最優(yōu)解的完全二叉樹(shù).特別地, 如果約束e=s, 那么最優(yōu)解有e(T)≈s(T) = log4(|T|), 此時(shí)方案的模數(shù)規(guī)模為q ≈κω(logκ),電路深度為NC2.如果忽略并行性, 那么可以取e(T)=1,s(T)=|T|?1, 此時(shí)q ≈κω(1), 電路深度至少是|T| 的線(xiàn)性函數(shù).

Kim[23]還將這種“鏈接” 的思路應(yīng)用到已有的偽隨機(jī)函數(shù)方案之上.通過(guò)串聯(lián)文獻(xiàn)[20] 中的方案,Kim 構(gòu)造了新的偽隨機(jī)函數(shù)方案, 記作FKim,BP.該方案的模數(shù)規(guī)模以及并行性與鏈接參數(shù)τ以及組件的擴(kuò)張參數(shù)e(T) 和串行參數(shù)s(T) 相關(guān): 一方面, 方案的安全性要求(2|T|σme(T)+1p/q)τ?1是可忽略量;另一方面, 方案的電路深度為τ·s(T)·log|T| (參數(shù)定義參考BP-PRF).令e(T) = 1,s(T) =O(|T|),τ= Θ(κ), 此時(shí)方案的模數(shù)可取q= 4|T|σm2p, 是安全參數(shù)的多項(xiàng)式函數(shù); 方案具備指數(shù)安全性, 但是需要線(xiàn)性深度電路實(shí)現(xiàn).

改進(jìn)LWE 到LWR 的歸約結(jié)果.Banerjee 等[18]基于LWE 假設(shè)證明了LWR 問(wèn)題的困難性, 但是這一證明成立要求模數(shù)q至少是安全參數(shù)的超多項(xiàng)式大小.源于這一限制, 基于LWR 假設(shè)設(shè)計(jì)的偽隨機(jī)函數(shù)方案, 其安全性都需要依賴(lài)于超多項(xiàng)式模數(shù)的LWE 假設(shè).Alwen 等[54]提出了一種新的LWE 到LWR 問(wèn)題的歸約方法, 簡(jiǎn)單來(lái)說(shuō), 基于LWE 假設(shè)可以將LWR 實(shí)例從正常模式切換至損失模式(lossy mode), 損失模式下的LWR 實(shí)例不會(huì)泄露太多的秘密信息, 因此求解是困難的.這一歸約證明對(duì)于模數(shù)q的要求可放松為q ≥nmσp, 當(dāng)取n,m,σ,p= poly(κ), 模數(shù)q也是安全參數(shù)的多項(xiàng)式函數(shù).需要注意的是, 為保證參數(shù)滿(mǎn)足q ≥nmσp, LWR 的實(shí)例數(shù)m需要提前給定.

結(jié)合Alwen 等[54]的歸約結(jié)果, GGM-PRF 實(shí)例化方案FBPR,GGM[18]可基于多項(xiàng)式模數(shù)的LWE 假設(shè)證明安全, 為方便區(qū)分, 本文將應(yīng)用了Alwen 等[54]結(jié)論的方案記作FAKPW,GGM.注意, GGM-PRF 方案的安全性證明只需要給定實(shí)例數(shù)的LWR 假設(shè)成立, 因此可應(yīng)用Alwen 等的結(jié)果.而其他基于LWR 的偽隨機(jī)函數(shù)方案, 其安全性證明需要LWR 假設(shè)對(duì)任意多項(xiàng)式大小的實(shí)例數(shù)m均成立; 如果對(duì)這些方案應(yīng)用Alwen 等的結(jié)果, 方案就只能實(shí)現(xiàn)受限的偽隨機(jī)性, 即方案的參數(shù)與安全實(shí)驗(yàn)中敵手提交的問(wèn)詢(xún)次數(shù)相關(guān).

Lai 等[8]進(jìn)一步優(yōu)化了文獻(xiàn)[54] 中LWE 到LWR 的歸約證明, 給出了一個(gè)n重LWE 問(wèn)題到Q重LWR 問(wèn)題的緊致歸約證明.借助這一結(jié)果, 他們提出了基于多項(xiàng)式模數(shù)LWE 假設(shè)的具有幾乎緊致安全性的GGM-PRF 實(shí)例化方案, 記作FLLW,GGM; 該方案也需要線(xiàn)性深度的電路實(shí)現(xiàn).Li 等[24]通過(guò)引入具有靈活輸出空間的偽隨機(jī)數(shù)發(fā)生器以及擴(kuò)展偽隨機(jī)合成器(generalized SYN, gSYN), 提出了一個(gè)SYN-PRF 通用構(gòu)造方案的變型, 見(jiàn)圖4.他們基于LWR 假設(shè)給出了該通用構(gòu)造方案的兩個(gè)實(shí)例化方案,結(jié)合文獻(xiàn)[54] 給出的LWE 到LWR 的歸約結(jié)果, 得到了兩個(gè)基于多項(xiàng)式模數(shù)LWE 假設(shè)的偽隨機(jī)函數(shù)方案, 其分別可在NC3和NC2電路內(nèi)實(shí)現(xiàn).但是源于文獻(xiàn)[54] 歸約結(jié)果的局限性, 這兩個(gè)實(shí)例化方案僅具有受限偽隨機(jī)性.進(jìn)一步地, Li 等在前述實(shí)例化基礎(chǔ)上借助“on-the-fly” 轉(zhuǎn)換[19]解決了安全性受限的問(wèn)題, 同時(shí)提升了方案并行性.最終方案, 記作FLLHG, 可基于多項(xiàng)式模數(shù)的LWE 假設(shè)證明安全, 且可以在NC1+o(1)電路內(nèi)實(shí)現(xiàn).

圖4 FLLHG 構(gòu)造示例, 其中密鑰為k =(k10,k11,··· ,k80,k81), 輸入消息為x=(10001101)Figure 4 An example of FLLHG, where the key k =(k10,k11,··· ,k80,k81) and the message x=(10001101)

使用消息空間擴(kuò)展技術(shù).一般來(lái)說(shuō), 偽隨機(jī)函數(shù)方案的參數(shù)規(guī)模、安全性、效率和電路深度等都會(huì)與其輸入消息的長(zhǎng)度相關(guān).基于這一思考, 一類(lèi)偽隨機(jī)函數(shù)的優(yōu)化思路是, 先構(gòu)造支持短輸入的偽隨機(jī)函數(shù)(這類(lèi)偽隨機(jī)函數(shù)往往可基于更弱的安全假設(shè)實(shí)現(xiàn), 且效率和并行性更好), 然后再通過(guò)或串或并的方式由支持短輸入的偽隨機(jī)函數(shù)組合出支持正常輸入的偽隨機(jī)函數(shù).簡(jiǎn)單地, 可以先借助通用哈希函數(shù)將偽隨機(jī)函數(shù)的輸入消息哈希為一個(gè)短輸入, 然后再調(diào)用支持短輸入的偽隨機(jī)函數(shù)實(shí)現(xiàn)計(jì)算[62], 但是這一方案無(wú)法抵抗生日攻擊.

Bellare 等[63]提出了級(jí)聯(lián)(cascade) 的技術(shù).級(jí)聯(lián)技術(shù)使用支持單個(gè)消息的偽隨機(jī)函數(shù)FBCK,1:K×X →K作為基本組件, 通過(guò)?次串行調(diào)用FBCK,1, 得到一個(gè)支持?個(gè)消息的偽隨機(jī)函數(shù)FBCK,?.級(jí)聯(lián)技術(shù)構(gòu)造思路如圖5(a)所示.注意到, 上述級(jí)聯(lián)構(gòu)造要求組件FBCK,1的輸出空間與其密鑰空間一致,但對(duì)于基于LWR 假設(shè)或LWE 假設(shè)設(shè)計(jì)的偽隨機(jī)函數(shù)方案來(lái)說(shuō), 很多都不滿(mǎn)足這一點(diǎn).Boneh 等[64]提出了增強(qiáng)級(jí)聯(lián)技術(shù)(augmented cascade), 他們?yōu)槊繉訂蝹€(gè)消息的偽隨機(jī)函數(shù)增加了一個(gè)外部輸入的獨(dú)立密鑰, 去除了級(jí)聯(lián)技術(shù)使用時(shí)要求輸出空間與密鑰空間一致這條限制.增強(qiáng)級(jí)聯(lián)使用的基本組件為FBMR,1: (K×S)×X →K, 其構(gòu)造思路如圖5(b)所示.通過(guò)(增強(qiáng)) 級(jí)聯(lián)的技術(shù)可以構(gòu)造更高效的偽隨機(jī)函數(shù)方案, 在某些實(shí)例化中還可以降低底層假設(shè)強(qiáng)度.

圖5 級(jí)聯(lián)技術(shù)(a)、增強(qiáng)級(jí)聯(lián)技術(shù)(b) 和FJKP,Dir(c) 構(gòu)造思路示例Figure 5 Illustrations of cascade technique (a), augmented cascade technique (b) and FJKP,Dir (c)

Jager 等[21]提出了一種增強(qiáng)的通用哈希函數(shù), 即all-prefix 通用哈希函數(shù)(all-prefix universal hash function, APUHF), 其滿(mǎn)足在任意位置對(duì)哈希函數(shù)的輸出進(jìn)行截?cái)? 得到的新哈希函數(shù)仍然是通用哈希函數(shù).Jager 等結(jié)合APUHF 以及增強(qiáng)級(jí)聯(lián)偽隨機(jī)函數(shù)提出了一個(gè)新的偽隨機(jī)函數(shù)構(gòu)造方法: 先調(diào)用APUHF 將偽隨機(jī)函數(shù)的輸入哈希為短向量(如將輸入從?= poly(κ) 比特長(zhǎng)哈希到y(tǒng)=ω(logκ) 比特長(zhǎng)), 然后再調(diào)用增強(qiáng)級(jí)聯(lián)偽隨機(jī)函數(shù)方案, 見(jiàn)圖5(c).與增強(qiáng)級(jí)聯(lián)方案相比, 該構(gòu)造方案在效率、并行性、密鑰規(guī)模以及歸約緊致性上都有所提升.Jager 等給出了APUHF 的簡(jiǎn)潔構(gòu)造, 并以偽隨機(jī)函數(shù)方案FBPR,Dir[18]實(shí)例化了增強(qiáng)級(jí)聯(lián)偽隨機(jī)函數(shù)(FBPR,Dir可看作組件為F((S,a),x) =Sx·a的增強(qiáng)級(jí)聯(lián)結(jié)構(gòu)的偽隨機(jī)函數(shù)), 由此得到了一個(gè)基于LWE 假設(shè)的偽隨機(jī)函數(shù)方案, 記作FJKP,Dir.該方案具有幾乎緊致的安全性, 其模數(shù)規(guī)模為q=κω(logκ), 且是NC1+o(1)電路可實(shí)現(xiàn)的.

D?ttling 和Schr?der[19]提出了另一種構(gòu)造具有(幾乎) 緊致安全性的偽隨機(jī)函數(shù)的通用構(gòu)造方法,其構(gòu)造大致包含兩個(gè)步驟.首先, 借助通用哈希函數(shù)將具有小消息空間的偽隨機(jī)函數(shù)進(jìn)行消息空間擴(kuò)展,得到一個(gè)受限偽隨機(jī)函數(shù), 這里小消息空間指的是偽隨機(jī)函數(shù)消息空間的規(guī)模為安全參數(shù)的多項(xiàng)式函數(shù),對(duì)任意Q= poly(κ),Q-受限偽隨機(jī)函數(shù)指的是對(duì)偽隨機(jī)函數(shù)進(jìn)行Q次不同的函數(shù)求值問(wèn)詢(xún)得到的結(jié)果是偽隨機(jī)的.第二步使用了通用的歸約技巧“on-the-fly” 轉(zhuǎn)換, 由受限偽隨機(jī)函數(shù)構(gòu)造正常的偽隨機(jī)函數(shù).D?ttling 等以FBPR,Dir[18]實(shí)例化了這一通用構(gòu)造方案, 也得到了一個(gè)基于LWE 假設(shè)的偽隨機(jī)函數(shù)方案,記作FDS,Dir.該方案具有幾乎緊致安全性, 模數(shù)規(guī)模為q=κω(logκ), 且是NC1+o(1)電路可實(shí)現(xiàn)的.

表1 整理了現(xiàn)有格上偽隨機(jī)函數(shù)方案的安全性(即敵手打破方案?jìng)坞S機(jī)性的優(yōu)勢(shì))、基于的底層LWE問(wèn)題的模數(shù)規(guī)模以及方案的并行性.這些偽隨機(jī)函數(shù)方案很多有其對(duì)應(yīng)的基于環(huán)困難問(wèn)題的版本, 這些環(huán)版本的方案與非環(huán)版本方案的構(gòu)造方式一致, 但往往在方案的效率以及參數(shù)規(guī)模上有更好的表現(xiàn); 部分方案, 如文獻(xiàn)[18,22], 還在并行性上有所提升.對(duì)于環(huán)版本方案的結(jié)果, 表1 也進(jìn)行了標(biāo)注.

表1 基于格困難問(wèn)題的偽隨機(jī)函數(shù)方案Table 1 Lattice-based pseudorandom functions

5 基于格的擴(kuò)展偽隨機(jī)函數(shù)

除偽隨機(jī)函數(shù)外, 密碼學(xué)家們還不斷地探索如何基于格困難問(wèn)題設(shè)計(jì)具備額外功能的偽隨機(jī)函數(shù), 如具有密鑰同態(tài)性質(zhì)的偽隨機(jī)函數(shù)、約束偽隨機(jī)函數(shù)(constrained pseudorandom function,CPRF)、水印偽隨機(jī)函數(shù)(watermarkable pseudorandom function, WPRF) 以及可驗(yàn)證偽隨機(jī)函數(shù)(verifiable random function, VRF) 等.本節(jié)將對(duì)格上擴(kuò)展偽隨機(jī)函數(shù)的研究進(jìn)展進(jìn)行討論.

5.1 具有密鑰同態(tài)性質(zhì)的偽隨機(jī)函數(shù)

具有密鑰同態(tài)性質(zhì)的偽隨機(jī)函數(shù)最早在文獻(xiàn)[25]中提出,后續(xù),Boneh 等[3]給出了它的正式定義.稱(chēng)偽隨機(jī)函數(shù)F:K×{0,1}? →{0,1}y具有密鑰同態(tài)性質(zhì), 如果密鑰空間及其上的運(yùn)算(K,?)、輸出空間及其上的運(yùn)算({0,1}y,⊕) 構(gòu)成群, 且對(duì)任意密鑰k1,k2∈K以及消息x有F(k1?k2,x) =F(k1,x)⊕F(k2,x).有時(shí)會(huì)對(duì)這一定義進(jìn)行放松, 稱(chēng)F具有γ-幾乎密鑰同態(tài)性質(zhì)(γ-almost key homomorphic), 如果有F(k1?k2,x)=F(k1,x)⊕F(k2,x)⊕e, 且e ∈[0,γ]y.具有(幾乎) 密鑰同態(tài)性質(zhì)的偽隨機(jī)函數(shù)可以用于設(shè)計(jì)對(duì)稱(chēng)密鑰版本的代理重加密以及可更新加密方案.前述文獻(xiàn)[3,20,23] 中的偽隨機(jī)函數(shù)方案都具有幾乎密鑰同態(tài)性.

5.2 約束偽隨機(jī)函數(shù)/穿孔偽隨機(jī)函數(shù)

約束偽隨機(jī)函數(shù)的概念是由Boneh 和Waters[65]在2013 年提出的, Kiayias 等[66]和Boyle 等[67]也在同時(shí)期的獨(dú)立工作中提出了類(lèi)似的概念.約束偽隨機(jī)函數(shù)允許通過(guò)約束函數(shù)來(lái)限制函數(shù)值的計(jì)算:CPRF 的主私鑰msk 可以對(duì)約束函數(shù)f派生出密鑰skf; 對(duì)于滿(mǎn)足約束函數(shù)的輸入, 即輸入x滿(mǎn)足f(x) = 1, 可以通過(guò)派生密鑰計(jì)算函數(shù)值; 對(duì)于不滿(mǎn)足約束函數(shù)的輸入, 即使已知派生密鑰, 其函數(shù)計(jì)算結(jié)果仍是偽隨機(jī)的.穿孔偽隨機(jī)函數(shù)(puncturable PRF, PPRF) 可以看作支持特殊約束函數(shù)的約束偽隨機(jī)函數(shù), PPRF 的約束函數(shù)是由某個(gè)點(diǎn)集S確定的, 即約束函數(shù)fS(x)=1 當(dāng)且僅當(dāng)x ∈S.

Brakerski 等[26]基于格困難問(wèn)題設(shè)計(jì)了支持給定深度的電路族的約束偽隨機(jī)函數(shù), 該方案同時(shí)具有密鑰同態(tài)性.Boneh 等[27]基于格困難問(wèn)題設(shè)計(jì)了具有約束隱藏屬性的穿孔偽隨機(jī)函數(shù).Canetti 等[28]及Chen 等[29]基于LWE 假設(shè)設(shè)計(jì)了支持NC1電路的具有約束隱藏屬性的約束偽隨機(jī)函數(shù)(constrainthiding CPRF, CHCPRF).Brakerski 等[30]以及Peikert 等[31]則分別基于LWE 假設(shè)設(shè)計(jì)了支持任意多項(xiàng)式規(guī)模電路的CHCPRF.Davidson 等[32]在標(biāo)準(zhǔn)模型下基于LWE 假設(shè)設(shè)計(jì)了一個(gè)支持內(nèi)積函數(shù)的具有自適應(yīng)安全性的約束偽隨機(jī)函數(shù).此外, 他們?cè)跇?biāo)準(zhǔn)模型下基于LWE 假設(shè)以及不可區(qū)分混淆(indistinguishability obfuscation, IO) 設(shè)計(jì)了一個(gè)支持P/Poly 電路的具有O(1)-抗合謀安全性的約束偽隨機(jī)函數(shù).

5.3 水印偽隨機(jī)函數(shù)

水印技術(shù)允許在程序中嵌入一個(gè)“標(biāo)記”, 同時(shí)不會(huì)影響程序的正常工作.其有兩個(gè)基本的性質(zhì)要求:一方面, 應(yīng)當(dāng)存在提取算法可以從嵌入水印的程序中將水印提取出來(lái); 另一方面, 在不破壞程序功能的情況下將水印移除是很難實(shí)現(xiàn)的, 即水印不可移除.水印技術(shù)在數(shù)字版權(quán)保護(hù)方面有重要應(yīng)用價(jià)值, 可以用于盜版追蹤以及解決版權(quán)糾紛等.Kim 等[33]提出了首個(gè)基于格困難問(wèn)題的水印偽隨機(jī)函數(shù)方案, 該方案實(shí)現(xiàn)了一種弱的水印不可移除性, 即安全實(shí)驗(yàn)中不允許敵手詢(xún)問(wèn)水印提取預(yù)言機(jī).后續(xù), Quach 等[34]提出的基于格的水印偽隨機(jī)函數(shù)實(shí)現(xiàn)了更強(qiáng)的水印不可移除性, 即使敵手訪(fǎng)問(wèn)了水印提取預(yù)言機(jī), 仍然無(wú)法在不破壞偽隨機(jī)函數(shù)功能的情況下移除水印.但是Quach 等的方案存在水印密鑰權(quán)限過(guò)大的問(wèn)題, 水印密鑰的持有者可以破壞偽隨機(jī)函數(shù)的偽隨機(jī)性.Kim 等[35]基于LWE 問(wèn)題分別在標(biāo)準(zhǔn)模型下和隨機(jī)預(yù)言機(jī)模型下設(shè)計(jì)了具有強(qiáng)水印不可移除性的水印偽隨機(jī)函數(shù)方案, 且(部分) 避免了水印密鑰權(quán)限過(guò)大的問(wèn)題.Kitagawa 等[36]首次考慮能夠抵抗量子敵手的水印偽隨機(jī)函數(shù), 并給出了一個(gè)基于LWE 的支持秘密提取的WPRF 方案和一個(gè)基于LWE 和IO 的支持公開(kāi)提取的WPRF 方案.

5.4 可驗(yàn)證偽隨機(jī)函數(shù)

可驗(yàn)證偽隨機(jī)函數(shù)是Micali 等[68]在1999 年提出的, 其允許對(duì)函數(shù)值進(jìn)行公開(kāi)驗(yàn)證, 同時(shí)不破壞函數(shù)計(jì)算結(jié)果的偽隨機(jī)性.可驗(yàn)證偽隨機(jī)函數(shù)與非交互式零知識(shí)(non-interactive zero-knowledge, NIZK)證明系統(tǒng)有密切聯(lián)系, 且可以用于設(shè)計(jì)區(qū)塊鏈協(xié)議、電子彩票和電子貨幣系統(tǒng).目前大部分可驗(yàn)證偽隨機(jī)函數(shù)方案[64,69–76]都是在配對(duì)群上的構(gòu)造; 文獻(xiàn)[77] 和[78] 同時(shí)期提出了一個(gè)可驗(yàn)證偽隨機(jī)函數(shù)的通用構(gòu)造方案, 使用了非交互式證據(jù)不可區(qū)分證明系統(tǒng)、承諾方案以及約束偽隨機(jī)函數(shù)作為組件, 但是這一通用構(gòu)造尚沒(méi)有完全基于格困難問(wèn)題的實(shí)例化方案.Chase 等[37]在公開(kāi)參數(shù)模型下可驗(yàn)證偽隨機(jī)函數(shù)的基礎(chǔ)上增加了對(duì)于可模擬性的要求, 提出了可模擬的可驗(yàn)證偽隨機(jī)函數(shù)(simulatable verifiable random function, sVRF), 給出了一個(gè)基于NIZK、承諾方案以及偽隨機(jī)函數(shù)的sVRF 通用構(gòu)造方案以及一個(gè)基于配對(duì)群的直接構(gòu)造方案.Brunetta 等[38]嘗試基于格假設(shè)對(duì)Chase 等提出的sVRF 通用構(gòu)造進(jìn)行實(shí)例化, 但是這一實(shí)例化并不完整(其中一個(gè)組件尚沒(méi)有基于格困難問(wèn)題的實(shí)例化).Li 等[39]提出了一個(gè)新的sVRF 通用構(gòu)造方案, 并在標(biāo)準(zhǔn)模型下基于LWE 假設(shè)對(duì)這一通用構(gòu)造進(jìn)行了實(shí)例化.

6 結(jié)論

本文從偽隨機(jī)函數(shù)的通用構(gòu)造方案、設(shè)計(jì)偽隨機(jī)函數(shù)常用的底層格困難問(wèn)題、基于格的偽隨機(jī)函數(shù)以及基于格的擴(kuò)展偽隨機(jī)函數(shù)這四個(gè)方面, 對(duì)格上偽隨機(jī)函數(shù)的國(guó)內(nèi)外研究現(xiàn)狀進(jìn)行了較為詳細(xì)的總結(jié).偽隨機(jī)函數(shù)作為密碼學(xué)領(lǐng)域的基礎(chǔ)原語(yǔ)之一, 在對(duì)稱(chēng)密碼和公鑰密碼方案設(shè)計(jì)以及解決現(xiàn)實(shí)問(wèn)題上都有重要應(yīng)用.作為底層組件, 偽隨機(jī)函數(shù)的安全性以及效率將會(huì)直接影響頂層方案的安全性以及效率.因此如何設(shè)計(jì)安全、高效的偽隨機(jī)函數(shù)方案一直都是密碼領(lǐng)域備受關(guān)注的問(wèn)題.格理論經(jīng)歷了30 多年的發(fā)展成熟,在同態(tài)加密以及其他高級(jí)密碼方案的設(shè)計(jì)方面證明了其強(qiáng)大的能力; 此外, 格上的困難問(wèn)題被普遍認(rèn)為具備抵抗量子攻擊的特性, 在后量子密碼體制研究中亦處于關(guān)鍵地位.自然地, 如何基于格困難問(wèn)題設(shè)計(jì)偽隨機(jī)方案是一個(gè)很好的研究課題.從2012 年至今, 密碼學(xué)家們?cè)诨诟窭щy問(wèn)題設(shè)計(jì)偽隨機(jī)函數(shù)方面取得了諸多成果, 盡管如此, 格上偽隨機(jī)函數(shù)仍然有進(jìn)一步發(fā)展和完善的空間, 無(wú)論是在方案安全性、效率或并行性上的提升, 還是豐富其功能以及應(yīng)用場(chǎng)景等方面都有進(jìn)一步研究的價(jià)值.本文給出一些值得進(jìn)一步研究的方向供讀者參考.

? 目前已有基于多項(xiàng)式模數(shù)LWE 假設(shè)且可以在NC1+o(1)電路內(nèi)實(shí)現(xiàn)的偽隨機(jī)函數(shù)方案[24]; 存在NC1電路可實(shí)現(xiàn)的PRF 方案, 但是依賴(lài)于指數(shù)規(guī)模模數(shù)的環(huán)LWE 假設(shè)[18,22].那么是否能設(shè)計(jì)PRF, 使其安全性能基于多項(xiàng)式模數(shù)LWE 假設(shè), 且能在NC1電路內(nèi)實(shí)現(xiàn)?

? 目前有許多方案對(duì)格上的偽隨機(jī)函數(shù)進(jìn)行了功能擴(kuò)展, 如可模擬可驗(yàn)證偽隨機(jī)函數(shù), 支持多項(xiàng)式規(guī)模電路或抗合謀的約束偽隨機(jī)函數(shù), 具有不可移除性、不可偽造性、公開(kāi)可嵌入或公開(kāi)可提取性質(zhì)的帶水印的偽隨機(jī)函數(shù)等.但是這些方案具有很高復(fù)雜度, 更多是提供理論上存在的證明, 距離實(shí)際應(yīng)用還有一定差距.因此, 基于格設(shè)計(jì)具有擴(kuò)展功能的偽隨機(jī)函數(shù), 如何避免使用類(lèi)似非交互零知識(shí)證明、不可區(qū)分混淆或是多線(xiàn)性配對(duì)等復(fù)雜組件？如何在所依賴(lài)安全假設(shè)的強(qiáng)度、參數(shù)的規(guī)模以及方案效率上進(jìn)行改進(jìn)？這些都是很好的研究方向.此外, 隨著(功能擴(kuò)展) 偽隨機(jī)函數(shù)應(yīng)用場(chǎng)景的不斷開(kāi)發(fā), 對(duì)現(xiàn)有(功能擴(kuò)展) 偽隨機(jī)函數(shù)又會(huì)不斷提出新的功能、屬性上的要求, 如何基于格困難問(wèn)題設(shè)計(jì)偽隨機(jī)函數(shù)變種以滿(mǎn)足新的應(yīng)用需求？這也是一個(gè)值得研究的問(wèn)題.