영지식 증명 프로토콜 c. 영지식 증명 프로토콜: 백서. 영지식 증명 프로토콜: 작동 방식
영지식 증명에는 세 가지 속성이 있어야 합니다.
- 완전성: 만약 그 진술이 정말로 참이라면, 증명자는 검증자에게 이를 확신시킬 것입니다.
- 단정: 진술이 거짓인 경우 부정직한 증명자라도 무시할 수 있는 확률을 제외하고는 검증자를 설득할 수 없습니다.
- 지식 제로: 진술이 사실이라면 부정직한 검증자라도 그 진술이 사실이라는 사실 외에는 아무것도 알 수 없습니다.
영지식 증명의 일반적인 구조
각 라운드 또는 증거 인정은 다음으로 구성됩니다. 세 단계. 그것들은 다음과 같이 개략적으로 묘사될 수 있습니다:
처음에는 ㅏ미리 결정된 집합에서 자신의 비밀(개인 키)이 될 요소를 선택합니다. 이 요소를 기반으로 공개 키가 계산된 후 게시됩니다. 비밀을 아는 것은 많은 질문을 결정합니다. ㅏ언제나 올바른 답을 드릴 수 있을 것입니다. 그 다음에 ㅏ특정 규칙에 따라(특정 알고리즘에 따라) 세트에서 임의의 요소를 선택합니다. 증거그런 다음 그것을 멀리 보냅니다 비. 이후 비전체 질문 중에서 하나를 선택하여 질문합니다. ㅏ대답하라 ( 부르다). 질문에 따라, ㅏ보낸다 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
영지식 증명은 당사자 중 하나(검증자, 당사자 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가 t 라운드에서 이를 공개하지 않고 당사자 B에게 입증해야 하는 것은 이 비밀 s에 대한 지식입니다. 각 인증은 다음 단계로 구성됩니다.
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 방식도 있습니다. 주제가 마음에 드시면 다음 주제에서 이에 대해 쓰겠습니다.영지식 증명 사용 기밀 정보구체적인 예를 들어 설명할 수 있다. 동굴이 있다고 가정해보자. 동굴 입구는 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은 매개변수입니다.
규약.
해결하기 어려운 문제, 한 문제를 다른 문제로 줄이는 방법, 난수 등은 가능하면 보리스가 위의 단계를 반복한 후에도 원래 문제의 해결 방법에 관한 정보를 갖지 않도록 선택해야 합니다. 규약.
해결하기 어려운 모든 문제가 기밀 정보의 영지식 증명에 사용될 수 있는 것은 아니지만 대부분은 그러한 목적에 매우 적합합니다. 예를 들어 연결된 그래프에서 해밀턴 사이클(그래프의 모든 꼭지점을 한 번만 통과하는 닫힌 경로)을 찾고 그래프 동형(두 그래프가 꼭지점 이름만 다를 경우 동형임)을 결정하는 것이 포함됩니다.
앨리스가 특정 정리의 증명을 알고 있고 그 정리가 참이라는 것을 밥에게 설득하고 싶다고 가정해 보겠습니다. 물론 Alice는 확인을 위해 Bob에게 증명을 전달할 수도 있습니다. 그러나 이후 Bob은 Alice의 도움 없이도 이 정리를 제3자에게 직접 증명할 수 있습니다. 앨리스는 정리 증명을 재구성하는 데 도움이 되는 정보를 받지 않고도 밥을 설득할 수 있습니까? 겉으로는 상호 배타적인 것처럼 보이는 이 두 가지 요구 사항은 영지식 증명 프로토콜에 의해 충족됩니다. 후자의 개념은 1985년 Goldwasser, Micali 및 Rakoff에 의해 도입되었습니다.
다음과 같은 프로토콜 모델이 고려됩니다. 앨리스와 밥은 각각 확률론적 튜링 기계를 갖고 있습니다. Alice가 사용할 수 있는 계산 리소스는 무제한이지만 머신 V는 다항식 시간에 실행됩니다. 기계에는 메시지 교환을 위한 공통 통신 피드가 있습니다. 통신 테이프에 메시지를 녹음한 후, 기기는 대기 상태로 들어가고 응답 메시지가 테이프에 녹음되는 즉시 종료됩니다. 기계에는 입력 단어 x가 기록되는 공통 입력 테이프도 있습니다. Alice가 증명한 진술에는 고정된(Alice와 Bob 모두에게 알려진) 언어가 있습니다. 사소함을 피하기 위해 언어는 어려워야 합니다(예: NP-완전). 그렇지 않으면 Bob이 독립적으로 이를 확인할 수 있습니다. 기본적으로 증명 프로토콜은 Bob이 무작위성을 사용하여 몇 가지 질문을 선택하고 Alice에게 질문한 후 정확성을 확인하는 것입니다. 답변 중. 프로토콜은 기계 V가 중지되면 종료되며, 증명이 승인되면 1을 출력하고 그렇지 않으면 0을 출력합니다.
두 개의 대화형, 즉 공통 통신 테이프를 통해 상호 작용하는 확률적 튜링 기계가 있다고 가정합니다. Through는 A와 B가 입력 단어 x에 대해 작업할 때 기계 A의 출력 단어인 무작위 변수를 나타냅니다. 단어 x의 길이는 다음과 같이 표시됩니다.
정의 4. 언어에 대한 대화형 증명은 다음 두 가지 조건이 충족되는 대화형 Turing 기계 쌍입니다.
1. (완전성). 모든
2. (정확성). 다항식과 충분히 큰 길이의 모든 튜링 기계에 대해
완전성은 입력 단어가 해당 언어에 속하고 Alice와 Bob이 모두 프로토콜을 따르는 경우 증명이 항상 허용된다는 것을 의미합니다. 정확성에 대한 요구 사항은 거짓 진술을 "증명"하여 그를 속이려고 하는 부정직한 앨리스로부터 밥을 보호합니다. 이 경우 Alice는 프로토콜에 규정된 작업에서 어떤 방식으로든 벗어날 수 있습니다(즉, Turing 기계 대신 다른 기계를 사용할 수 있음) 어떤 경우에도 속임수 가능성이 무시할 수 있어야 합니다.
정의 5. 언어에 대한 대화형 증명 프로토콜은 조건 1과 2 외에도 다음 조건도 충족하는 경우 완전 영지식 증명이라고 합니다.
3. (지식재산권 제로). 모든 다항식 확률적 튜링 기계 V에 대해 평균 다항식 시간에 실행되는 확률적 튜링 기계가 있습니다.
이 기계는 시뮬레이션 기계라고 불립니다. 작동 시간에 대한 수학적 기대는 길이 x의 다항식에 의해 제한된다고 가정합니다. 이는 원칙적으로 작업에 사용되는 확률 변수가 어떤 값을 취하는지에 따라 꽤 오랜 시간 동안 작동할 수 있음을 의미합니다. 그러나 작업 시간이 특정 다항식 범위를 초과할 확률은 작습니다. 각 기계 V에 대해 자체 모델링 기계가 구축됩니다. 후자는 V를 서브루틴으로 사용할 수 있습니다. Through는 무작위 변수(입력에서 단어 x를 수신할 때 기계의 출력 단어)를 나타냅니다.
영지식 속성은 프로토콜에 규정된 작업에서 임의로 벗어나(V 대신 V 사용) 프로토콜 실행에서 추가 정보를 추출하려고 시도하는 부정직한 Bob으로부터 Alice를 보호합니다. 조건 3은 Bob이 다항식 시간에 프로토콜을 실행하여 독립적으로 계산할 수 있는 정보만 얻을 수 있음을 의미합니다.
Goldreich, Micali 및 Wigderson의 작업에서 나온 언어에 대한 완전 영지식 증명 프로토콜의 예를 들어 보겠습니다. 입력 단어는 한 쌍의 그래프이고 여기에 다음과 같은 순열이 있는 경우 그래프는 동형이라고 말해지는 모서리 집합의 자연수 집합으로 식별될 수 있는 정점 집합이 있습니다. (그래프 동형 인식 문제로 표시되는) 경우에만 수학 문제, 이에 대해 이 순간다항식 알고리즘은 알려져 있지 않습니다. 반면에, 이 문제가 NP-완전인지 여부는 알 수 없지만 그렇지 않다고 가정할 만한 충분한 이유가 있습니다.
IG 프로토콜
다음 네 단계 사이의 동형이 루프에서 한 번 수행되고, 매번 독립 확률 변수가 사용됩니다.
1. P는 세트에서 무작위 순열을 선택하고 이 그래프를 계산하여 보냅니다.
2. V는 임의의 비트를 선택하여 보냅니다.
3. 만약 V 순열을 보낸다면, 그렇지 않으면 - 순열 o
4. V에 의해 획득된 순열이 두 사이의 동형이 아닌 경우 V는 증명을 중단하고 거부합니다. 그렇지 않으면 프로토콜 실행이 계속됩니다.
4단계의 검사에서 모든 주기에서 긍정적인 결과가 나오면 V는 증명을 수락합니다.
IG 프로토콜에서 기계가 추가 입력 단어로 동형을 수신하는 경우 프로토콜을 실행하는 데 무제한 컴퓨팅 리소스가 필요하지 않습니다. 게다가 이 경우에는 다항식 확률론적 튜링 머신이 있을 수 있습니다.
정리 2 (). IG 프로토콜은 GRAPH ISOMORPHISM 언어에 대한 절대적인 영지식 증명입니다.
IG 프로토콜의 완전성은 분명합니다.
정확성을 증명하려면 V가 2단계에서 선택하는 비트 a가 그래프 중 어느 것인지를 나타내거나 그래프와 동형성을 입증하는 데 필요하다는 점을 알아두는 것만으로도 충분합니다. 동형이 아닌 경우 기껏해야 동형일 수 있습니다. 그들 중 한 명에게. 따라서 4단계를 확인하면 한 주기에서는 확률이 1/2이고 모든 주기에서는 확률이 긍정적인 결과가 나옵니다.
영지식 속성을 증명하는 것은 훨씬 더 어렵습니다. 따라서 우리는 주요 아이디어만을 재현합니다. 우선, 기계 V의 주요 임무는 사이의 동형사상에 대해 가능한 최대 정보를 얻는 것입니다. V와 달리 V와는 달리 1비트가 아닌 모든 정보를 출력 워드로 생성한다고 가정하는 것이 당연합니다. IG 프로토콜의 1단계와 3단계에서 각각 얻은 랜덤 테이프, 그래프, 순열의 내용을 포함하여 프로토콜을 실행한 결과 얻은 것입니다. 모델링 기계는 동형사상을 알지 못한 채 동일한 무작위 문자열, 그래프 및 순열을 구성할 수 있어야 하므로 2단계에서 기계 V의 요청이 될 비트 a를 추측하려고 시도합니다. 무작위 비트, 무작위 순열을 계산하고 이를 계산합니다. 그런 다음 기계 V의 상태(무작위 테이프의 내용 포함)를 기억하고 이를 서브루틴으로 호출하여 입력으로 그래프를 제공합니다. 기계 V의 응답은 약간의 비트가 될 것입니다. ㅏ. 그러면 이 주기의 시뮬레이션은 필요한 동형성을 보여줄 수 있으므로 성공적으로 완료됩니다. If and는 이전에 저장된 머신 V의 상태를 복원하고 다시 시도합니다.
영지식 속성의 정의에서 확률 변수의 동등성을 확률 분포가 "거의 다르지 않다"는 요구 사항으로 대체하면 통계적 영지식 증명이라는 또 다른 유형의 증명을 얻게 됩니다.
또 다른 유형은 계산적 영지식 증명입니다. 이 경우 시뮬레이터는 다항식 확률 알고리즘과 구별할 수 없는 확률 분포를 생성해야 합니다(여기서 구별 불가능성은 의사 난수 생성기의 정의와 동일한 방식으로 정의됩니다).
영지식에 대한 세 가지 정의 모두에서 언어에 속하는 단어에 대해서만 모델링 기계의 동작에 조건이 부과된다는 점을 특히 강조하겠습니다.
영지식 증명은 사소하지 않은 수학적 객체로서 관심을 끌 뿐만 아니라 실제 응용과 관련하여 연구됩니다. 이러한 애플리케이션의 가장 자연스럽고 중요한 유형은 인증 프로토콜입니다(3장 참조). 이러한 프로토콜의 도움으로 Alice는 Bob에게 자신의 진정성을 증명할 수 있습니다.
예를 들어 앨리스가 지능적인 사람이라고 가정하자. 은행 카드, 알고리즘이 구현되고 Bob은 프로그램을 실행하는 은행 컴퓨터입니다. 은행 업무를 시작하기 전에 은행은 카드의 진위를 확인하고 소유자를 식별해야 합니다. 또는 암호화 언어로 카드를 인증해야 합니다. 원칙적으로 위의 IG 프로토콜을 이러한 목적으로 사용할 수 있습니다. 이 경우, 뱅킹 컴퓨터의 메모리에는 앨리스와 연관된 한 쌍의 그래프가 저장되고, 스마트 카드에도 동일한 그래프 쌍과 동형이 저장되는데, 앨리스 외에는 누구도 이 동형을 알지 못한다고 가정한다(단, 아마도 Bob) 따라서 IG 프로토콜을 사용하여 카드가 진품임을 증명합니다. 더욱이, 완전성이란 카드가 진위임을 확실하게 증명한다는 것을 의미합니다. 정확성 속성은 은행 고객이 아닌 가짜 카드를 사용하여 인증을 시도하는 공격자로부터 은행의 이익을 보호합니다. 영지식 속성은 카드 인증 프로토콜의 실행을 한 번 이상 엿본 후 Alice로 인증을 시도하는 공격자로부터 클라이언트를 보호합니다. 물론 이 경우 그래프 쌍이 GRAP ISOMORPHISM 언어에 속한다는 것을 증명하는 것은 의미가 없습니다. 왜냐하면 해당 그래프는 분명히 이 언어에서 선택되었기 때문입니다. 대신 Alice는 자신이 동형론을 알고 있음을 증명합니다. 이러한 유형의 대화형 증명을 지식 증명이라고 합니다.
을 위한 실용적인 응용 프로그램 IG 프로토콜과 다른 지식 증명 프로토콜의 매우 중요한 속성은 알고리즘이 다음과 같이 수신된다는 것입니다. 추가 입력동형은 다항식 시간으로 실행됩니다. IG 프로토콜 대신 일반적으로 알고리즘에 이 속성이 있는 다른 영지식 증명을 사용할 수 있습니다. 이 아니라면 실제 응용대부분의 유사한 프로토콜과 마찬가지로 IG 프로토콜은 비효율적입니다. 많은 수의루프, 너무 긴 메시지 등. 더욱 효율적이고 안전하다고 입증된 프로토콜을 찾는 것이 이 분야의 주요 연구 분야 중 하나입니다.
대화형 증명 시스템(P,V,S)을 제시해 보겠습니다.
대화형 증명 시스템의 정의에서는 이전에는 V가 적이 될 수 있다고 가정하지 않았습니다.(부정직한 참가자 P가 존재할 가능성만 가정했습니다.) 그러나 V는 알고 싶어하는 적대자로 판명될 수 있습니다. P로부터 새로운 정보를 얻었습니다. 유용한 정보 S의 진술에 대해. 이 경우 P는 작업의 결과로 이런 일이 발생하는 것을 원하지 않을 수 있습니다.
대화형 증거 시스템 프로토콜. 그래서
28 Zapechnikov S. V. 암호화 프로토콜 및 그 전신
이런 식으로 우리는 영지식 증명 프로토콜에 대한 아이디어를 얻었습니다. 영지식 지식은 대화형 증명 시스템 프로토콜의 결과로 V가 진술 S에 대한 지식을 늘리지 않을 것임을 의미합니다. 즉, S가 참인 이유에 대한 정보를 추출할 수 없습니다.
이전과 마찬가지로 프로토콜은 특정 명령문 S를 미리 공식화합니다. 예를 들어 일부 개체 w가 속성 L을 갖는다는 것입니다. 즉, 우리는 L입니다. 프로토콜 중에 P와 V는 메시지를 교환합니다. 그들 각각은 난수를 생성하여 계산에 사용할 수 있습니다. 프로토콜이 끝나면 V는 S가 참인지 거짓인지 최종 결정을 내려야 합니다.
P의 목표는 실제로 사실인지 아닌지에 관계없이 항상 S가 사실이라고 V를 설득하는 것입니다. 즉, P는 적극적인 반대자일 수 있으며, V의 임무는 P의 주장을 테스트하는 것입니다. 참가자 V의 목표는 S가 사실인지 판단하는 것입니다. 참 또는 거짓입니다. 이전과 마찬가지로 V는 다항식으로 제한된 계산 능력을 가지고 있습니다. 즉, V의 작동 시간은 다음의 일부 다항식에 의해 제한됩니다.
증명할 진술의 길이: 이제 영지식 지식이 있는 증명 프로토콜의 예를 고려해 보겠습니다.
1. “알리바바 동굴의 문제.” 동굴이 있는데 그 계획은 그림 1에 나와 있습니다. 1.2. 동굴에는 C 지점과 D 지점 사이에 비밀이 있는 문이 있습니다. 마법의 단어를 아는 사람은 누구나 이 문을 열고 C에서 D로 또는 그 반대로 갈 수 있습니다. 다른 모든 사람들에게는 두 동굴 통로 모두 막다른 골목으로 이어집니다.
R에게 동굴의 비밀을 알려주세요. 그는 마법의 단어를 누설하지 않고 이 비밀에 대한 자신의 지식을 V에게 증명하고 싶어합니다. 통신 프로토콜은 다음과 같습니다.
V는 A점에 있습니다.
P는 동굴에 들어가 C지점이나 D지점에 도착합니다.
P가 동굴 속으로 사라진 후, V는 P가 어느 방향으로 갔는지 알지 못한 채 B 지점에 도착합니다.
V는 R에게 전화를 걸어 V의 희망에 따라 동굴의 왼쪽이나 오른쪽 복도로 나오라고 요청합니다.
R은 필요한 경우 문을 열어서 이 작업을 수행합니다. 물론 그가 마법의 단어를 알고 있다면;
P와 V는 단계 (1) - (5)를 n번 반복합니다.
n번의 프로토콜 라운드 후에는 확률이 1/2"로 감소합니다.
2. 그래프 동형성 증명. P는 그래프 Go 및 Gb Let G, = (p(G0):G0 = G의 V 동형성을 증명하려고 합니다. 여기서 Φ는 동형 변환이고 m은 그래프 정점 N 세트의 카디널리티입니다. 표 1.4는 다음과 같습니다. 이 진술을 증명하기 위한 프로토콜입니다.
이 프로토콜의 구조를 설명하겠습니다. 단계 (1)에서 참가자 P는 G\와 동형인 무작위 그래프 H를 생성합니다. 단계 (2)에서 참가자 V는 임의의 비트 a = (0D)를 선택하여 다음을 증명하도록 요청합니다.
Н ~G0 또는 Н « Gj. 단계 (3)에서 참가자 P는 참가자 V에게 변환 \|/을 보냅니다. 이는 a = 1에 대해 이 변환을 그래프 Gu에 적용한 결과 그래프 F1 = TtG, = H가 되는 방식으로 구성됩니다. a = 0에 대해 이 변환을 그래프 Ga에 적용한 결과 그래프 F0 =를 얻습니다.
Zo Zapechnikov S.V. 암호화 프로토콜 및 해당 응용
= 7i((p(G0))~7iG] = #, (4)단계에서 참가자 V는 그래프 동일성 검사를 수행하여 조건을 만족하는지 판단한다.
N = 파. (1) - (4) 단계가 t회 반복됩니다. 이 프로토콜의 모든 m 라운드에서 테스트 결과가 긍정적이면 V는 증거를 수락합니다.
표 1.4. 그래프 P V 1%의 동형성을 증명하기 위한 프로토콜 - 정점의 무작위 순열, H = nG1 2 f n을 계산합니다. (a -1),
V = 1 / h 1 l of f if (a = 0) -> m times 4 그래프 \j/Ga를 계산하고 비교합니다: H =\jfGa 5 Vm에 대한 경우에만 증명을 받아들입니다.
이 프로토콜은 실제로 영지식 프로토콜입니다. 왜냐하면 동형 G0 ~ Gx의 경우 참가자 V는 그래프 G0 및 G\의 동형을 제외한 어떤 정보도 수신하지 않으며 무작위로 번호를 다시 매길 수 있기 때문입니다. , 임의의 비트 a를 선택하고 그래프 Ga의 번호를 무작위로 다시 매깁니다.
3. 숫자 X의 이산 로그 x에 대한 지식 증명. 프로토콜을 시작하기 전에 공개 수량은 다음과 같이 지정됩니다.
q - q\(p -1), 요소 g e Z*, 숫자 X와 같은 소수. Do-]. 기본 암호화 프로토콜 31
P에게 전화를 건 사람은 비밀 값 x\xTable 1.5를 알고 있습니다. 이산 로그 P V I r&RZ에 대한 지식을 증명하기 위한 프로토콜
M = g(mod p) 2 A. 기초에서 숫자 y 표현에 대한 지식 증명(y 표현에 대한 지식에 대한 영지식 증명). 프로토콜이 시작되기 전에 모든 참가자에게 알려진 공개 수량(소수 p, q, 요소 y, gvg2,..., gk Є Gq)이 지정됩니다. 증명자 P는 비밀량 ara 2,...,ake ZQ를 알고 있습니다: y =
= 8i" " 8r1""> 그는 이러한 수량 자체를 공개하지 않고 V에게 증명해야 하는 지식입니다. 프로토콜은 표에 나와 있습니다. 1.6.
표 1.6. 표현 지식 증명 프로토콜
기본 숫자 P V 1 rl.r2,...,rk. ЄІ( Zq, 2 5. 해당 베이스에서 숫자 집합의 표현에 대한 지식 증명(각 베이스에서 모든 y(j)의 표현 동일성에 대한 지식에 대한 영지식 증명). 프로토콜이 시작되기 전에, 공개 수량은 지정되어 있으며 알려져 있습니다.
여 >\
모든 참가자에게 알려짐: 소수 p, q, 요소 y, 일부(/)에 대한 82^nt. 증명자 P는 비밀값 0C[,a2,...,a,. ψ Zq, V/ у^ =
= (і^) " 1 > 그가 V를 증명해야 하는 지식,
이러한 가치 자체를 공개하지 않고. 테이블에 1.7은 이 문제를 해결하는 프로토콜을 보여줍니다.
표 1.7. 숫자 집합에 대한 지식을 증명하기 위한 프로토콜
해당 염기에서 U/ 2에 대한 P V 1 rvr21...lrkeR(AiP
d는 h = gd인 알 수 없는 요소입니다. 프로토콜이 시작되기 전에 공개 수량(소수 p, q, 요소 A, B, C Є Gq)이 지정됩니다. P의 증명자는 비밀 수량을 알고 있습니다.
a, a, b, b, c, c, c = ab, A = gah"\ B = gbhb, C = gche. 그는 값 자체를 공개하지 않고 V에 대한 지식을 증명해야 합니다. 표 1.8 , with - 그러한 증거에 대한 프로토콜이 유지되었습니다.
표 1.8. 입금된 수량의 곱셈 관계에 대한 지식을 증명하기 위한 프로토콜 P V 1 М=і">/Ї, j Mt = gx-h*\ ¦ M2= Bx ¦ h"1 2 =CK-M2
지식의 공개
표 1.9. PS가 0인 증명 프로토콜의 구조: x œ L- 증명할 진술, h - dp, 공개 매개변수 및 수량, s - S가 참인 이유에 대한 증명자의 비밀 데이터, r- 난수 V 1 rp - 무작위, 2 rv - 무작위 숫자,
c = LM 고려된 예를 일반화하고 여러 정의를 공식화해 보겠습니다. 안에 일반적인 견해영지식 지식을 사용한 대화형 증명 프로토콜(표 1.9)은 4단계로 구성됩니다.
테이블 끝. 1.9 P S: xe L은 증명되는 진술, h는 공개적으로 사용 가능한 기타 매개변수 및 양, s는 S가 참인 이유에 대한 증명자의 비밀 데이터, r은 난수 V 3 R = f3(C,x) 4
증명자는 소위 증거(증인 -W)를 검증자에게 전달합니다. 이는 그가 증명한 지식인 비밀 값의 일방향 함수를 계산한 결과입니다.
리뷰어는 그에게 무작위로 요청을 보냅니다.
증명자는 이 질문에 대답하고 대답은 무작위 쿼리와 비밀 값에 따라 달라지지만 그에게서 이 비밀 값을 얻는 것은 계산상 불가능합니다.
답변을 받은 V는 첫 번째 단계에서 전송된 '증거'와의 일관성을 확인합니다.
영지식 공개로 증명을 구성하는 기본 원칙, 즉 영지식 지식의 속성이 의미하는 바를 고려해 보겠습니다.
영지식 증명 이론에서 지식 P와 V는 "블랙박스"로 취급됩니다(그림 1.3).
\tr ), \)Py )를 P에서 V로(각각 V에서 P로) 전송된 모든 메시지의 집합이라고 가정합니다. 각 메시지는 무작위 변수이므로 (x,h,rv,(mp),( mv)) = = 뷰피)
