영지식 증명,ZKP

영지식 증명, 零知識證明,

Zero-Knowledge Proof, ZKP

개인(prover)이 자신만이 가진 비밀 정보를 공개하지 않고 상대방인

확인자(verifier)에게 정보를 알고 있음을 증명할 수 있는 암호화 체계.

예를 들어 동굴 입구에는 두 개의 갈림길이 있고, 동굴 내에서 서로 통하는 비밀문이 있다.

이때 비밀문의 키를 가진 개인은 증명자(prover)이며, 비밀문의 키를 가지고 있다는 것을

확인하고자 하는 사람은 확인자(verifier)다. 2개의 갈림길로 연결되는 동굴 안쪽의

비밀 문을 혼자 알고 있는 증명자가 비밀 문이 있다는 것을 알리지 않고,

동굴 반대편으로 나올 수 있는 비밀 문을 알고 있다는 것을 확인자에게 검증받으려고 할 때 다음과 같은 방법으로 증명할 수 있다.

1) 증명자는 동굴에 있는 2개의 갈림길 중 임의로 1개를 선택하여 들어간다,

이때 확인자는 증명자가 어느 갈림길로 들어가는지 볼 수 없다.

2) 확인자는 동굴 입구로 들어와 임의로 1개의 갈림길을 지정하고 증명자가 그 갈림길로 나오게 지시한다.

3) 증명자는 비밀키를 이용하여 지정된 갈림길로 나온다.

4) 1)~3) 과정을 n번 반복하여 확인자가 지시한 갈림길로 증명자가 모두 나오는 경우 증명자가 비밀 문을 알고 있다고 검증한다

증명자가 들어간 갈림길로 확인자가 나오라고 지시할 확률은 1/2이다.

즉, 비밀 문을 몰라도 지시에 맞게 나올 확률이 1/2이다.

따라서 n번 이렇게 될 가능성은 1/2n이다. 그러므로

2) 과정에서 증명자가 n번 모두 확인자가 원하는 길로 나오는 경우 높은 확률로 비밀 문을 알고 있다고 할 수 있다.

다음 예제는 이산대수 문제의 어려움에 바탕을 둔 것으로 영지식 증명으로 구현이 가능하다.

비밀정보 x를 알고 있는 증명자가 x를 노출하지 않고 알고 있다는 것을 증명하려고 한다.

증명자와 확인자는 큰 소수 p, Zp*={1,2,...,p-1}=를 이용하여 검증하기로 약속한다(단, 1 < x < p-1).

이때 검증 과정은 다음과 같다.

1) 증명자는 Y = gx ∈ Zp*를 구하여 확인자에게 전달한다.

2) 증명자는 무작위 값 r(1 < r < p-1)을 선택하고 C = gr ∈ Zp*를 계산하여 확인자에게 전달한다.

3) 확인자는 1) (x+r) mod (p-1) 또는 2) r 를 요구한다.

1)의 경우 g(x+r) mod (p-1) = C·Y mod p로

2)의 경우 C = gr mod p로 검증한다.

4) 1), 2) 과정을 n번 반복하여, 3)의 검증을 모두 통과하는 경우 증명자는 x를 알고 있다고 검증한다.

즉, 3)의 검증 과정에서 확인자의 r 요구는 증명자의 정직성 - (x+r) mod (p-1) 또는 x를 안다는 것 - 을 검증하기 위한 것이다.

이와 같이 영지식 증명은 완전성, 건실성, 영지식성을 만족하여야 한다.

- 완전성(completeness): 어떤 문장(statement)이 참이면 정직한 증명자는

정직한 확인자에게 참인 사실을 확신시킬 수 있어야 한다.

- 건실성(soundness): 어떤 문장(statement)이 거짓이면, 어떠한 부정직한 증명자라도

정직한 확인자에게 이 문장이 참이라고 확신시킬 수 없어야 한다.

- 영지식성(zero-knowledge): 어떤 문장(statement)이 참이면,

확인자는 문장의 참 이외에는 아무것도 알 수 없어야 한다.

영지식 증명은 비밀유지의 목적뿐만 아니라,

암호화폐에서 사용자의 익명성과 거래정보의 익명성을 제공하는 데 사용된다.

영지식.JPG

출처:TTA 정보통신 용어사전

게시물 댓글 0개

상세페이지