強大的單向功能

在《密碼學基礎-Oded Goldreich-Page 33》一書中，如果我們使用確定性多項式時間算法而不是機率多項式時間算法來處理案例 2（難以求逆），會是什麼情況？

假設我們生活在一個工作中 $ \mathsf{P}\neq\mathsf{BPP} $ - 也就是說，存在可以在隨機多項式時間內解決的問題，但不能通過任何確定性多項式時間算法來解決。換句話說，如果我們將 OWF 定義為對於確定性多時間攻擊者而言難以反轉的函式，我們實際上可能無法真正保證其安全性：在現實世界中，生成隨機位並不難（比如說，使用一些適當的量子設備）。因此，可能存在一種在現實世界中執行良好的攻擊，使用隨機位源，即使 OWF 可能對所有確定性對手都是安全的。因此，這樣的定義不會正確地擷取允許安全密碼應用程序的功能類別。

但請注意，人們普遍認為 $ \mathsf{P} = \mathsf{BPP} $ . 實際上，這是從一些最壞情況下的電路下界（或等效地，存在某種強形式的偽隨機發生器）得出的：如果存在問題 $ \mathsf{DTIME}(2^{O(n)}) $ 具有電路複雜性 $ 2^{\Omega(n)} $ ， 然後 $ \mathsf{P} = \mathsf{BPP} $ .

引用自：https://crypto.stackexchange.com/questions/61956