什麼是複雜性利用
複雜性利用是一種通常用於證明選擇性安全方案的自適應安全性的技術。例如：我們可以使用複雜性槓桿證明 Yao 的亂碼方案的自適應安全性。許多論文提到了複雜性利用，但沒有詳細介紹。如果有人能用一個詳細的例子來解釋複雜性，我將不勝感激。
複雜性利用是一種降低類型，其中“降低算法”在比對手更大的複雜性類別中執行。例如，可以建構一個及時執行的模擬器 $ n^{\log n} $ 雖然對手只是多項式時間。在考慮模擬範式時，這不是很令人滿意。例如，在零知識中，論點是對手什麼都學不到，因為它可以通過執行模擬器本身來生成它看到的任何東西。然而，當使用複雜性利用時，攻擊者實際上無法執行模擬器（因為它屬於較低複雜性的類）。然而，在某些情況下，它可能是有意義的。例如，讓我們考慮一個“基於遊戲”或基於不可區分性的安全概念。然後我們證明，如果一個在多項式時間內執行的對手可以破壞我們的方案，那麼就存在一個在時間上執行的對手說 $ n^{\log n} $ 誰可以破壞散列函式（或其他任何東西；這只是一個例子）。現在，如果假設散列函式對於任何及時執行的對手都是安全的 $ n^{\log n} $ 那麼這足以保證我們方案的安全性。
我個人不是複雜性利用的忠實擁護者。除了在某些情況下定義的缺點（例如，使用模擬）之外，還有一個很大的缺點是它需要一個更強大的假設（不是原語不能被多時間對手破壞，而是被超多時間對手破壞對於某些特定功能）。但是，它已成功用於實現其他未知的事情。此外，在許多情況下，第一個構造使用複雜性槓桿，然後後來的構造成功地擺脫了假設。
========
後面補充：需要更強的假設的原因如下。假設您從 ZK 減少到 OWF，以便任何將模擬與具有不可忽略機率的實際執行區分開來的算法都可以以不可忽略的機率反轉 OWF。現在，假設您使用準多項式仿真。為了證明對手什麼也沒學到，你需要假設單向函式對準多項式逆變器是安全的。這是因為，為了用模擬的證明執行替換真實的證明執行，您需要在準多項式時間內執行。所以，現在你有一個實際執行的準多項式時間對手。然後，只有在對手無法破壞 OWF 的情況下，減少 OWF 才會起作用。（當然，這一切都是徒勞的，但這就是證明中發生的事情。）