영지식 증명(Zero-Knowledge Proof, ZKP)은 2012년 튜링상 수상자인 샤피 골드와서와 2012년 튜링상 수상자이자 알고랜드 설립자인 실비오 미칼리, 그리고 찰스 랙코프(Charles Rackoff)가 1986년에 전기 전자 기술자 협회 FOCS 학술대회(IEEE Symposium on Foundations of Computer Science)에서 처음 제시한 암호 이론으로, 다양한 개인정보보호 문제를 해결하는 데 아주 요긴하게 활용될 수 있다.

블록체인과 가상자산 분야도 예외는 아니어서, 가상자산에서 영지식 증명이 처음 사용된 것은 2013년 존스홉킨스 대학 연구진이 개발한 제로코인(ZeroCoin)이다. 이후 제로코인은 2014년 제로캐쉬(Zero Cash)로 이름이 바뀌었으며, 2016년 들어 지캐시(Zcash)라는 이름으로 다시 한번 변경된다. 이후 영지식 증명 이론은 블록체인 응용분야 전반으로 확대 적용되며 그 영향력을 과시하게 된다.

이러한 인기를 말해주듯 이미 인터넷상에는 영지식 증명을 소개하는 많은 글들이 있는데, 이들 대부분은 1989년에 발표된 “자녀들에게 영지식 프로토콜을 설명하는 방법(How to Explain Zero-Knowledge Protocols to Your Children)”이란 논문에서의 알리바바와 40인의 도둑 예제를 인용한다. 그런데 문제는 인터넷상의 글들이 논문에서 말하고자 하는 핵심 철학을 제대로 전달하지 못하고 있다는 것이다.

영지식증명은 현재 매사추세츠 공과대학교(MIT) 교수로 재직 중인 샤피 골드와서 박사가 1984년에 본인의 학위 논문에서 정립한 ‘어의적 안전성(Semantic Security)’ 개념을 보다 더 일반화한 것이다. 우리가 누구의 설명을 듣거나 영화 등을 봤을 때 그것이 이미 알고 있던 내용이라면 흔히 “에이! 시시해. 별거 없네. 그건 나도 얼마든지 (따라)할 수 있겠다.”라고 말하곤 한다.

영지식 증명 이론은 바로 이를 수학적으로 모델링한 것으로서, ‘특정인의 행동을 누구나 쉽게 모방할 수 있다면 그 사람의 행동거지로부터 유출되는 비밀정보는 거의 없는 것으로 볼 수 있다’는 개념이다. 영지식 증명에서는 이를 ‘시뮬레이션 가능성(Simulatability)’이라고 한다.

다시 알리바바와 40인의 도둑 예제로 돌아가 보자. 그림 1에 통로 중간이 철문으로 막힌 동굴이 있다. 알리바바(P)는 이 문을 여는 마법의 주문 “열려라 참깨”를 본인이 알고 있다는 사실을 기자(V)에게 증명하고 싶어 한다. 단, 이때 마법의 주문을 기자에게 노출시키는 것은 싫다. 어떻게 하면 될까?


그림 1 알리바바의 마법 동굴. 출처=Nick Bolduc
기자와 함께 동굴 입구에 도착한 알리바바는 먼저 동굴에 입장한다. 기자는 잠시 동안 밖에서 대기하는데, 이때 기자는 동굴 내부를 볼 수 없다. 동굴에 들어간 알리바바는 A, B 두 갈래 길 중 하나를 택한 후 잠긴 문까지 걸어 들어간다. 이어 동굴에 입장한 기자는 알리바바에게 A, B 두 경로 중 하나로 나오라고 소리친다. 첫 실험에서 기자가 요청한 방향으로 나온 알리바바가 실제로 마법의 주문을 알고 있을 확률은 50%에 불과하다.

그러나 이러한 실험이 반복될 때마다 알리바바가 정말로 주문을 알고 있을 확률은 계속해서 증가하게 된다. 예를 들어 실험을 100회 반복했을 때 마법의 주문을 모르는 사람이 이를 통과할 확률은 2의100승 분의 1(약 0.0000000000000000000000000079%)에 불과하다.

또다른 방법도 있다. 알리바바는 기자와 함께 두 갈래 길이 나 있는 곳까지 걸어 들어간다. 기자가 갈래 길 입구에 대기하고 있으면, 알리바바는 A, B 중 하나를 택해 들어가고, 마법의 주문을 이용해 잠긴 문을 통과한 후, 반대편으로 나온다.

위 두 가지 방법 모두 알리바바는 기자에게 “열려라 참깨”라는 주문을 노출시키지 않은 채 본인이 마법 주문을 알고 있다는 사실만을 입증할 수 있다. 그러나 처음의 1안은 영지식 증명인 반면, 2안은 영지식 증명이 아니다. 왜냐하면 1안은 시뮬레이션이 용이한 반면, 2안은 시뮬레이션이 쉽지 않기 때문이다. 마법의 주문을 모르는 사람이 어떻게 알리바바의 행동을 시뮬레이션, 즉 모방할 수 있을까?

먼저 알리바바를 흉내 내려는 알리순이는 기자와 함께 동굴 입구로 간다. 기자는 밖에서 대기하고, 알리순이는 먼저 동굴 안으로 들어간다. 동굴에 들어간 알리순이는 기자가 어느 쪽 갈래 길로 나오라고 할지를 미리 예측한 후 그리로 들어가 기자를 기다린다.

이제 동굴에 입장한 기자는 알리순이에게 A, B 중 하나로 나오라고 주문하고, 예측이 맞았을 경우 알리순이는 마법의 주문을 모르고도 기자가 주문한 경로로 나올 수 있다. 만일 알리바바가 100회의 실험을 했다면, 알리순이의 경우 200회의 실험을 진행해 이를 영상으로 찍고 이중 예측이 틀린 부분들만을 편집해내면 알리바바가 한 것과 동일한 화면을 만들어 낼 수 있다. 이를 시뮬레이션에 성공했다고 한다.

2안은 어떨까? 일단 알리순이는 기자와 함께 두 갈래 길이 나 있는 곳까지 걸어 들어간다. 기자가 갈래 길 입구에 대기하고 있으면, 알리순이는 A, B 중 하나를 택해서 들어간 후 마 법 주문을 이용해 잠긴 문을 통과해야 하는데, 이때 이 마법의 주문을 찍어서 맞추려면 무수히 많은 주문들을 반복적으로 시도해봐야 한다. 즉 쉽게(전문 용어로는 다항식 시간(Polynomial Time) 안에) 알리바바의 행동을 흉내 내기가 어려운 것이다.

영지식 증명은 작게는 사용자 신원 확인에서부터 크게는 블록체인, 가상자산, 전자투표에 이르기까지 다양한 분야에서의 개인정보보호문제를 해결하는 데 있어 중요한 솔루션임에는 분명하다. 그러나 위에서 살펴본 바와 같이 영지식 증명은 매우 까다로운 기술이다.

더욱이 영지식 증명은 매우 엄격한 수학적 증명을 요구하기 때문에 시스템이 복잡해질 수 있으며, 시스템 설정이 조금만 바뀌어도 영지식 증명이 유지되지 못하는 경우 또한 허다하다. 개인 정보보호에 있어 전가의 보도(傳家寶刀)는 없으며, 올바른 이해 없이 맹목적으로 사용하는 기술은 오히려 독이 될 수도 있음을 명심해야 할 것이다.

 

김승주 교수는 2011년부터 고려대학교 정보보호대학원 교수로 재직했으며, 올해부터는 새롭게 사이버국방학과의 학과장을 맡고 있다. 교수 재직 전에는 한국인터넷진흥원(KISA)에서 암호기술팀장과 IT보안평가팀장으로 근무한 암호 보안 전문가다.

#NFT#칼럼#김승주

출처 : 코인데스크 코리아 (http://www.coindeskkorea.com/news/articleView.html?idxno=79339)