PUF 硬體如何與質詢/響應位數成正比？
維基百科文章聲稱物理不可複製功能優於 ROM，因為它們需要更少的硬體：
與包含對所有可能挑戰的響應表的 ROM 不同，ROM 需要在挑戰位數量上呈指數增長的硬體，PUF 可以在硬體中與挑戰和響應位的數量成比例地建構。
然後，給出了 PUF 的範例，例如在啟動時讀取 DRAM 中存在的特定於設備的簽名，這確實需要指數級硬體。其他類型的 PUF 基於不同的物理原理（光學、機械、磁性），這些原理對特定於設備的差異進行編碼，但我看不出使用不同的物理原理如何導致線性（而不是指數）硬體要求。
有人可以提供此類硬體的範例或解釋如何在 PUF 中實現如此低的硬體要求嗎？
要僅在 ROM 中實現質詢-響應（無需計算），您基本上需要一個查找表，即從質詢到響應的映射。所以對於一個 $ k $ 有點挑戰，你需要 $ 2^k $ 查找表中的條目。
這將如何在 PUF 上工作？
考慮以下 PUF 範例（取自改進的環形振盪器 PUF：一種 FPGA-friendly Secure Primitive，Journal of Cryptology，2011 年）：
右側部分顯示了環形振盪器 (RO)，其值將完全取決於製造過程，因此是“不可複製的”。您將這些 RO 放在一起，輸入兩個 MUX，挑戰決定選擇哪個 RO 值。最後，兩個 MUX 的輸出用於遞增兩個計數器，這些計數器（在一段時間後）用於通過比較來確定單個位。您的 $ k $ 位質詢可以分成更小的質詢，以便從 PUF 獲得比單個位更大的響應。這將是一個確定性的過程，因此給定相同的 $ k $ 位挑戰，您會得到相同的響應（實際上，響應中存在位翻轉的可能性，因此通常會進行一些糾錯）。
為了獲得一個安全的 $ k $ 位響應，您將需要一定數量的 RO，但您不需要指數數量的 RO。如果你有 $ N $ RO，有 $ N(N-1)/2 $ 不同的 RO 對。每個配對可用於使用上面顯示的設置生成單個位。但是，如用於設備身份驗證和密鑰生成的物理不可複製函式中所述，電路的熵不會那麼高。在那篇論文中，作者推導出電路的最大熵為 $ \log_2(N!) $ . 所以對於一個想要的 $ k $ ，你可以計算 $ N $ . 作為一種替代方法，作者指出，為簡單起見，您可以設計系統，使每個振盪器僅用於任何挑戰值一次。如果你這樣做了，你需要 $ 2k $ 振盪器產生一個 $ k $ 位響應。我會注意到，由於糾錯，您可能需要額外的位，但這只會將振盪器的數量增加一個常數因子。
現在，如何在質詢/響應協議中使用它。好吧，首先必須有一個受信任的設置。挑戰者在乾淨的環境中，向 PUF 發送一堆挑戰並記錄響應。因此，挑戰者可能必鬚根據應用程序儲存大量挑戰/響應對。關鍵是，硬體不必儲存所有這些資訊。
然後，當系統投入使用時，挑戰者向設備發送挑戰。設備通過 PUF 執行它並返迴響應。無法訪問 PUF 的人無法計算出正確的響應。此外，由於 RO 的製造差異，試圖複製 PUF 的人不會成功。這些製造變化，即使非常微妙，也足以使反應不一樣。
