당신이 유용한 지식을 가지고 있다고 상상해보십시오. 아마도 비밀 레시피나 암호의 열쇠일 것입니다. 당신은 그것에 대해 아무 것도 밝히지 않고 당신이 그 지식을 가지고 있다는 것을 친구에게 증명할 수 있습니까? 컴퓨터 과학자들은 30년 전에 영지식 증명(zero-knowledge proof)이라고 불리는 것을 사용하면 가능하다는 것을 증명했습니다.
이 아이디어를 이해하는 간단한 방법으로 경로에 대한 세부 정보를 공개하지 않고 미로를 통과하는 방법을 알고 있다는 것을 친구에게 보여주고 싶다고 가정해 봅시다. 친구가 보는 것이 금지되어 있는 동안 제한 시간 내에 미로를 횡단할 수 있습니다. (시간 제한이 필요한 이유는 시간이 충분하면 누구나 시행착오를 거쳐 결국 길을 찾을 수 있기 때문입니다.) 친구는 당신이 할 수 있다는 것을 알지만 방법을 모릅니다.
영지식 증명은 비밀 정보를 다루는 암호 작성자에게 도움이 될 뿐만 아니라 다양한 문제의 난이도를 분류하는 계산 복잡성을 연구하는 연구자에게도 유용합니다. "현대 암호화의 많은 부분은 복잡성 가정에 의존합니다. 특정 문제는 해결하기 어렵기 때문에 항상 두 세계 사이에 약간의 연결이 있다는 가정에 기반합니다."라고 말했습니다. 클로드 크레포, McGill 대학의 컴퓨터 과학자. "그러나 [이러한] 증거는 연결의 전체 세계를 만들었습니다."
영지식 증명은 대화식 증명으로 알려진 범주에 속하므로 전자가 어떻게 작동하는지 배우려면 후자를 이해하는 것이 도움이 됩니다. 첫 번째 기술 된 컴퓨터 과학자들의 1985년 논문에서 샤피 골드와서, 실비오 미칼리(Silvio Micali) 및 찰스 라코프(Charles Rackoff)에 따르면 대화형 증명은 질문처럼 작동합니다. 일련의 메시지를 통해 한 당사자(증명자)는 다른 당사자(검증자)에게 주어진 진술이 참임을 확신시키려고 합니다. 대화형 증명은 두 가지 속성을 충족해야 합니다. 첫째, 진실한 진술은 항상 결국 정직한 검증자를 설득할 것입니다. 둘째, 주어진 진술이 거짓이라면 어떤 증명자도(특정 지식을 가장하는 척하는 사람이라도) 무시할 수 있을 정도로 작은 확률을 제외하고는 검증자를 설득할 수 없습니다.
대화형 증명은 본질적으로 확률적입니다. 증명자는 운에 의해 한두 가지 질문에 올바르게 답할 수 있으므로 증명자가 실제로 그 진술이 참임을 알고 있다는 확신을 가지려면 증명자가 모두 맞아야 하는 충분한 수의 도전이 필요합니다.
이러한 상호 작용에 대한 아이디어는 Micali와 Goldwasser(당시 버클리 캘리포니아 대학교 대학원생)가 네트워크를 통해 포커를 플레이하는 과정에서 어리둥절했을 때 나왔습니다. 모든 플레이어가 가상 덱에서 카드를 받았을 때 결과가 무작위인지 어떻게 확인할 수 있습니까? 대화형 증명이 그 길을 이끌 수 있습니다. 그러면 플레이어가 모든 플레이어의 핸드를 공개하지 않고 전체 프로토콜(전체 규칙 세트)이 올바르게 준수되었는지 어떻게 확인할 수 있습니까?
이 목표를 달성하기 위해 Micali와 Goldwasser는 대화식 증명에 필요한 두 가지 속성에 세 번째 속성을 추가했습니다. 즉, 증명은 지식 자체에 대해서는 아무것도 나타내지 않고 진술의 진실성만 나타내야 합니다. Goldwaser는 "프로토콜을 통과한다는 개념이 있습니다. 결국 [포커 플레이어]는 자신이 알아야 하는 것 이상을 모른다고 생각합니다."라고 Goldwasser가 말했습니다.
고전적인 예를 생각해 봅시다. Alice는 Bob에게 특정 그래프가 G — 모서리(선)로 연결된 정점(점)의 고유한 모음 — "해밀턴 주기"가 있습니다. 즉, 그래프에는 모든 점을 정확히 한 번 방문하고 시작된 동일한 점에서 끝나는 경로가 있습니다. Alice는 단순히 Bob에게 이 작업을 수행하는 경로를 보여줌으로써 이 작업을 수행할 수 있지만 당연히 그도 경로를 알고 있을 것입니다.
다음은 Alice가 Bob에게 그런 경로가 있다는 것을 보여주지 않고 자신이 알고 있다는 것을 Bob에게 확신시킬 수 있는 방법입니다. 먼저 그녀는 새로운 그래프를 그리고, H, 그건 아닌 것 같다 G 그러나 결정적인 면에서 유사합니다. 동일한 수의 정점이 있고 동일한 방식으로 연결되어 있습니다. (만약에 G 실제로 해밀턴 주기가 있습니다. 이 유사성은 H 도 마찬가지입니다.) 그런 다음 모든 가장자리를 덮은 후 H 마스킹 테이프로 그녀는 잠그고 H 상자에 넣어 Bob에게 상자를 줍니다. 이것은 그가 그것을 직접 보는 것을 방지하지만 또한 그녀가 그것을 변경하는 것을 방지합니다. 그런 다음 Bob은 선택을 합니다. H 정말 비슷하다 G, 또는 그는 그녀에게 해밀턴 주기를 보여달라고 요청할 수 있습니다. H. Alice는 두 요청 모두 쉬워야 합니다. H 정말 비슷하다. G그리고 그녀는 정말로 그 길을 알고 있습니다.
물론 앨리스가 해밀턴 주기를 모른다고 해도 G, 그녀는 다음과 유사하지 않은 그래프를 그려서 Bob을 속일 수 있습니다. G, 또는 그녀가 경로를 모르는 그래프를 제출함으로써. 그러나 여러 라운드를 플레이한 후에 Alice가 매번 Bob을 속일 가능성은 점점 작아집니다. 그녀가 모든 것을 올바르게 이해한다면 결국 Bob은 Alice가 그래프에서 해밀턴 순환을 알고 있다고 확신하게 될 것입니다. G, 밥이 그것을 본 적이 없이.
그러한 증명을 처음 기술한 최초의 논문 이후, Micali와 두 명의 수학자(Oded Goldreich와 Avi Wigderson)는 광범위한 효과와 함께 예상치 못한 결과를 발견했습니다. 그것은 NP로 알려진 거의 동일한 난이도의 문제의 주요 범주와 관련이 있습니다. 이러한 문제는 해결하기 어렵지만 솔루션을 확인하는 것은 쉽습니다. 세 명의 연구원 발견, 진정으로 안전한 암호화라면 가능하다, 그러면 NP의 모든 문제에 대한 솔루션도 영지식 증명으로 증명될 수 있습니다. 이 연구는 연구자들이 ~을 생각하다 애초에 보안 암호화가 필요하지 않은 영지식 증명의 변종; 이를 다중 증명자 대화형 증명이라고 합니다.
그리고 1988년 미칼리 등 보여 증명자와 검증자가 짧은 랜덤 비트 문자열을 공유하는 경우 상호 작용이 필요하지 않습니다. 이것은 이론적으로 영지식 증명이 상호작용할 필요가 없다는 것을 의미하며, 이는 두 당사자 간의 지속적인 통신이 필요하지 않음을 의미합니다. 이것은 연구원들에게 훨씬 더 유용할 것이지만, 그러한 증명이 시작된 것은 21세기가 되어서야 이루어졌습니다.
"2000년대 후반에 우리는 영지식 증명을 구축하기 위한 효율적인 기술의 진화를 보기 시작했습니다."라고 말했습니다. 매튜 D. 그린, 존 홉킨스 대학의 암호학자. “'잠깐만요. 실제로 이것을 사용할 수 있는 방법이 있을지도 모른다'는 것을 깨달았습니다.'”
이제 증명자는 둘 다 온라인 상태가 아니더라도 단일 메시지를 검증자에게 보낼 수 있으며 연구원은 매우 복잡한 문제에 대해서도 신속하게 확인할 수 있는 매우 짧은 증명을 만들 수 있습니다. 이는 암호화폐 거래 후 블록체인을 빠르게 검증하면서도 거래 내역을 숨길 수 있는 등 여러 가지 실용적인 용도로 이어졌습니다. 그리고 2016년에 물리학자 그룹 보여 영지식 증명이 핵 군축에 어떻게 도움이 되는지: 핵탄두 설계에 대한 비밀을 공개하지 않고 한 국가는 이제 핵 검사관에게 탄두가 활성인지 비활성화되었는지 증명할 수 있습니다.
최근에는 양자 컴퓨팅의 발전으로 인해 Crépeau가 과거 연구를 스트레스 테스트하여 영지식 프로토콜이 여전히 실행 가능한지 확인해야 했습니다. 2021년에 그는 보여 다중 증명자 대화형 증명은 양자 컴퓨터가 관련된 경우에도 비밀을 유지하지만 동일한 수준의 보안을 달성하면 프로토콜이 훨씬 느려집니다. 그는 이 발견은 좋은 소식이지만 기술이 발전함에 따라 새로운 우려가 제기될 것이라고 말했다.
"우리가 미래에 할 수 있는 모든 유형의 계산에는 양자 컴퓨터가 포함될 것입니다."라고 Crépeau가 말했습니다. "좋은 편집증 암호학자로서 우리는 시스템의 보안을 평가할 때마다 시스템이 안전한지 확인하고 싶습니다."
편집자 주: Shafi Goldwasser는 Simons Foundation으로부터 자금을 지원받았으며, 이 또한 이 자금을 지원합니다. 사설 독립 출판물. Simons Foundation 기금 결정은 당사의 보장에 영향을 미치지 않습니다.
