Mac
為什麼 Carter-Wegman 式的消息認證不會被 P = NP 破壞？
在研究 P = NP 對密碼學的影響時，我發現有人說唯一剩下的密碼學將是一次性密碼和 Carter-Wegman 式消息身份驗證。雖然一次性墊似乎很明顯，但我不確定 Carter-Wegman-Style 消息身份驗證。誰能解釋一下？
雖然一次性墊似乎很明顯，但我不確定 Carter-Wegman-Style 消息身份驗證。
他們談論的是一種 Carter-Wegman 身份驗證方法，該方法使用隨機比特流作為過程的一部分（就像一次性鍵盤使用隨機比特流進行加密一樣）。
通常，當我們實現 CW 時，我們使用一些幾乎通用 (au) 的雜湊函式，並將其與一些加密對象配對。au 雜湊函式處理被 MACed 的消息；然後使用加密對象來偽裝 au 雜湊輸出。
這是如何工作的：使用 au 散列意味著不知道 au 散列鍵的人不能生成兩條消息，這些消息具有散列到相同值的非平凡機率（並且有許多構造可以證明這一點）。但是，看到 au 雜湊輸出的人可以推斷出很多；因此，我們偽裝中間 au 散列以使用加密對像生成完整散列。
在一次性填充設置中，我們可以做的一件事是用“xor the au-hash with the next set of pad bits”替換加密對象；這也有效地掩蓋了雜湊輸出，因此滿足標準（並且可以執行 NP 的預言機無法恢復 au-hash，因為（就像一次性填充一樣），沒有足夠的資訊來這樣做）。注意：實際上，在這種構造中，您需要一個幾乎通用的 delta 散列函式；如果您關心這些細節，請在單獨的問題中提問。
另一方面，這兩個並不是密碼學工具箱中唯一剩下的東西。此外，我們還有：
- 秘密共享（如果某人的共享數量少於必要數量，他們實際上沒有足夠的資訊來重建秘密）
- 一些密鑰分發方案（有人向各方發布密鑰共享，兩方可以生成相同的密鑰，並且沒有少於 k 個密鑰共享的其他人（其中 k 是一個安全參數）有足夠的資訊來重建他們的秘密。