영지식 대화형 증명시스템

영지식대화형증명시스템은 다음의 4가지 개념이 조화를 이룬 시스템이다.

1)영(Zero), 2)지식(Knowledge), 3)대화형(Interactive), 4)증명시스템(Proof system)

 

먼저 지식에 대해서 살펴보자. 지식이란 무엇인가? 이에 대해서 적절한 정의를 내릴 수 있을까? 이런 질문을 던지는 순간,(원하든 원하지 않든) 우리는 철학에 한 걸음 발을 내딛게 된다. 책을 한 권 읽었다고 해보자. 거기에서 얻은 지식이 얼마나 되는지 정량화하는 것이 가능할까? 인간은 배울 때 분야를 넘나드는 경우가 많다. 인간의 지식은 유추해석이 적용된다. 톨스토이 소설을 읽었다고 해보자. 거기에는 주인공이 나오고 사랑, 감정, 이야기, 사건, 싸움, 패배, 열정 등 모든 것들이 나온다. 이 자체만 해도 양이 상당할텐데, 이런 책을 읽으면서 사람의 지식은 유추해석을 적용한다. 그렇다면, 톨스토이 소설을 한 권 읽은 후에 거기에서 얻은 지식을 정량화하는 것이 가능할까? 얼마나 배웠는지 나열할 수 있을까? 여기서 말하고자 하는 요지는 A라는 대상을 통해서 얻은 지식을 정량화하는 것이 매우 어렵다는 것이다.

 

암호학과는 크게 관련이 없지만, 지식에 대해서 말했던 철학자들의 담론을 짧게 조망해보자. (지식이 얼마나 정의하기 힘든지 보여주기 위함이다.)

프랜시스 베이컨 : 과학주의를 제창하고 경험론의 문을 활짝 열었다. 그는 네 가지 우상을 말했고 그 우상을 적절히 피해서 경험주의와 귀납적 방법을 사용할 것을 권고하였다. 귀납의 방법에 문제가 있을 수 있다는 점은 인정하였으나, 연역의 방법만으로는 올바른 지식이 얻어질 수 없다고 생각하였다.

존 로크 : 그는 인간이 백지와 같은 상태로 태어난다고 보았다. 백지와 같이 태어난 인간은 경험에 의해서 자신들만의 인식을 점차 세워나가는데, 그 인식이 객관적 실재와 일치할 수 있는 요인은 대상의 1차 성질에 의해 보장된다고 생각하였다. 그는 데카르트가 경험 요소를 배제하고자 했던 것에 의문을 던졌고 인식과 지식이 경험에 근거해야 한다고 믿었다.

데이비드 흄 : 기존의 경험주의에 굉장히 날카로운 비판을 들이대었다. 경험에 의해서 인과관계를 파악할 수 있다고 하더라도, 그것이 그렇게 쉽게 확정될 수는 없다고 생각하였다.

데카르트 : 경험을 배제하고 이성에 근거하여 학문과 지식의 기초를 닦으려 하였다. (Cogito ergo sum)

이외에도 많은 철학자들이 있지만, 여기까지 하는 것이 좋을 듯하다. 이렇게 철학자들을 나열한 이유는 이 철학자들이 지식에 대한 생각이 각기 달랐기 때문이다. 철학자들뿐만 아니라 각 분야의 지식인들과 학자들은 지식에 대해서 다른 생각을 하고 있고 아직 모두가 인정할만한 합의에 이르지 못했다.

 

A를 통해서 얻은 지식을 수량화하는 것도 어렵고 지식이 무엇인지에 대해서 만족할만한 합의에 이르는 것 역시 어렵지만, 영지식 = 1)영 + 2)지식이 무엇인지 정의를 내리는 것은 간단하다. 이것은 거리를 재는 것에 비유해서 설명할 수 있다. 거리를 잴 때 각기 방법은 다를 수 있다.

m, feet, inch, yard, mile....etc

그러나

0 m = 0 feet = 0 inch = 0 yard = 0 mile

방법이 다르더라도, 0길이에 있어서는 모두 같다. 이와 마찬가지로, 지식을 어떻게 정의하고 정량화할 수 있는지에 대해서는 각기 다르더라도, 영지식에 있어서는 모두 같다. (확률공간과 연동해서 생각한다면, 영지식은 확률공간에 영향을 미치지 않는 것을 의미한다)

 

이제 대화형 증명시스템에 대하여 설명해보자.

대화형 증명시스템은 기존의 증명시스템을 확장한 개념이다.

증명시스템이란 증명자가 어떤 사실을 검증자에게 증명하는 시스템으로 다음의 2가지 특징이 있다.

(1) 일방향

(2) 증명이 이루어지면 100% 사실

 

기존의 증명시스템은 바로 이러한 방식을 따랐다. 증명자는 검증자에게 해당 명제를 증명하는 메시지를 보냈고 검증자는 그가 맞는지/틀린지 단박에 파악할 수 있었다. 굳이 비유하자면, 학생들이 보는 시험과 유사하다. (검증은 채점이랑 비슷하다)

대화형 증명시스템이란 위의 2가지 특성을 다음과 같이 확장한다는 것이다.

(1) 일방향에서 대화형으로

(2) 증명이 이루어지면 100%가 아닌 믿을만한 충분한 확률( 1에 가까운 확률 )로

사실이라는 것이다.

 

이 의미는 충분히 작은 확률이지만 옳지 않은 사실이 증명될 수도 있다는 것이다. 그러나 이 확률이 충분히 작기 때문에 무시해도 상관 없다는 것이다.

대화형 증명 시스템을 정의하기 위해서는 먼저 간단히 다음의 2가지 개념을 생각한다.

(1) 완전성 ( completeness ) 조건

진실이라면 충분한 확률로 증명 가능

(2) 건전성 ( soundness ) 조건

거짓이라면 아주 적은 확률로 증명 가능

 

이러한 대화형 증명시스템의 이해를 돕기 위해서 예시를 하나만 들어보자.(재미를 더하고 이해를 증진시키기 위한 예시일 뿐이다. 정확히 말하면 이 예시는 건전성 조건을 충족한다고 보기 어렵다.)

영화 ‘케이펙스’에 보면 지구에서 1천 광년 떨어져있는 케이펙스라는 행성에서 왔다고 주장하는 ‘프롬’이 나온다. 정신과 전문의 ‘마크’는 그의 주장을 시험하기 위해서 그에게 여러 가지 질문을 던진다.

“왜 지구에 왔는가?”

“케이펙스에서의 가족형태는 어떠한가?”

“케이펙스의 행성궤도는 어떠한가?”

이것을 암호학적인 용어로 표현하면 다음과 같다. ‘검증자 마크’는 ‘증명자 프롬’에게 케이펙스에서 왔다는 그의 주장을 검증하기 위한 질문을 던진다. 그리고 ‘프롬’도 ‘검증자 마크’에게 답을 한다. 대화형증명시스템은 바로 이러한 방식으로 검증한다. 대화형으로 서로 소통하면서 명제의 옳고 그름이 확률적으로 검증된다.

<최고의 수학자가 사랑한 문제들>을 보면 지도색을 활용한 영지식 내용이 나온다.(자세한 내용은 책 참고) 엄밀성 면에서는 조금 떨어지기는 하지만, 나름 재미있는 내용이라고 생각한다. 어떤 지도 색깔을 알고 있을 때 그 색을 곧바로 보내지 않는 이유는 영지식 특성을 만족시키기 위해서이다. 곧바로 색을 보내게 되면 검증자 V에게 답까지 전부 알려주게 된다. 그러나 약간 변환해서 보내면, 증명자는 해당 답을 알고 있다는 사실만을 증명하면서 그 내용은 알려주지 않을 수 있다. (원래, 이보다 훨씬 엄밀한 예시를 제시할 수 있었지만, 출처 문제가 있어서 뺐다.)

 

이제 영지식과 대화형 증명시스템에 대해서 기본적으로 살펴보았으니 이것을 하나의 문장으로 간략화해보자.

영지식대화형증명시스템이란, 위에서 살펴본대로 완전성과 건전성을 모두 만족하는 일방향이 아닌 쌍방향 증명시스템에서 상대방에게 지식을 전달하지 않으면서(영지식) 증명자가 검증자에게 자신이 알고있음을 증명하는 검증방식이다.