제로 널리지 프로토콜

위키백과, 우리 모두의 백과사전.
(영지식 증명에서 넘어옴)
이동: 둘러보기, 검색

영지식 증명(零知識 證明, 영어: zero-knowledge proof) 또는 제로 널리지 프로토콜(영어: zero-knowledge protocol)은 암호학에서 누군가가 상대방에게 어떤 문장(statement)이 참이라는 것을 증명할 때, 그 문장의 참 거짓 여부를 제외한 어떤 것도 노출되지 않는 interactive한 절차를 뜻한다.

어떤 문장이 참이라는 것을 증명하려는 쪽을 증명자(證明者, prover)라 하고, 증명 과정에 참여하여 증명자와 정보를 주고 받는 쪽을 검증자 (檢證者, verifier)라고 한다. 영지식 증명에 참여하는 당사자들이 상대방을 속이려는 목적으로 프로토콜을 임의로 변경하는 경우, 당사자들이 부정직하다 또는 정직하지 않다 (dishonest, 혹은 cheating)고 한다. 그 외의 경우에는, 정직하다고 한다.

영지식 증명은 다음과 같은 세가지 성질을 만족시켜야 한다.

  1. 완전성(完全性, completeness): 어떤 문장이 참이면, 정직한 증명자는 정직한 검증자에게 이 사실을 납득시킬 수 있어야 한다.
  2. 건실성(健實性, soundness): 어떤 문장이 거짓이면, 어떠한 부정직한 증명자라도 정직한 검증자에게 이 문장이 사실이라고 납득시킬 수 없어야 한다.
  3. 영지식성 (零知識性, zero-knowledgeness): 어떤 문장이 참이면, 검증자는 문장의 참 거짓 이외에는 아무것도 알 수 없어야 한다.