영지식 증명. 기밀 정보에 대한 영지식 증명 프로토콜입니다. 다른 사전에 "영지식 증명"이 무엇인지 확인하세요
증명 사용 지식이 전혀 없다기밀 정보는 구체적인 예를 들어 설명할 수 있습니다. 동굴이 있다고 가정해보자. 동굴 입구는 A 지점에 있고 B 지점에서는 동굴이 C와 D의 두 부분으로 갈라집니다. 동굴에는 비밀이 있습니다. 마법의 단어를 아는 사람만이 C와 D 사이에 있는 문을 열 수 있다는 것입니다.
안톤은 마법의 단어를 알고 있지만 보리스는 모릅니다. 안톤은 보리스에게 자신이 마법의 단어를 알고 있다는 것을 증명하고 싶어하지만 보리스는 여전히 이 단어에 대해 어둠 속에 남아 있습니다. 그런 다음 Anton은 다음 프로토콜을 사용할 수 있습니다.
1. 보리스는 A 지점에 서 있습니다.
2. Anton은 자신의 선택에 따라 C 지점에서 문으로 접근합니다.
또는 D 지점에서.
3. 보리스는 B 지점으로 이동합니다.
4. 보리스는 안톤에게 문 왼쪽 통로를 통해 나타나라고 명령합니다.
아니면 오른쪽을 통해.
5. Anton은 필요한 경우 다음을 사용하여 Boris의 명령을 따릅니다.
문을 통과하라는 마법의 말.
6. 1~5단계가 n번 반복됩니다. 여기서 n은 프로토콜 매개변수입니다.
보리스가 동굴 깊은 곳에서 안톤이 사라진 모든 것과 이후의 모든 모습을 기록하는 비디오 카메라를 가지고 있다고 가정해 봅시다. 보리스가 안톤과 함께 수행한 모든 n번의 실험 기록을 보여준다면, 이 기록은 안톤이 다른 사람(예를 들어 블라디미르)에 대한 마법의 단어를 알고 있다는 증거가 될 수 있습니까?
거의 ~ 아니다. Vladimir는 Anton이 매번 Boris에게 자신의 의도를 미리 알리지 않았는지 확인할 수 없으므로 Boris는 Anton이 들어온 문 옆에서 정확히 떠나라고 명령했습니다. 또는 안톤이 보리스의 명령을 수행할 수 없었던 실패한 모든 실험이 만들어진 비디오 녹화에서 제외되지 않았습니다.
이는 보리스가 동굴 실험 중에 개인적으로 참석하지 않은 블라디미르에게 안톤이 실제로 비밀에 대한 지식을 확인했다고 설득할 수 없음을 의미합니다. 이는 Anton이 사용하는 증명 프로토콜이 기밀 정보를 전혀 공개하지 않는다는 특징을 가지고 있음을 의미합니다. Anton이 동굴의 문을 여는 마법의 단어를 모른다면 Anton을 보면서 Boris는 아무것도 알아낼 수 없습니다. Anton이 마법의 단어를 알고 있다면 수행된 실험에 대한 자세한 비디오 녹화도 Boris에게 도움이 되지 않습니다. 첫째, 보리스는 시청할 때 이미 라이브로 본 것만 볼 수 있기 때문입니다. 둘째, 보리스가 위조한 영상과 진짜 영상을 구별하는 것이 거의 불가능하기 때문이다.
영지식 증명 프로토콜은 마법의 단어를 모르면 Anton이 자신이 들어온 쪽에서만 나갈 수 있다는 사실 때문에 작동합니다. 따라서 모든 경우의 50%에서만 Anton이 어느 쪽에서 떠나라고 요청할지 추측하여 Boris를 속일 수 있습니다. 실험 횟수가 n이면 Anton은 2n개 중 한 가지 경우에만 모든 테스트를 성공적으로 통과합니다. 실제로는 n=16으로 제한할 수 있습니다. 안톤이 16가지 경우 모두에서 보리스의 명령을 올바르게 실행했다면 그는 실제로 마법의 단어의 비밀을 알고 있는 것입니다.
동굴의 예는 예시적이지만 심각한 결함이 있습니다. Boris는 Anton이 지점 B에서 어떻게 한 방향으로 회전한 다음 반대편에서 나타나는지 확인하는 것이 훨씬 쉽습니다. 여기서는 영지식 증명 프로토콜이 필요하지 않습니다.
따라서 Anton이 "Open Sesame"과 같은 마법의 단어를 모른다고 가정해 보겠습니다. 아니요, Anton은 더 흥미로운 정보를 가지고 있습니다. 그는 이 어려운 문제에 대한 해결책을 찾은 최초의 사람이었습니다. 이 사실을 Boris에게 증명하기 위해 Anton은 자신의 결정을 모든 사람에게 보여줄 필요가 없습니다. 그가 해야 할 일은 기밀 정보에 대해 다음 영지식 증명 프로토콜을 적용하는 것뿐입니다.
1. Anton은 자신이 보유한 정보와 생성된 정보를 사용합니다.
어려운 문제를 원래 문제와 동형인 또 다른 어려운 문제로 줄이기 위한 난수입니다. 그런 다음 Anton은 이 새로운 문제를 해결합니다.
2. Anton은 다음에서 발견된 비트에 대해 비트 예측 프로토콜을 사용합니다.
그러면 나중에 Boris가 이 결정을 숙지해야 하는 경우 Anton이 제시한 결정이 1단계에서 실제로 수신되었는지 Boris가 확실하게 확인할 수 있습니다.
3. 안톤은 보리스에게 새로운 어려운 문제를 보여주고,
4. 보리스는 안톤에게 두 가지 어려운 문제가 있음을 증명해 달라고 요청합니다.
(기존 및 새) 동형이거나 Anton이 1단계에서 찾았어야 했던 솔루션을 제공하고 Anton이 동일한 단계에서 원래 문제를 축소한 문제에 대한 솔루션임을 증명합니다.
5. 안톤은 보리스의 요청을 이행합니다.
6. Anton과 Boris는 1~6단계를 n번 반복합니다. 여기서 n은 매개변수입니다.
규약.
해결하기 어려운 문제, 한 문제를 다른 문제로 줄이는 방법, 난수가능하다면 프로토콜의 단계를 반복한 후에도 Boris가 원래 문제에 대한 해결책에 관한 정보를 갖지 않도록 선택해야 합니다.
해결하기 어려운 모든 문제가 기밀 정보의 영지식 증명에 사용될 수 있는 것은 아니지만 대부분은 그러한 목적에 매우 적합합니다. 예를 들어 연결된 그래프에서 해밀턴 사이클(그래프의 모든 꼭지점을 한 번만 통과하는 닫힌 경로)을 찾고 그래프 동형(두 그래프가 꼭지점 이름만 다를 경우 동형임)을 결정하는 것이 포함됩니다.
영지식 증명은 당사자 중 하나(검증자, 당사자 B)가 다른 당사자(증명자, 당사자 A)가 일부 진술을 알고 있는지 확인할 수 있도록 하는 반면, 검증자는 진술 자체에 대한 다른 정보를 수신하지 못하도록 하는 암호화 프로토콜입니다. 즉, A는 비밀 자체를 밝히지 않고 비밀을 알고 있음을 증명한다.
신원을 증명하기 위해 영지식 증명을 사용하는 것은 Uriel Fieg, Amos Fiat 및 Adi Shamir에 의해 처음 제안되었습니다. 안에 이 경우사용자는 자신의 개인 키에 대해 알고 있음을 증명합니다. 이 경우 개인 키는 공개하지 않고 비밀로 작용합니다. 이런 식으로 그는 자신의 정체성을 증명합니다.
영지식 증명에는 세 가지 주요 속성이 있습니다.
1. 완전성. 증명자가 그 진술을 알고 있다면 그는 검증자를 설득할 수 있을 것입니다.
2. 정확성. 증명자가 그 진술을 모른다면 그는 무시할 확률로만 검증자를 속일 수 있습니다.
3. 지식이 전혀 없습니다. 검증자는 부정직하게 행동하더라도 그 진술이 증명자에게 알려져 있다는 사실 외에는 아무것도 배우지 못할 것입니다.
증명은 대화형 프로토콜의 형태를 취합니다. 이는 B가 증명자에게 일련의 질문을 하고, 그가 비밀을 안다면 모든 질문에 정확하게 답할 것임을 의미합니다. 당사자 A가 비밀을 알지 못하지만 조사관을 설득하고 싶다면 질문에 올바르게 답할 확률(이 항목의 예에서와 같이 50% 정도)이 있습니다. 그러나 일정한 수의 질문(10~20개) 후에 검증자는 증명자가 비밀을 모른다고 상당히 높은 확률로 확신합니다. 그러나 답변 중 어느 것도 비밀 자체에 대한 정보를 제공하지 않습니다.
제로 지식의 동굴
영지식 증명은 Jean-Jacques Quiscaterre와 Louis Guilloux가 알리바바의 동굴 이야기를 사용하여 잘 설명합니다(그림 참조). 동굴을 통과하려면 C와 D 사이의 문을 열어야 합니다. 누군가 마법의 말을 해야 문이 열립니다. Peggy에게 마법의 단어를 알려주고 단어 자체를 공개하지 않고 Victor에게 그것을 증명하고 싶습니다.이 경우 영지식 증명이 작동하는 방식은 다음과 같습니다.
1. 빅터는 A 지점에 있습니다.
2. Peggy는 통로 C나 통로 D를 따라 동굴을 통과하여 문까지 계속 걸어갑니다. Victor는 Peggy가 어느 방향으로 갔는지 알지 못합니다. Peggy가 동굴 속으로 사라진 후 Victor는 B 지점으로 이동합니다.
3. 빅터는 페기에게 왼쪽 통로나 오른쪽 통로로 동굴에서 나가라고 소리칩니다.
4. Peggy는 필요한 경우 마법의 단어를 사용하여 문을 열고 Victor가 그녀에게 나오라고 요청한 통로에서 동굴을 나갑니다.
5. Peggy와 Victor는 1~4단계를 여러 번 반복합니다.
Peggy가 비밀을 모르는 경우 증명(인증) 단계가 여러 번 연속 반복되면 Victor를 속일 수 없습니다. 그녀는 자신이 들어간 통로에서만 나갈 수 있기 때문에 프로토콜의 각 라운드에서 Victor가 그녀에게 어느 쪽에서 나가라고 요청할지 추측할 확률은 50%입니다. 따라서 그녀가 빅터를 속일 확률도 50%이다. 그러나 두 라운드에서 그를 속일 확률은 이미 25%이고, n 라운드에서 그녀는 2^n에 단 한 번의 기회만 갖습니다. Victor는 Peggy의 증명의 n(n=10-20) 라운드가 모두 정확하다면 C와 D 사이의 문을 여는 비밀 단어를 알고 있다고 자신 있게 가정할 수 있습니다.
Victor가 비디오 카메라에서 일어나는 모든 일을 녹화한다면 이 비디오 녹화는 제3자에게 증거가 되지 않습니다. Peggy와 Victor는 Victor가 그녀에게 떠나라고 요청할 곳을 미리 합의할 수도 있었습니다. 그런 다음 그녀는 마법의 단어를 모르고 매번 Victor가 지정한 장소를 떠날 것입니다. 반면에 Victor는 비디오 녹화를 위조하여 Peggy의 성공적인 시도만 남기고 다른 모든 것을 잘라낼 수 있습니다.
동굴 비유가 완전히 정확하지는 않다는 점에 유의해야 합니다. 단어에 대한 지식을 증명하기 위해 Peggy는 한쪽에서 간단히 들어갈 수 있고 Victor는 그녀가 어느 방향으로 갔는지 확인하고 다른 쪽에서 나갈 수 있습니다. 그러나 이 프로토콜은 수학적 관점에서 영지식 증명을 완벽하게 설명합니다.
법정화폐-샤미르 프로토콜
가장 잘 알려진 영지식 증명 프로토콜 중 하나는 검색의 어려움을 기반으로 하는 Amos Fiat와 Adi Shamir가 제안한 프로토콜입니다. 제곱근모듈로 충분히 큰 합성수 n, 인수분해는 알려져 있지 않습니다.이전에는 증명 자체에 앞서 신뢰 센터 T가 인수분해하기 어려운 충분히 큰 수 n = p*q의 모듈을 선택하여 게시했습니다. 이 경우 p, q - 소수비밀로 유지됩니다. 각 사용자 A는 n까지의 간격 (1, n−1) coprime에서 비밀 s를 선택합니다. 그런 다음 공개 키 v = s^2(mod n)가 계산됩니다.
결과 v는 사용자 A의 공개 키로 신뢰 센터에 등록되고 값 s는 A의 비밀입니다. A는 이 비밀 s에 대한 지식을 t 라운드에 공개하지 않고 당사자 B에게 증명해야 합니다. 각 인증은 다음 단계로 구성됩니다.
1. A는 간격 (1, n−1)에서 임의의 r을 선택하고 x = r^2 (mod n)을 파티 B에 보냅니다.
2. B는 비트 e(0 또는 1)를 무작위로 선택하여 A로 보냅니다.
3. A는 y = r*s^e(mod n)을 계산하여 B로 다시 보냅니다.
4. B측은 y^2 CHAR x*v^e(mod n)가 동일한지 확인합니다. 그것이 사실이라면, 프로토콜의 다음 라운드로의 전환이 일어나고, 그렇지 않으면 증명이 받아들여지지 않습니다.
세트에서 e를 선택하는 것은 당사자 A가 실제로 비밀을 알고 있다면 선택한 e에 관계없이 항상 정확하게 대답할 수 있다는 것을 의미합니다. A가 B를 속이고 싶어하고 임의의 r을 선택하고 x = r^2 / v를 보낸 다음 e = 0이면 A는 성공적으로 B y = r을 반환하고 e = 1의 경우 A는 그렇지 않습니다. 정확하게 대답할 수 있습니다. t .To. s를 모르고 v 모듈로 n의 제곱근을 추출하는 것은 매우 어렵습니다.
사용자 A가 비밀 s를 모르지만 검사자 B가 그 반대임을 확신할 확률은 p = =2^(-t)와 동일한 확률로 추정됩니다. 여기서 t는 인증 수입니다. 높은 신뢰도를 얻으려면 충분히 큰 크기(t = 20 − 40)가 선택됩니다. 따라서 B는 모든 t 라운드가 성공한 경우에만 A를 알고 있음을 인증받습니다.
이 프로토콜이 올바르게 실행되려면 당사자 A는 x 값을 절대 재사용해서는 안 됩니다. A가 이 작업을 수행하고 다른 루프의 B가 2단계에서 A에게 또 다른 임의 비트 r을 보낸 경우 B는 A의 답을 모두 갖게 되며 B는 s의 값을 계산할 수 있고 Alice의 비밀 키를 알게 됩니다.
결론
스마트 카드와 같은 구현의 경우 Fiat-Shamir 프로토콜은 그다지 적합하지 않습니다. 외부 세계시간이 걸리며 각 인증에 대한 데이터를 저장하면 빠르게 소진될 수 있습니다. 제한된 기회카드. 따라서 Gillu와 Kiskatr는 다음과 같은 목적에 더 적합한 영지식 식별 알고리즘을 개발했습니다. 유사한 응용 프로그램. Peggy와 Victor 간의 교환과 각 교환의 병행 인증은 최소한으로 유지됩니다. 각 증거에 대해 단 하나의 교환만 있으며, 여기에는 단 하나의 인증만 있습니다. Gillu-Kiskatra 및 Fiat-Shamir 방식의 대안인 Schnorr 방식도 있습니다. 주제가 마음에 드시면 다음 주제에서 이에 대해 쓰겠습니다. 영지식 증명)는 상대방(증명자)으로부터 다른 정보를 받지 않고도 당사자(검증자) 중 하나가 진술(일반적으로 수학적 진술)의 신뢰성을 확인할 수 있도록 하는 대화형 프로토콜입니다.영지식 증명에는 세 가지 속성이 있어야 합니다.
- 완전성: 만약 그 진술이 정말로 참이라면, 증명자는 검증자에게 이를 확신시킬 것입니다.
- 단정: 진술이 거짓인 경우 부정직한 증명자라도 무시할 수 있는 확률을 제외하고는 검증자를 설득할 수 없습니다.
- 지식 제로: 진술이 사실이라면 부정직한 검증자라도 그 진술이 사실이라는 사실 외에는 아무것도 알 수 없습니다.
영지식 증명의 일반적인 구조
각 라운드 또는 증거 인정은 다음으로 구성됩니다. 세 단계. 그것들은 다음과 같이 개략적으로 묘사될 수 있습니다:
처음에는 ㅏ미리 결정된 집합에서 자신의 비밀(개인 키)이 될 요소를 선택합니다. 이 요소를 기반으로 공개 키가 계산된 후 게시됩니다. 비밀을 아는 것은 많은 질문을 결정합니다. ㅏ언제나 올바른 답을 드릴 수 있을 것입니다. 그 다음에 ㅏ특정 규칙에 따라(특정 알고리즘에 따라) 세트에서 임의의 요소를 선택합니다. 증거그런 다음 그것을 멀리 보냅니다 비. 이후 비전체 질문 중에서 하나를 선택하여 질문합니다. ㅏ대답하라 ( 부르다). 질문에 따라, ㅏ보낸다 B 답변. 수신된 정보 비여부를 충분히 확인할 수 있습니다. ㅏ비밀을 소유하고 있습니다. 라운드는 다음 확률이 나올 때까지 필요한 만큼 반복될 수 있습니다. ㅏ"추측" 답변은 충분히 낮아지지 않습니다.
이 기술은 "잘라내기 및 선택"이라고도 합니다.
예
검증측을 Petya라고 하고, 검증측을 Dima라고 부르자(영어 문헌 쌍 Peggy(from 증명자) 및 Victor(에서 검증자). Dima가 큰 그래프에서 해밀턴 주기를 알고 있다고 가정합니다. G. Petya는 백작님을 알고 있습니다 G, 그러나 그는 그 안의 해밀턴 순환을 알지 못합니다. Dima는 주기 자체나 이에 대한 정보를 제공하지 않고 자신이 해밀턴 주기를 알고 있음을 Petya에게 증명하고 싶어합니다(아마도 Petya는 Dima에서 이 해밀턴 주기를 구입하고 싶어하지만 그 전에 Dima가 실제로 그것을 가지고 있는지 확인하십시오).
이를 위해 Petya와 Dima는 여러 라운드의 프로토콜을 공동으로 수행합니다.
각 라운드에서 Petya는 Dima가 알지 못하는 새로운 무작위 비트를 선택하므로 Dima가 두 질문에 답하려면 다음이 필요합니다. 시간정말 동형이었어 G그리고 Dima는 해밀턴 사이클을 알아야 합니다. 시간(따라서 또한 G). 따라서 충분한 수의 라운드 후에 Petya는 Dima가 실제로 해밀턴 사이클을 가지고 있음을 확신할 수 있습니다. G. 반면에 Dima는 해밀턴주기에 대한 정보를 공개하지 않습니다. G. 더욱이 Petya가 자신이나 Dima가 해밀턴 주기를 알고 있다는 사실을 다른 사람에게 증명하는 것은 어려울 것입니다. G.
Dima에 해밀턴 사이클이 없다고 가정해 보겠습니다. G그는 Petya를 속이고 싶어합니다. 그러면 Dima는 비동형이 필요합니다. G그래프 G", 그는 여전히 해밀턴주기를 알고 있습니다. 각 라운드에서 그는 Petya에게 패스할 수 있습니다. 시간"- 동형 G", 또는 시간- 동형 G. Petya가 동형성을 증명하도록 요청하고 통과된 경우 시간, 그러면 속임수가 드러나지 않습니다. 마찬가지로, 그가 해밀턴 사이클을 보여달라고 요청했고, 시간". 이 경우 Dima가 이후에도 Petya를 속일 가능성은 다음과 같습니다. N라운드 수는 1/2 n과 동일하며, 이는 충분한 수의 라운드가 주어지면 미리 결정된 값보다 작을 수 있습니다.
Petya가 해밀턴 순환을 인식하지 못하지만 Dima가 그것을 알고 있다는 것을 Vasya에게 증명하고 싶다고 가정해 보십시오. 예를 들어 Petya가 프로토콜의 모든 라운드를 촬영했다면 Vasya는 그를 믿지 않을 것입니다. Vasya는 Petya와 Dima가 공모하고 있다고 가정할 수 있으며 각 라운드에서 Petya는 Dima가 그에게 넘겨줄 수 있도록 임의의 비트 선택을 미리 Dima에게 알렸습니다. 시간동형성 검사 및 시간"해밀턴 사이클을 확인하기 위한 것입니다. 따라서 Dima의 참여 없이 프로토콜의 모든 라운드에서 실제로 무작위 비트가 선택되었음을 증명함으로써만 그가 해밀턴 주기를 알고 있음을 증명할 수 있습니다.
남용
영지식 증명을 남용하는 여러 가지 방법이 제안되었습니다.
또한보십시오
- 길루-키스카트라 프로토콜
문학
- A. Menezes, P. van Oorschot, S. Vanstone.응용암호화 핸드북. - CRC Press, 1996. - 816 p. - ISBN 0-8493-8523-7
- 슈나이어 B.암호화를 적용했습니다. C 언어의 프로토콜, 알고리즘, 소스 텍스트 = 응용 암호화. C.의 프로토콜, 알고리즘 및 소스 코드 - M.: Triumph, 2002. - 816 p. - 3000부. - ISBN 5-89392-055-4
위키미디어 재단. 2010.
- 폰비지나, 나탈리아 드미트리예브나
- 추주모보
다른 사전에 "영지식 증명"이 무엇인지 확인하십시오.
기밀 정보에 대한 영지식 증명- 지식의 뚫을 수 없는 증거; 이 정보를 공개하지 않고 정보를 소유하고 있음을 증명합니다. 주제: 정보 보호 EN 영지식 증명…
민감한 정보에 대한 반복적인 영지식 증명- — 주제 정보 보안 EN 영지식 반복 증명ZKIP … 기술 번역가 가이드
민감한 정보에 대한 비반복적 영지식 증명- NDNR - [] 주제 정보 보호 동의어 NDNR EN 비반복 영지식 증명NIZK ... 기술 번역가 가이드
암호화- 독일 로렌츠 암호화 기계는 제2차 세계 대전 중에 가장 비밀스러운 메시지 암호화를 암호화하는 데 사용되었습니다. 암호화(다른 그리스에서 온 ... Wikipedia
알고리즘 목록- 이 페이지는 정보 목록입니다. 주요 기사: 알고리즘 아래는 카테고리별로 그룹화된 알고리즘 목록입니다. 더 자세한 정보는 데이터 구조 목록과 ... Wikipedia에 나와 있습니다.
암호 사용자- 제2차 세계대전 중 가장 비밀스러운 메시지를 암호화하는 데 사용된 독일 로렌츠 암호화 기계 암호화(그리스어 κρυπτός 숨겨진 및 γράΦΩ 쓰기에서 유래) 과학 수학적 방법기밀 유지... ... Wikipedia
프로그래밍 가능한 알고리즘- 주제 개발에 대한 작업을 조정하기 위해 작성된 기사 서비스 목록입니다. 이 경고는 설정되지 않았습니다... Wikipedia
SRP- SRPP(Secure Remote Password Protocol)는 도청 및 MITM 공격에 강하고 신뢰할 수 있는 제3자가 필요하지 않은 비밀번호 인증 프로토콜입니다. SRP에는 다른 키 교환 및 식별 프로토콜의 일부 요소가 포함되어 있습니다... Wikipedia
법정화폐 프로토콜- Fiat Shamir 프로토콜은 가장 유명한 영지식 식별 프로토콜(Zero Knowledge Protocol) 중 하나입니다. 이 프로토콜은 Amos Fiat와 Adi Shamir에 의해 제안되었습니다. Let A... ... Wikipedia
법정화폐-샤미르 프로토콜- Fiat Shamir 프로토콜은 가장 유명한 영지식 식별 프로토콜(Zero Knowledge Protocol) 중 하나입니다. 이 프로토콜은 Amos Fiat와 Adi Shamir에 의해 제안되었습니다. A에게 알려주세요... ... Wikipedia
암호학의 주요 문제점 중 하나는 한 참가자(증명자)가 증명의 본질을 밝히지 않고 다른 참가자(검증자)에게 진술의 진실성을 증명하는 양방향 대화형 게임입니다. 이 경우 검증자는 증명자가 사용할 수 있는 정보를 모르기 때문에 진술의 진실성을 독립적으로 평가할 수 없습니다. 이 게임을 대화형 증명 프로토콜(시스템) 또는 IP 프로토콜(대화형 증명 - IP)이라고 합니다. IP 프로토콜에 의해 수행되는 증명은 “비밀 증명”(“어둠 속의 증명”)이라고 할 수 있습니다. 이 증명의 비밀은 첫째, 증명되는 진술의 진실성을 확신한 검증 당사자가 독립적으로 증명을 반복할 수 없으며, 둘째, 프로토콜이 완료된 후에는 누구도 증명할 수 없다는 사실에 있습니다. 의 외부인은 증명 당사자와 검토 당사자 간에 교환되는 단일 메시지를 이해할 수 있습니다.
증명의 본질을 드러내지 않고 증명해야 할 진술이 일부 유명한 미해결 문제에 대한 해결책이라고 상상해 봅시다. 수학 문제. 이 경우, 표절을 두려워하는 증명자는 잠재적으로 부정직한 검토자에게 증명의 기술적 세부 사항을 숨기고 싶어할 수 있습니다. 이를 위해 그녀는 추가 정보를 제공하지 않고 검토자(IP 프로토콜에서 신뢰 당사자 역할을 하는)에게 결론의 정확성을 확신시키는 "비밀" 증명을 수행해야 합니다.
많은 것에서 실제 응용"비밀" 증거를 수행하는 데에는 훨씬 더 심각한 이유가 있습니다. 일반적으로 IP 프로토콜은 엔터티를 인증하는 데 사용됩니다. 사용자가 입력하는 기존 인증 프로토콜과 달리 디지털 서명 IP 프로토콜에서 인증할 증명자는 메시지가 신뢰 당사자 이외의 누구에게도 공개되는 것을 원하지 않으며 "비밀" 인증을 수행합니다. 또한 IP 프로토콜은 숨겨진 정보가 특정 구조를 가지고 있음을 증명하는 데 자주 사용됩니다. 이는 일부 민감한 애플리케이션(예: 전자 경매를 수행하는 경우)에 필요합니다. 숨겨진 숫자(lot)은 허용 범위 내에 있어야 합니다(예를 들어 입찰가를 나타내는 및 의 값을 공개하지 않고 x > y임을 입증해야 함).
IP 프로토콜을 고려할 때 고려해야 할 두 가지 문제가 있습니다.
- 질문 1. 검증자는 대화형 증명 중에 얼마나 많은 정보를 받게 됩니까?
- 질문 2: 검증자를 설득하려면 증명자는 몇 라운드를 수행해야 합니까?
첫 번째 질문에 대한 이상적인 대답은 “전혀 아니다” 또는 “0”이다. IP 프로토콜이 속성을 갖는 프로토콜을 영지식 프로토콜 또는 ZK 프로토콜(영지식 - ZK)이라고 합니다. 두 번째 질문은 실제 적용뿐만 아니라 계산 복잡도 이론에도 중요합니다. 왜냐하면 이 문제를 해결하려면 더 낮은 복잡도 추정치를 얻는 것이 포함되기 때문입니다.
개발의 역사
영지식 증명은 Shafi Goldwasser, Silvio Mikali 및 Charles Recoff와 같은 과학자들이 발명하고 개발했으며, 1985년 "대화형 증명 시스템의 지식과 복잡성"이라는 기사에 게재되었습니다. 이 작업은 증명자에서 검증자로 전송되어야 하는 증명 정보의 양을 기반으로 하는 대화형 증명 시스템의 계층 구조를 제시했습니다. 그들은 또한 특별히 공식화된 영지식 증명(2차 잔차 모듈로 m)의 첫 번째 증명을 제안했습니다. 이후 작업을 확장하여 1993년에 첫 번째 괴델상을 수상했습니다.
계속...
지식 제로
계산 모델
대화형 증명 프로토콜의 기본 모델을 (P,V)로 표시하겠습니다. 여기서 P는 증명자이고 V는 검증자입니다. 원칙적으로 (P,V) 프로토콜은 특정 문장이 알파벳 (0,1)*에 지정된 언어에 속하는지 검증하도록 설계되었습니다.
L을 알파벳 (0,1)* 위의 언어라고 하자. P측과 V측은 공통 입력인 샘플 xϵL을 수신합니다. 샘플 소유권 증명은 (P,V)(x)로 표시됩니다. 프로토콜의 양쪽은 정보를 교환하는 통신 채널로 연결됩니다.
프로토콜의 결과는 (P,V)(x) ϵ(수락, 거부) 형식으로 작성됩니다.
이 두 값은 검증자가 증명자 P의 주장 xϵL을 확인하거나 반박한다는 것을 의미합니다. 시스템 (P,V)는 확률적이므로 각 x에 대해 결과 (P,V)(x)는 확률 변수입니다. 일반 입력 데이터 x, 사용자 P의 비공개 입력 데이터(비공개 입력), 사용자 P와 Q에 공통된 일부 무작위 입력 데이터(임의 입력)에 따라 달라집니다.
(P,V) 프로토콜은 양면 게임이기 때문에 각 측면이 추가적인 이점을 얻으려고 한다고 가정하는 것이 당연합니다. 한편, 증명자 P는 x가 L에 속하지 않더라도 x를 수락한 결과에 관심이 있어야 합니다. 이러한 부정 행위 증명자 전략을 추구하는 증명자는 P'로 표시됩니다. 반면, 검증자 V는 플레이어 P의 비공개 입력 데이터에 대한 정보를 공개하는 데 관심이 있어야 합니다. 이러한 부정직한 검증자를 따르는 검증자를 V'라고 표시합니다.
질문 1(P,V)에 대한 이상적인 대답(영지식 프로토콜)이 있다고 가정해 보겠습니다. 사용자 V(또는 V')는 자신의 개인 입력에 대해 새로운 것을 배우지 않고 사용자 P의 주장이 올바른지 확인합니다.
(P,V) 프로토콜이 이러한 특성을 갖기 위해서는 사용자의 컴퓨팅 파워 V(또는 V')를 입력 정보의 크기에 따라 다항식으로 제한해야 합니다. 분명히 이러한 제한이 없으면 무제한의 컴퓨팅 자원을 가진 사용자 V가 사용자 R의 비밀 입력 데이터를 독립적으로 공개할 수 있으므로 영지식이 보장될 수 없습니다.
대화형 증명 프로토콜의 공식적인 정의
대화형 증명 프로토콜을 정의해 보겠습니다. L을 알파벳 (0,1)*에 대해 정의된 언어로 둡니다. IP 프로토콜(P,V)은 다음과 같은 경우 언어 L에 대한 대화형 증명 시스템이라고 합니다.
그리고
여기서 숫자 ϐ 및 ϐ는 조건 τϵ(1/2;1], ϐϵ)을 충족하는 상수입니다.
