具有常數個 1 的散列函式
在以下論文：https ://eprint.iacr.org/2018/056.pdf中，隨機預言機定義如下： $ H: *\xrightarrow{} { \mathbf{v} | \mathbf{v} \in R_{q,[1]}, || \mathbf{v}||_{1}=\omega} $
在哪裡 $ R_{q,[1]} $ 代表那些屬於環的元素 $ R_{q}=Z_{q}/<x^n+1> $ 並且係數介於
$$ -1,1 $$. 這些隨機預言機安全嗎？如果是這樣，哪個雜湊函式可以在不影響安全性的情況下輸出恆定數量的 1？
如果它們表現得像隨機預言機，那麼它們提供與圖像空間大小相稱的安全性，即 $ 2^\omega\binom n\omega $ （注意有 $ \omega $ 非零條目，每個條目都可以是正數或負數）。因此，如果安全性因在 $ H $ 這應該需要 $ O(2^{\omega/2}\sqrt{\binom n\omega}) $ 的評價 $ H $ 找到。對於任何給定的安全級別，都可以找到適當的值 $ n $ 和 $ \omega $ 所需的工作大於安全級別。
實際建構這樣一個最簡單的方法 $ H $ 是適應一個正常的 $ h $ -bit 散列函式，被認為表現得像一個隨機預言機。使用它來生成一個介於 0 和 $ V:=2^\omega\binom n\omega $ （例如，通過將雜湊輸出視為 $ h $ -位整數；如果這個值小於 $ 2^h\mod V $ ，將 1 附加到輸入並迭代，否則將值取模 $ V $ ）。現在拆分值 $ v $ 分為兩個值 $ c:=v/2^\omega $ 和 $ b:=v\mod {2^\omega} $ （注意 $ b $ 和 $ c $ 將是獨立且均勻分佈的模數 $ 2^\omega $ 和 $ \binom n\omega $ 分別）。現在使用 $ c $ 以及這個答案選擇一組的方法 $ \omega $ 非零係數並使用 $ b $ 在係數正負 1 之間進行選擇。