Zero Knowledge Proof
- 지식의 "전달"없이 지식의 보유가 증명한 것이다.
- IP(Interactive Proof System) 대화형 증명 시스템
P: prover, inform computing
V: verifier, polynomial computing
* shortest path ∈ P
* longest path ⊂ Np- complete
어떤 문제의 instance X가 yes instance일때는 Verifier는 Prover의 증명을 accept한다
어떤 문제의 인스턴스 X가 no instance일때는 , Verifier 는 높은 확률로 Prover의 증명을 reject한다.
NP는 ?
IP의 특수한 경우이다.
- no interaction (상호작용이 존재하지 않고, )
- no일떄 reject될 확률이 100퍼센트이다.
- IP = PSAPCE이다 . 이것은 논문의 한펭
- ZKP
- IP 인데 Verifier가 "전달 받는 " 정보가 없다.
Graph Isomorphic ZKP
- Isomorphic : 그래프 두 개가 같은 지 확인하는 것.
- Graph :node set과 edge set으로 구성된 하나의 집합이다.
- 두 그래프의 모양이 같은지 확인하는 것인데 , 노드의 이름을 바꾸어서 같은 그래프를 만들 수 있으면 모양이 같다는 것인지 확인할 수 있다.
- 문제를 풀려면 쉽게 생각해서는 노드를 각각 바꿔서 비교해볼 수 있다 . n!의 경우를 바꾸어서 풀 수 있는데, n!라는 수는 너무 크기 때문에 2의 n짜리 시간으로 둘 수 있다.
- 그래프가 isomorphic하다는 것을 알게 되면, 답이 yes라는 것을 말하기 쉽다 .
- how? 그래프 2개가 주졌을 때 두개가 isomorphic하다면 실제로 노란 번호를 주면 test를 해서 yes라는 것을 도출할 수 있다.
- 증거를 제시해 줄 수 있고, 답이 yes인데 no라고 속일 수가 없다.
- 답이 yes인것은 쉽게 알려줄 수 있지만, 답이 no라는 것은 쉽게 알려줄 수 없다.
- 가정
- prover : G1과 G2가 isomorphic이라는 것을 알고 있다.
- 즉 G1과 G2의 mapping 정보를 알고 있다.
- V에게 Mapping을 전달하지 않고 G1과 G2가 isomorphic하다는 사실만 전달하려고 한다.
- prover가 isomorphic하다는 사실을 알려주려고 하는데 , mapping을 주지 않고, mapping이 있다는 것만 알려준다(Zero - knowledge)
- IP stype 의 증명을 하면서 정보의 전달은 하지 않고 정보의 보유만 알려준다
- 알고 있는 사실 자체에는 거짓이 없다.
- IP (Interactive proof) 의 조건을 만족하는 프로토콜이 존재해야하므로 이를 증명한다 .
- 그 프로토콜에서 mapping정보가 전달되지 않는다는 것을 증명한다. (어려움)
- Protocol (프로토콜)
- P : G1, G2를 permutate ==> G3 , G3을 Verifier에게 전달
- Verifier는 left / right를 선택한다 .
- P는 선택에 따라 G1 <-> G3, G2 <-> G3매핑을 전달
- P가 할 수 있는 최선은 ½의 확률이상으로 mapping을 알게 되는 것까지만 가능하기 떄문에 거짓말이 불가하다.
- Ip(interactive proof) 알면 아는 것을 전달가능하고 , 모르는 것은 전달할 수 없다는 것을 알게 되었다.