LWE 和偽隨機函式
考慮有錯誤的學習問題。假設 LWE（或 LWE 的變體，如環 LWE）對於多項式時間算法來說很難，我們可以從那裡構造一個偽隨機函式族嗎？
你可以。這裡應該提到一個警告 — LWE 問題的硬度（部分）由模量的大小控制 $ q $ . 兩個重要的參數方案是 $ q $ 在安全參數中是多項式大的，並且是**超多項式大的。較小的模量對於效率和安全性都更好。我認為直到最近我們才有來自 LWE 的多項式模數 PRF，例如，參見this。在那篇論文之前，這導致了一個有趣的情況，我們可以從比我們建構 PRF 所需的更弱的晶格假設建構像水平 FHE 之類的東西。
對於超聚 $ q $ 但是，有一些簡單的結構。 這篇論文是一個很好的參考。關鍵思想是 LWE 樣本 $ (a, \langle a,s\rangle + e) $ 是偽隨機的，因此可能是 PRF 的基礎。如果有人試圖寫下一些自然候選人，例如：
$$ F_s(a) = \langle a,s\rangle + e\bmod q $$
有兩個明顯的問題：
- 這只是偽隨機的，如果 $ a $ 是隨機的（所以這是一個“弱 PRF”而不是 PRF — 只是一個稍微不同的密碼原語）
- $ F_s(a) $ 是一個隨機函式—錯誤 $ e $ 必須隨機選擇。
您可以通過將其四捨五入到最接近的倍數來解決第二個問題 $ p $ ，即寫作 $ F_s’(a) = \lfloor \langle a,s\rangle + e\rceil_p $ . 前提是 $ q/p $ 足夠大，隨機選擇 $ e $ 通常只會對最終結果的影響微乎其微，所以我們不妨編寫（確定性）函式 $ F_s’(a) = \lfloor \langle a,s\rangle\rceil_p $ . 或者，這可以看作是根據“*舍入學習”*假設建構的弱 PRF。
要將弱 PRF“升級”為標準 PRF，可以將密鑰設為 $ (A, S_1, \dots, S_k) $ , 並定義
$$ F_{A, S_1,\dots, S_k}(x_1,\dots,x_k) = \left\lfloor A\prod_{i =1}^k S_i^{x_i}\right\rceil_p. $$
在哪裡 $ x_i\in{0,1} $ ， 和 $ A, S_1,\dots, S_k $ 要麼是環元素，要麼是具有適當維度的矩陣，使得表達式有意義。這正是第 5 節第二篇論文中所做的構造。
總之：
- 是的，我們可以從 LWE/晶格問題建構 PRF
- 有效地做到這一點（從小模量）非常困難，但現在知道如何做到（見第一篇論文）
- 從 LWR 問題出發在概念上很簡單，但我們只能將 LWR 問題的安全性建立在 LWE 問題的大模數上。