영지식 상호 증명

정보화 사회가 발달하면서 컴퓨터 네트워크를 통해서 다양한 정보 교환이 이루어지면서 데이터 보호 대책이 요구되기 시작했다. 즉 네트워크 정보 교환이 활발히 이루어지는 현재 상황에서 다양한 데이터 트랜잭션에 대처할 수 있는 응용 프로토콜의 연구 필요성이 높아지게 된 것이다. 응용 프토토콜은 범위가 매우 넓고 개인정보 보호의 역할과 중요성이 높다. 특히 EDI(Electronic Data Interchange)와 NHS(Nessage Handling System), 디지털 서명 등에서의 보안 필요성이 높아진 상태이다. 현재까지 연구된 응용 프로토콜 방식들은 안전성 요구 조건에 부적합하거나 복잡해 실제로 구현하는 데 어려움을 겪고 있었다. 그래서 효율적인 정보보호 프로토콜에 대한 연구를 통해 안전한 보호 프로토콜과 컴퓨터 통신망에서 전송되는 데이터량 및 통신 횟수를 감소시키고자 했다. 여러 암호 함수를 이용한 방식들이 있지만, 그 중 영지식 상호 증명방식(ZKIP : Zero-Knowledge Interactive Proof)이 주목을 받았다.

1985년 Goldwasser, Micali, Rockoff가 영지식 상호 증명 방식에 대한 개념을 최초로 제안했다. 그들은 비트위임(Bit Commitment) 방식이 존재한다는 가정하에서 “모든 NP문제는 ZKIP 방식을 갖는다”며 ZKIP 개념을 확장하였다. 영지식 상호 증명 방식은 비밀을 알고 있다는 사실을 밝히지 않고 증명하는 방식이다. 통상적으로 패스워드 방식을 사용할 때 본인 인증을 위해 비밀 패스워드를 그대로 표시하므로 항상 보안의 위험성이 따른다. 하지만 영지식 상호 증명 방식을 사용하면 일반 난수와 비밀 정보로부터 연산한 결과를 증명자(유저)와 검증자 간 주고받으며 확률적으로 납득시켜 증명하는 방식이다. 결과를 주고받는 횟수가 늘어날수록 확신도도 비례해서 높아진다.

상호 증명 방식은 증명자와 검증자 상호간 메시지를 교환하는 computation을 모델링한 abstract machine(이론적인 컴퓨팅 모델)을 의미한다. 증명자는 전능하고 무한정의 계산 자원을 소유함에도 신뢰할 수 없는 존재이지만, 검증자는 한정된 계산 자원을 소유했지만 신뢰할 수 있는 존재를 의미한다. 그래서 상호 증명 방식과 관련한 대부분 공격 시나리오는 증명자가 악역을 맡고, 이들이 검증자를 속이려고 하는 상황을 가정했다. 검증자역시 전달받은 증명자의 정보를 타인에게 판매하여 부당한 이익을 챙기려는 상황이 일어날 수 있다. 누구나 검증자가 지식을 누설하지 않았다는 사실 여부를 확인할 수 있는지, 검증자가 검증 과정동안 알고 있어야하는 지식 비중이 어느정도인지 의문점이 들 수 밖에 없다. 이 의문점을 해결하기 위해 ZKIP의 개념이 나오게 되었다.

하지만 영지식을 이용한 프로토콜은 안정성을 제공하지만, 아직 계산량와 통신량에서 문제점이 있다. 문제점을 해결하기 위해 round complexity에 대한 연구를 활발히 진행중이다. ZKIP과 관련한 이론적이고 실제적인 관점에서 의문점은 ZKIP의 round complexity의 최적의 bound는 얼마인지에 대한 문제이다. Goldreich는 BPP이외의 언어가 4 move 이상의 ZKIP를 구성한다고 했다. 그래서 기존 ZKIP 방식을 갖는 QR, CDLA 등은 round수가 제한되지 않았다.