什麼是理想的記憶硬功能？
這說 $ f_n $ 如果，對於任何空間，是不是很難記憶 $ S $ 和時間 $ T $ , $ S\cdot T \in \Omega(n^2) $ .
我的問題：
- 什麼是 $ S $ ? 空間？例如可用記憶體的字節數？
- 什麼是 $ n $ ? 記憶體硬函式請求的記憶體字節數？
- 什麼是 $ T $ ? 輪數？
- 這個定義有多好？例如，它有多緊？例如 $ \Omega(n^2) $ 是漸近最低界，但我猜不是所有的函式都是 $ \in \Omega(n^2) $ 是平等的。例如，也許有些更好？所以我想這個定義還不夠嚴格，無法向我們展示哪個記憶體硬 KDF 必然更好？
- 有更好的記憶硬度定義嗎？例如，比簡單的更緊 $ \in \Omega(n^2) $ ?
其中許多都在文章中得到了解決。在這種情況下，“對手”是一些可以評估的算法 $ f_n $ 使用的資源比我們希望的要少。
- $ S $ = 對手的空間/記憶體複雜度。在這行工作中， $ f_n $ 是一個呼叫某個隨機預言機的函式 $ H : {0,1}^k \to {0,1}^k $ ， 和 $ S $ 是對手的（最壞情況）空間使用情況，以 $ k $ -位“塊”。
- $ T $ = 對手的時間複雜度。通常以呼叫次數來衡量 $ H $ . 在某些模型中，允許攻擊者並行呼叫 $ H $ 免費，所以 $ T $ 是呼叫“連續輪次”的次數 $ H $ .
- $ n $ = 記憶硬函式的可調硬度參數。較大 $ n $ 增加評估功能所需的工作量 $ f_n $ （理想情況下，工作量成二次方 $ n $ ）。誠實的當事人應該選擇最大的 $ n $ 這樣他們就願意花精力去評估 $ f_n $ .
這個定義有多好？…所以我猜這個定義不夠嚴格，無法向我們展示哪個記憶體硬 KDF 必然更好？
這是真的 $ n^2/1000 $ 與很多不同 $ 1000n^2 $ ，但是這個定義對具有這些難度級別的記憶困難的函式是滿意的。在撰寫本文時，大多數候選記憶困難函式在漸近上比 $ \Theta(n^2) $ . 所以這個定義對於排除很多不好的候選人是相當有效的。一旦你有許多滿足這個漸近定義的候選者，你就可以開始擔心常數因子了。
有更好的記憶硬度定義嗎？
是的，這個定義只考慮了最壞情況下的空間使用情況 $ S $ . 認為 $ f_n $ 是一個確實需要的功能 $ n $ 要評估的記憶體單位——沒有辦法評估 $ f_n $ 沒有持有 $ n $ 在某個時間點的記憶體單位。 這不排除這種可能性 $ n $ 記憶體單位只需要很短的時間視窗。換句話說，可能有一個算法 $ f_n $ 其記憶體使用情況隨時間變化的圖如下所示：
（圖片取自Leo Reyzin 在 scrypt 上的幻燈片）
如果這個算法有最大的空間使用 $ n $ 並且還使用 $ n $ 時間，它的 ST 複雜度是 $ \Omega(n^2) $ . ST-complexity 就像這張圖片中藍色邊界框矩形的區域。
但是這種記憶硬度的測量掩蓋了一些問題。假設對手想要評估 $ f_n $ 在許多不同的輸入上，它巧妙地安排了這些評估，如下所示：
該策略可用於評估範例 $ f_n $ 上 $ n $ 僅使用不同的輸入 $ O(n) $ 時間和 $ O(n) $ 總記憶體！所以評估函式的總“ST成本” $ n $ 時代是 $ O(n^2) $ ，意味著每個實例的攤銷成本僅為 $ O(n) $ .
對函式的記憶硬度進行分類的更好方法是測量曲線下的面積，而不是邊界框的面積。這確實是後續工作中提出的，其中記憶體硬度度量被稱為“累積記憶體複雜度”。
