基于LWR的偽隨機(jī)函數(shù)的研究.pdf

1、帶近似學(xué)習(xí)問(wèn)題(LWR)是帶錯(cuò)誤學(xué)習(xí)問(wèn)題(LWE)的一個(gè)變形,它存在一種損耗模式,在損耗模式下LWR抽樣僅僅能揭露關(guān)于密鑰的部分信息,這一特性給了LWR一個(gè)新的歸約證明,與原來(lái)超多項(xiàng)式大小的要求相比,新的歸約對(duì)參數(shù)模的要求只有多項(xiàng)式大小,這大大改進(jìn)了LWR問(wèn)題的安全性和有效性。
　　受到LWR新的歸約方式的啟發(fā),本文首先對(duì)文獻(xiàn)[29]中兩種基于LWR的偽隨機(jī)函數(shù)作了分析研究,其中基于LWR合成器的偽隨機(jī)函數(shù),由于它是直接基于LWR

2、原形的構(gòu)造,所以對(duì)LWR的歸約改進(jìn)對(duì)它同樣有效,但是degree-k偽隨機(jī)函數(shù)由于它并非直接基于LWR原形的構(gòu)造,所以LWR的歸約改進(jìn)對(duì)它并非直接有效,本文中運(yùn)用了一種類似LWR歸約的方式對(duì)degree-k偽隨機(jī)函數(shù)做了新的歸約證明,使它對(duì)參數(shù)模的要求同樣達(dá)到多項(xiàng)式大小的要求。
　　另外,對(duì)于文獻(xiàn)[28]提出的基于格的k-almost密鑰同態(tài)的偽隨機(jī)函數(shù),在該函數(shù)的安全性證明過(guò)程中,要求函數(shù)中兩個(gè)公開(kāi)矩陣必須選自特殊的分布,本文中