一切の情報を漏らさずプログラムの正当性を証明する方法

概要

論文の詳細を見る
Suppose you have discovered an efficient algorithm to solve the graph isomorphism problem. The graph isomorphism problem is to decide whether two given graphs are isomorphic or not., i.e. whether there is a bijective mapping (a permutation) from the nodes of one graph to the nodes of the second graph such that the edge connections are preserved. Until today, this problem is still unsolved in the sense that no efficient algorithm for it has yet been found. So, you would strongly like to announce that you have found a new algorithm for the problem by demonstrating the algorithm (the program). However, you must do the demonstration carefully so as to reveal as little information as possible in order to avoid the verifier's getting important information (e.g. the algorithm, on solutions of instances etc.) via your demonstration.
社団法人電子情報通信学会の論文
1995-03-27