Zero-knowledge proof(0KP)

프로젝트 중간 발표를 하던 중, 주용수 교수님께서 'Zero-knowledge proof'에 대해 들어보았는지 여쭤보셨다.

한 번도 들어보지 못했던 개념이라, 어떤 개념이고, 우리 프로젝트에 어떻게 적용할 수 있을지 정리해본다.

0KP란?

해당 개념이 처음 등장한 1985년의 "THE KNOWLEDGE COMPLEXITY OF INTERACTIVE PROOF SYSTEMS" 논문을 바탕으로 정리 하면,

For any interactive protocol (A, B) to be zero-knowledge for a language L, whether or not (A, B) is a proof system for L.

상호작용 프로토콜 (A, B)가 zero-knowledge하다는 것은, prover가 L에 대한 증명을 하기 위해 필요한 정보를 최소화하면서도 verifier가 L에 대한 증명이 유효하다는 것을 검증할 수 있다는 것을 의미한다.

이를 간단히 하면, 0KP란, prover가 제공하는 정보를 최소화하면서, verifier가 해당 검증이 유효하다는 것을 쉽게 확인할 수 있으므로 효율적이고 보안에도 우수한 시스템이라는 뜻이다.

또한, 0KP는 NP 기반의 언어이기 때문에, 유효성 검증이 다항시간 내에 가능해야 한다.

어떻게 동작하는 걸까?

어떠한 context를 제공하지 않으면서 증명이 가능하기위해, zero-knowledge protocol은 input으로 어떤 데이터를 받고, true 혹은 false를 반환하는 알고리즘을 사용한다.

또한, zero-knowledge protocol 다음의 기준을 만족해야 한다.

• Completeness: 입력 데이터가 유효하다면, 결과는 무조건 true여야 한다.
• Soundness: 입력 데이터가 유효하지 않다면, 어떠한 방식으로든 zero-knowledge protocol을 속여 true를 반환할 수 없다.
• Zero-knowledge: verifier는 prover에 대한 어떠한 다른 정보 없이 증명이 가능해야 한다.

가령, 대한민국이라는 국가의 시민이라는 것을 증명할 때, 이를 뒷받침할 '증거'(ex. 여권, 운전면허증)를 제출할 필요가 없는 것이다.

어디에 적용할 수 있을까?

0KP는 보안 프로토콜, 암호화, 인증 등에 사용될 수 있는데, 해당 논문에 아래와 같이 기술 돼 있다.

Although we find the idea of a zero-knowledge interactive proof system fascination in iteself, the main motivation for it and the main applications of it are in the area of cryptographic protocols.

또 다른 예로, 사용자의 개인정보에 대한 보안을 향상시킬 때 사용될 수 있다.