支援零知識查詢的集合封存方案

Abstract

在離散對數問題很難在多項式時間解決的假設下，Micali, Rabin, 和Kilian 三位作者提供了一個零知識的集合封存法，此集合是由有限個字串所組成。事先給定一個公開且夠隨機的字串，此集合封存法以非交談式的方法運作如下：證明者先將他的集合在多項式時間內封存起來，並且公開一個字串以代表此集合。之後證明者可根據驗證者所提出的問題對於某字串在或不在集合中給出證明，驗證者可以根據事先給定的字串以及公開的字串來驗證證明者給出的證明是否正確。此三位作者的集合封存法有一個很好的性質是驗證者無法根據證明者給出的證明計算出他本來在多項式時間內算不出來的資訊。 Micali 等作者提供的方法不能直接推廣到一段範圍的查詢，Ostrovsky, Racko , 和 Smith 三位作者提供另一種集合封存法來處理這類型的查詢並將每個字串皆視為某個正整數。此推廣犧牲的是在證明過程中驗證者會得知此集合的正整數個數，並且是交談式的證明法。除此之外，此集合封存法仍然讓驗證者無法根據證明者給出的證明計算出他本來在多項式時間內算不出來的資訊。 在這篇論文中，我們對Ostrovsky 等作者的結果再加以延伸，因此，我們的集合封存法仍然是交談式的證明法且驗證者會得知此集合的正整數個數。然而我們提供了更多的問題可以查詢，包括了加法、減法與乘法的查詢，且仍然讓驗證者無法根據證明者給出的證明計算出他本來在多項式時間內算不出來的資訊。