帶有“熱”位參數量的 PRF / 散列函式？
是否存在可以將輸出中“熱比特”的數量作為參數的加密安全散列函式（或密鑰 PRF）？如果是這樣，名字是什麼？這裡的目標是生成一個加密安全的偽隨機位遮罩，遮罩中的位數固定。
例如 $ \text{some_magic_hash}(x; 12) $ 應該產生一個正好有 12 個正位的位串。
我將回答 PRF 的問題，我不知道是否可以安全地散列到相應的集合中。
那麼，我們實際上想要在這裡實現什麼？我們想要創建一系列具有一定長度的所有位串的共同域的偽隨機函式 $ \ell $ 漢明權重 $ w $ . 即，集 $$ Y_{\ell,w}=\bigl{y\in {0,1} \mid \mathsf{hw}(x) = w\bigr}. $$
我實際上會回答一個更普遍的問題。
定理。 讓 $ Y $ 成為一個集合併讓 $ \mathcal{S} $ 是一種高效的（即 PPT）算法，從 $ Y $ . 我們表示 $ y := \mathcal{S}(r) $ 的輸出 $ \mathcal{S} $ 用隨機硬幣抽樣時 $ r $ . 存在一族具有共域的偽隨機函式 $ Y $ ，如果一個正則的偽隨機函式族（即具有共域 $ {0,1}^n $ 存在。
**證明。**讓 $ p $ 是一個限制執行時間的多項式 $ \mathcal{S} $ . 讓 $ F : {0,1}^n \times {0,1}^n \to {0,1}^{p(n)} $ 是一個 PRF 家族。¹我們建構了一個 PRF 家族 $ G {0,1}^n \times {0,1}^n \to Y $ 作為 $ G(x) := \mathcal{S}(F(x)) $ .
我們可以證明 $ G $ 是一個 PRF，使用了對安全性的平凡簡化 $ F $ . 讓 $ A $ 是一個任意的 PPT 區分器 $ G $ . 我們構造一個區分器 $ B $ 為了 $ F $ 如下。輸入安全參數 $ 1^n $ 並被授予訪問神諭的權限， $ B $ 呼叫 $ A(1^n) $ . 每當 $ A $ 用輸入查詢它的預言機 $ x $ , $ B $ 前鋒 $ x $ 到它自己的神諭，接收 $ y $ 作為響應並返回 $ \mathcal{S}(y) $ 至 $ A $ . 最終 $ A $ 將輸出位 $ b $ ， 哪個 $ B $ 也會輸出。
如果 $ B $ 可以訪問實現真正隨機函式的預言機 $ f $ ，然後它的響應 $ A $ 根據定義 $ \mathcal{S} $ 均勻分佈，因此， $ B $ 完美地模擬了一個隨機函式 $ g : {0,1}^n \to Y $ 在這種情況下。另一方面，如果， $ B $ 可以訪問執行的預言機 $ F(k,\cdot) $ ，那麼就完美模擬了 $ G(k,\cdot) $ .
因此， $ B $ 區分 $ F $ 從具有相同優勢的隨機函式 $ A $ 區分 $ G $ 從一個隨機函式。自從 $ F $ 是一個PRF，優點是 $ A $ 因此必須可以忽略不計，並且 $ G $ 因此也是一個 PRF。 $ \tag*{$\square$} $
有待證明的是， $ Y_{\ell,w} $ 可以在嚴格的多項式時間內均勻採樣。可悲的是，情況並非如此。² 從 $ Y_{\ell,w} $ , 是採樣 $ w $ 唯一索引 $ i_1,\dots,i_w \in {0,\dots,\ell-1} $ 並返回代表的位串$$ \sum_{j=1}^w 2^{i_j} $$在大端。
這種策略的問題在於它涉及在 $ 0 $ 和 $ \ell-j $ 為了 $ j = 1,\dots,w+1 $ . 然而，在嚴格的多項式時間內使用二進制隨機硬幣是不可能的，除非 $ \ell-j $ 是一種力量 $ 2 $ . 然而，我們可以做兩件事：
- 我們可以使用拒絕採樣在預期多項式時間內均勻採樣。然而，這意味著我們上面的歸約現在不再在嚴格的多項式時間內執行，所以我們需要處理這個問題，這很快就會變得醜陋。
- 我們可以在嚴格多項式時間內任意採樣*接近均勻。*這通過對整數進行採樣來工作 $ I $ 之間 $ 0 $ 和 $ 2^a \gg \ell $ 和設置 $ i=I \bmod \ell $ . 在這種情況下，即使在製服的情況下， $ \mathsf{S} $ 採樣不均勻。但是，它在統計上任意地採樣接近均勻，這使得上述證明仍然可以通過。
¹ 請注意，具有共同域的 PRF $ {0,1}^n $ 和 $ {0,1}^{p(n)} $ 對於任何多項式都是存在等價的 $ p $ . ² 我現在沒有證據證明這一點，但如果有一些策略可以做到這一點，我會感到非常驚訝。