[재미있는 수학] 완벽한 정보보호의 실마리 '영지식 증명'

내가 어떤 비밀번호나 정보를 알고 있다는 사실을 상대방에게 확실히 증명하되, 그 비밀의 내용은 ‘단 한 글자’도 알려주지 않는 것이죠. 수학에서는 이를 ‘영지식 증명(Zero-Knowledge Proof)’이라고 부릅니다. 영지식 증명은 이미 우리 주변에서 많이 쓰입니다.

Getty Images Bank

친구와 비밀 이야기를 해본 적 있죠? 비밀이란 참 묘한 구석이 있습니다. 내가 무언가 대단한 비밀을 알고 있다는 걸 자랑하고 싶으면서도, 정작 그 내용을 말해버리면 더 이상 비밀이 아니게 되어버리니까요.

그런데 수학의 세계에는 아주 신기한 방법이 하나 있습니다. 내가 어떤 비밀번호나 정보를 알고 있다는 사실을 상대방에게 확실히 증명하되, 그 비밀의 내용은 ‘단 한 글자’도 알려주지 않는 것이죠. 수학에서는 이를 ‘영지식 증명(Zero-Knowledge Proof)’이라고 부릅니다. 상대방에게 나에 대한 지식(Knowledge)을 영(Zero)인 상태로 유지하면서 증명한다는 뜻입니다.

이 추상적 개념을 이해하기 위해 특이한 구조의 건물을 상상해봅시다. 이 건물은 입구가 하나뿐인 둥근 복도 형태로 되어 있습니다. 안으로 들어가면 왼쪽 통로(A)와 오른쪽 통로(B)로 갈라지죠. 복도의 가장 깊숙한 안쪽에는 두 통로를 연결하는 ‘비밀의 문’이 하나 있습니다. 이 문은 비밀번호를 알아야만 열 수 있어 보통 사람들은 반대편 통로로 건너갈 수 없습니다.

이제 철수와 영희가 있다고 가정해볼게요. 영희는 이 문을 여는 비밀번호를 알고 있고, 철수에게 비밀번호 자체는 가르쳐주지 않으면서 자신이 그 번호를 알고 있다는 사실만 증명하고 싶습니다.

먼저 철수가 건물 밖에서 기다리는 동안, 영희는 어느 쪽 통로(A 혹은 B)로든 마음대로 들어갑니다. 건물 밖에서는 영희가 어느 방향을 선택했는지 전혀 알 수 없습니다. 이제 철수가 건물 입구로 들어와서 외칩니다. “영희야, 오른쪽(B)으로 나와줘!” 만약 영희가 비밀번호를 알고 있다면, 어느 쪽으로 들어갔든 안쪽의 비밀 문을 열고 지나가 철수가 요구한 쪽으로 당당히 걸어 나올 수 있습니다.

하지만 영희가 번호를 모른다면 어떨까요? 운 좋게 처음부터 오른쪽(B)으로 들어갔다면 나올 수 있겠지만, 왼쪽(A)으로 들어갔다면 문을 열지 못해 다시 들어갔던 길로 되돌아 나와야 합니다.

철수는 생각합니다. ‘한 번은 운 좋게 맞힌 걸 수도 있어.’ 그래서 이 과정을 여러 번 반복합니다. 두 번 연속으로 성공할 확률은 4분의 1이고, 열 번 연속으로 성공할 확률은 1024분의 1에 불과합니다. 만약 영희가 이 과정을 20번도 넘게 한 번도 틀리지 않고 성공한다면, 철수는 영희가 비밀번호를 확실히 알고 있다고 믿게 됩니다. 하지만 중요한 건 이 실험이 끝날 때까지 철수는 비밀번호가 무엇인지 전혀 알지 못한다는 점입니다.

디지털 세상에서 영지식 증명은 이 건물 이야기보다 훨씬 복잡한 수학적 구조를 가집니다. 주로 ‘한쪽 방향으로는 계산하기 쉽지만, 반대 방향으로 풀기는 불가능에 가까운’ 함수들을 이용합니다.

예를 들어, 두 소수 p=10,427과 q=13,109를 곱해 n=136,687,543을 만드는 과정은 금방 해낼 수 있습니다. 하지만 누군가에게 결괏값인 136,687,543만 알려주고 원래 어떤 두 소수를 곱했는지 찾아내라고 한다면, 수천 개의 숫자를 일일이 나눠보며 꽤나 긴 시간을 씨름해야 합니다. 여러분도 직접 해보면 알 수 있듯 생각만 해도 아찔한 일입니다.

실제 암호 체계에서는 수백 자리의 소수를 사용하기 때문에 이 ‘거꾸로 풀기’의 난이도는 현대의 슈퍼컴퓨터로도 수백 년이 걸릴 만큼 압도적으로 높아집니다. 영지식 증명은 바로 이 성질을 활용합니다. ‘나는 이 큰 수를 만든 두 소수를 알고 있다’는 사실을 증명하지만, 그 소수가 무엇인지는 끝까지 알려주지 않는 것이죠.

이 수학적 기술이 왜 우리에게 그토록 중요할까요? 뉴스를 통해 대형 정보기술(IT) 기업에서 수천만 명의 개인정보가 유출되었다는 소식을 들어본 적 있을 겁니다. 과거의 여러 유출 사건은 모두 서비스 제공자의 서버에 우리의 소중한 비밀번호나 그와 비슷한 정보가 직접 저장돼 있었다는 점이 문제였습니다.

아무리 튼튼한 금고(서버 보안)를 만들어도 도둑(해커)이 금고를 통째로 털어가면 그 안의 보물(개인정보)은 속수무책으로 당할 수밖에 없습니다. 하지만 영지식 증명을 사용하면 패러다임이 완전히 바뀝니다. 여러분은 서버에 비밀번호를 보내지 않습니다. 그 대신 “나는 이 계정의 주인임을 증명하는 수학적 답을 알고 있다”는 사실만 보여줍니다. 서버에는 비밀번호가 저장되어 있지 않으니 설령 서버가 해킹당하더라도 해커가 훔쳐갈 ‘비밀번호’ 자체가 존재하지 않는 셈이죠.

영지식 증명은 이미 우리 주변에서 많이 쓰입니다. 암호화폐 거래에서 금액을 숨긴 채 거래의 유효성만 증명하거나, 온라인 신원 인증에서 개인정보를 넘기지 않고도 ‘나는 성인입니다’를 증명하는 방식이 대표적입니다.

이정현 푸른숲발도르프학교 교사

누군가를 신뢰하기 위해 반드시 비밀을 공유할 필요는 없습니다. 모든 것을 파헤치지 않고도 그가 진실을 말하고 있다는 것을 논리적으로 확신할 수 있는 길이 있습니다. 수학은 차가운 숫자의 나열 같지만, 때로는 인간의 프라이버시를 존중하면서도 서로를 신뢰할 수 있게 만드는 따뜻한 도구가 되기도 합니다.