ゼロ知識証明

3-Coloring 問題を考える。 検証者は、解インスタンスの一部のみを reveal されるとする。 reveal された箇所については、正しいことを検証できる。 繰り返しランダムに reveal 箇所を指定することで、本当に知っていると確信に至る。

おそらく、証明したい内容を暗号学的ハッシュ関数で飛ばして、その結果をランダムオラクルとして利用した上で、ゼロ知識証明を行うこと、みたいな形で実現されていると推測される。---2022/12/14