영지식 상호 증명

영지식 상호 증명 또는 ZKIP(Zero-Knowledge Interactive Proof)은 비밀의 내용은 밝히지 않으면서 그 비밀을 알고 있다는 사실을 증명하는 방법을 말한다. 증명자와 검증자 간 일반 난수와 비밀 정보로부터 연산한 결과를 주고받으며 확률적으로 납득시키며, 횟수가 늘어날수록 확신도는 높아지게 된다. 영지식 대화형 증명이라고도 한다.

배경

정보화 사회가 발달하면서 컴퓨터 네트워크를 통해서 다양한 정보 교환이 이루어지면서 데이터 보호 대책이 요구되기 시작했다. 즉 네트워크 정보 교환이 활발히 이루어지는 현재 상황에서 다양한 데이터 트랜잭션에 대처할 수 있는 응용 프로토콜의 연구 필요성이 높아지게 된 것이다. 응용 프토토콜은 범위가 매우 넓고 개인정보 보호의 역할과 중요성이 높다. 특히 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의 개념이 나오게 된 것이다.

구성

영지식 증명방식은 일반적으로 상호 증명방식의 형태를 취한다. 상호 증명방식은 증명자와 검증자가 일련의 질문 및 답으로 구성된 대화를 통해 증명을 하는 방식이다. 이러한 의미에서 영지식 증명방식을 영지식 상호 증명방식이라 일컫는다. 영지식 증명방식은 NP 증명방식을 일반화시킨 방식으로 암호화 프로토콜의 안정성 문제를 해결하기 위해 제시된 모델이므로 NP 증명방식, 상호 증명방식, 영지식 상호 증명방식 순으로 설명이 가능하다.

NP 증명방식

NP 증명방식은 상호 통신이 가능한 무한한 계산 능력을 가진 증명자(Deterministic turing machine Prover)와 다항식 계산 능력을 갖는 검증자(Deterministic turing machine Verifier)로 구성되며 증명자와 검증자는 NP문제인 X를 공통 정보로 입력받아 들인다. 이때 무한한 계산 능력을 갖고 있는 증명자는 문제 X에 대한 해답 S를 구하여 검증자 V에게 전송하면, 다항식 계산 능력을 가진 검증자 V는 해답 S가 문제 X의 해인지 판단하는 방식을 NP 증명방식이라고 한다. NP 증명방식의 예시로는 패스워드를 이용한 단순한 사용자 인증을 들 수 있다. 컴퓨터 시스템의 사용자인 증명자가 컴퓨터 시스템인 검증자에게 패스워드를 전송하면 검증자인 컴퓨터 시스템은 이 패스워드가 사용자인 검증자의 패스워드인지 검증하여 인증하는 방식이다. 위와 같은 방식은 증명자가 검증자에게 자신의 정보를 전송하는 일방향 방식이며 또한 전송하는 정보인 해답 S는 중요한 정보이고 암호학 입장에서 보면 패스워드와 같은 해답 S가 증명방식을 통해서 공개되는 것이기 때문에 적용 분야가 극히 한정될 수 밖에 없다.

상호 증명방식

상호 증명방식은 일방향 적인 NP 증명방식과 달리 검증자도 자신의 정보를 증명자에게 전송하는 양방향 방식이다. 상호 증명방식은 상호 통신이 가능한 무한 계산 능력을 가진 증명자(Interactive turing machine Prover)와 다항식 계산 능력을 가진 검증자(Interactive turing machine Verifier)로 구성된다. 여기에 첫 번째 조건으로 NP문제인 X를 공통 입력 정보로 받아들이며, S가 문제 X의 해답일 경우 증명자는 검증자에게 일정 확률 이상으로 해답이 S라는 점을 증명해야하는 완전성 조건과 두 번째로 위와 같이 NP 문제인 X를 공통 입력 정보로 받아들이며, x가 문제 X의 해가 아닐 경우, 임의의 증명자는 검증자에게 문제 X의 해답이 S라는 것을 증명할 수 있는 확률이 일정 확률 이하여야 하는 건전성 조건을 모두 만족해야 상호 증명방식이라고 할 수 있다. 결국 조건 1인 완전성의 경우 문제 X의 해답이 S일 경우, 검증자는 압도적인 확률로 수락하여야 한다는 것을 의미하며, 조건 2인 건전성의 경우 문제 X의 해답이 S가 아닐 경우, 검증자가 수락할 확률이 무시할 정도로 적은 확률이어야 한다는 것이다.

영지식 상호 증명방식

영지식 상호 증명방식은 앞서 언급한 상호 증명방식에 추가로 어떤 임의의 검증자에게 증명자가 계산 능력을 갖는다는 것 이외의 증명자의 관련 정보 및 문제에 대한 해답을 노출시키지 않는다는 조건인 영지식성 조건이 추가된 것을 말한다.

영지식 비상호 증명방식

영지식 상호 증명방식의 경우 증명자와 검증자가 항상 온라인(on-line) 상태여야 한다는 전제가 필수이다. 이러한 전제는 시스템 전체적으로 보았을 때 매우 비효율적인 구조였기에 1986년 fiat, Shamir는 결국 영지식 비상호 증명방식인 ZKNIP(Zero Knowledge Non-Interactive Proof)를 제시하였고 이 방식은 증명자와 검증자의 온라인 여부와 관계없이 증명을 할 수 있도록 고안이 되었다. 영지식 비상호 증명방식은 결국 증명자와 검증자의 메시지 교환이 최소화 되어야 한다는 것을 의미하며 증명자가 증명에 필요한 메시지를 보내고 난 후 연결이 끊어진다고 하더라도 결국에는 그 메시지가 보증되어야 하는 것이 비상호 증명방식의 핵심이다. 이러한 장점이 있지만 비상호 증명방식의 경우 연산의 횟수가 기하급수적으로 증가하기 때문에 증명에 대한 검증을 완료하는데 상당한 시간이 걸릴 수 있다는 단점 역시 존재하게 된다. 이를 해결하기 위해 비상호 증명방식에서 발생하는 증명자의 증거 데이터의 사이즈를 줄여 빠른 검증을 수행할 수 있도록 하여 비상호 증명방식의 실용성을 극대화 한 것이 현재 지캐시(Zcash)의 기반이 되는 핵심 기술인 zk-SNARKs이다.

영지식 증명방식

상호 증명방식에서 상호 통신이 가능한 무한 계산 능력을 갖는 확률 선회 기계 P와 다항식 계산 능력을 갖는 확률 선회 기계 V가 다음의 조건을 만족할 때, 영지식 증명방식이라고 한다. 조건) 임의의 다항식 계산 능력을 갖고 있는 검증자 V에 대하여, 다항식 계산 능력을 갖는 확률 선회 기계 Mv*가 존재하고 정보 X가 입력된 Mv*와 정보 X가 입력된 P와 V는 구별되지 않아야 한다.

영지식 증명방식은 3가지의 조건을 모두 만족해야 한다.

① 어떤 조건이 참이라면 신뢰 할 수 있는 검증자(honest verifier)는 신뢰할 수 있는 증명자(honest prover)에 의해 이 사실을 납득할 수 있어야 한다는 완전성(Completeness).

② 어떤 조건이 거짓이면 신뢰할 수 없는 증명자(dishonest prover)는 거짓말을 통해 검증자에 조건이 참임을 절대 납득시킬 수 없다는 건전성(Soundnes).

③ 어떤 조건이 참일 때, 검증자는 이 조건이 참이라는 사실 이외의 아무 정보를 알 수 없다는 영지식성(Zero-Knowledge).

여러 번의 반복을 통해 검증자는 증명자가 비밀번호를 알고 있다는 사실을 납득했지만 비밀번호가 무엇인지는 알지 못한다는 사실은 영지식성을 따르게 된다.

응용 방식

영지식 상호 증명방식은 개인 식별방식, 키 분배방식, 디지털 서명방식 등 세가지 방식으로 응용된다.

① 개인 식별(Identification) 문제는 암호학의 여러 분야에서 발생하는 매우 중요한 문제 중 하나로 손꼽힌다. 개인 식별은 가입자 A가 가입자 B와 협조하여 A는 B에게 자신이 A인 사실을 증명할 수 있지만, 제 3자인 C가 A로 위장하여 B에게 자신이 A라고 속일 수 없는 사용자 인증(Entity Authentication) 기능에 B역시 또 다른 제 3자 D에게 자신이 A라고 증명할 수 없다는 조건이 추가된 기능이다. 개인 식별 방식이 유용하고 안전하기 위해서는 3가지 조건을 만족해야 한다. 첫 번째로 합법적인 검증자는 합법적인 증명자의 사용자 증명을 높은 확률로 받아들여야 하며, 두 번째로 합법적인 검증자는 불법적인 증명자의 사용자 증명을 낮은 확률로 받아들여야 한다. 마지막으로 불법적인 검증자는 합법적인 증명자와 다항식 횟수 만큼 상호 통신하더라도 어떤 사람에게도 자신이 합법적인 증명자라고 흉내낼 수 있는 어떠한 정보라도 획득할 수 없어야 한다. 효율적인 개인 식별은 영지식 상호 증명 개념과 연관성이 높다. 또한 개인 식별 방식을 포함한 ID 정보와 영지식 상호 증명 방식을 이용한 개인 식별 프로토콜은 많은 변형이 가능하다.

② 키 분배방식은 증명자와 검증자 사이에 무작위의 정보가 전송되며, 증명자의 랜덤성(Randomness)은 영지식 조건을 만족시키기 위해 사용된다. 랜덤 정보는 아직까지는 상호 증명방식에서만 사용되고 있지만, 효과적으로 사용한다면 더 많은 정보 통신 분야에서 사용될 것으로 예상되고 있다.

③ 디지털 서명 방식은 개인 식별 방식과 동일한 준비 과정을 거치며, 증명자가 메시지에 대하여 서명을 만들어 검증자에게 전송해야 하므로 개인 색별 방식처럼 상호 방식은 사용할 수 없다. 그래서 증명자는 해쉬함수를 이용하여 서명할 메시지와 자신이 선택한 랜덤수에 의존하는 2진 벡터를 생성하여 이용한다. 가입자 A와 B는 각자 서로의 서명이 정당한 지 여부를 항상 확인할 수 있어 안전성이 높다.

성과

현대사회가 정보사회로 변화하는 과정에서 고도의 통신처리 및 정보처리 기술을 필요로 하고 있다. 특히 고도의 부가가치가 있는 각종 서비스를 제공하기 위해 안전하고 효율적인 암호화 프로토콜을 필요로 하고 있다. 이 때 영지식 상호 증명방식은 암호화 프로토콜의 안전성을 제시하는 모델로서 개인 식별, 키 분배, 전자 서명 등 각종 분야에서 활용되었다. 영지식 상호 증명을 이용한 암호화 프로토콜은 영지식 상호 증명방식을 구성하는데 소요되는 통신 횟수와 통신량이 많은 단점이 있긴 하지만, 이를 극복하기 위한 연구가 활발히 진행되고 있다. 뿐만 아니라 영지식 상호 증명을 이용한 응용 분야도 연구가 진행 중에 있다. 즉, 영지식 상호 증명을 이용하면, 안전한 암호화 프로토콜의 구성이 가능하게 되므로, 그 효율성을 극대화하려는 노력이다. 국내 정보 보호와 관련된 연구에서도 영지식 상호 증명방식이 활발히 응용되어 정보화 사회에서 요구되는 전자송금 및 전자우편, 전자거래, 홈쇼핑, 홈뱅킹, 전자현금 등의 서비스를 구현하는데 필요한 기반을 다졌다.

참고자료

• k1ng-first, 〈(블록체인, 정보) 그림으로 이해하는 영지식증명(Zero Knowledge Proof)!!〉, 《스팀잇》
• Argon Group, 〈On Zero-Knowledge Proofs in Blockchains〉, 《미디움》, 2018-03-23
• 영 지식 상호 증명, 〈영 지식 상호 증명〉, 《네이버 지식백과》
• 김승주, 박성준, 이임영, 원동호, 〈암호 알고리즘과 암호 프로토콜〉, 《학술논문》
• 권창영, 이인숙, 원동상, 〈영지식 대화형 증명 방식 및 응용 프로토콜〉, 《학술논문》, 1993-02

이 영지식 상호 증명 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반