為什麼互動式證明中的證明者在計算空間的指數時間內執行?
我目前正在嘗試了解可驗證計算以及過去方法的優缺點。
特別是,我一直在觀看以下YouTube 影片,其中討論了互動式證明作為驗證計算知識的一種方式。在時間 11:55 出現的幻燈片上,它提到證明者在計算空間中需要指數時間。誰能解釋這是怎麼回事?
我也對每一個確定性計算都有一個互動式證明的說法感到困惑。
我試過閱讀下面的論文,但似乎無法找到對這些結果的明確解釋。任何幫助將非常感激!
參考:
隆德,卡斯滕等人。“互動式證明系統的代數方法”。ACM 雜誌 (JACM) 39.4 (1992): 859-868。
沙米爾,阿迪。“IP = pspace。” ACM 雜誌 (JACM) 39.4 (1992): 869-877。
可驗證計算的全部意義在於允許驗證者驗證計算是否正確執行,而無需自己執行計算。因為像往常一樣,我們將“多項式時間”與“高效計算”聯繫起來,如果計算需要多時間,那麼使用可驗證計算就沒有意義,因為驗證者也可以自己執行計算。
在一般的證明系統中,如果驗證者可以自己確定所討論陳述的真實性,則根本不需要證明者。
以下是對您第一個問題的回答。
這是我發現很難用通常的互動式證明展示來掌握的一件事,所以我認為這是一個很好的問題。
互動式證明有兩個總體目標。
- 首先,驗證者應該只需要進行廉價的計算(高效,即多項式時間)來確信一個陳述是正確的。
- 其次,無論他願意付出多少計算努力,證明者都不應該能夠始終如一地說服驗證者接受一個非事實。(這就是給我們一個“證明”的原因。)
大多數學生沒有想到的是,雖然驗證者必須是高效的,但並不要求證明者應該是高效的。因此,在範例中,效率不高的證明者往往會不時出現。
為什麼我們不要求證明者高效?我不是這方面的專家,但我相信它為我們提供了更豐富、更普遍的理論。從理論的角度來看,這是一個完全有效的觀點。
然而,當互動式證明的理論與密碼學發生衝突時,這對學生來說就變得很尷尬,因為在密碼學中,一個非高效的證明者似乎沒有意義。顯然,允許作弊證明者無效是有一定價值的(類似於資訊論安全性),但在密碼學中,我們實際上打算(至少在理論上)執行一個非作弊證明者,這意味著它必須是高效的。因此,互動式證明的通常定義在密碼學中沒有直覺意義。
總結一下:互動式證明的理論不是密碼學。該理論並不完全適用於密碼學。但是,它對於密碼學至關重要。