제로 지식 증명 2 부 : 비 대화식 제로 지식 증명

제로 지식 증명 시리즈의 1 부에서 검증 자와 프로 버가 서로 상호 작용할 때 제로 지식 증명이 어떻게 작동하는지 설명했습니다..

대화식 제로 지식 증명은 검증 자만이 지식이 있다는 것을 절대적으로 확신 할 수 있다는 이점이 있습니다. 그러나 이것은 또한 단점이 될 수 있습니다.

방관자와 관찰자가 주장을 확인할 수없는 경우, 검증자는 모든 검증 자와 독립적으로 상호 작용해야합니다. 시간이 걸리고 리소스를 많이 사용합니다.

2 부에서는 비 대화식 제로 지식 증명을 살펴 보겠습니다..

비 대화식 제로 지식 증명

비 대화식 제로 지식 증명의 이유는 많은 수의 관찰자가 증명을 효율적으로 검증 할 수 있도록하기 위해서입니다..

제로 지식 증명을 비 대화식으로 만들 필요는 없습니다. 종종 증거의 무결성을 보증하는 신뢰할 수있는 검증자를 찾을 수 있습니다..

비 대화식 제로 지식 증명 예 : 스도쿠 및 카드 놀이

스도쿠는 다양한 난이도가 있지만 비교적 간단한 규칙을 가진 게임입니다. 9 개의 행, 9 개의 열 및 9 개의 섹터 (굵은 검은 선으로 표시)는 각각 1에서 9까지의 각 숫자를 정확히 한 번 포함해야합니다..

스도쿠 퍼즐에 대한 솔루션은 특히 얻기가 어렵고 슈퍼 컴퓨터조차도 계산하는 데 며칠이 걸린다고 상상해보십시오.

그러나 누군가 (발표자)는 퍼즐에 대한 해결책을 가지고 있다고 주장하고 그것을 기꺼이 팔려고합니다. 검증자가 솔루션을 공개하지 않고도 솔루션을 보유하고 있음을 어떻게 입증 할 수 있는지 확인하는 방법?

증거:

증명 인은 총 1-9 – 243의 27 장의 카드를 필요로합니다..

이제 프로 버는 모든 상자에 올바른 스도쿠 솔루션에 해당하는 번호의 카드 3 장을 넣습니다. 예를 들어, 박스에 대한 정답이 7이면, 프로 버는 7의 값을 가진 3 장의 카드를 넣습니다..

스도쿠 테이블에는 일부 답변이 표시됩니다. 이 답 상자에 카드 놀이가 배치됩니다 위로 향. 비어있는 스도쿠 상자에 카드가 배치됩니다 아래로.

페이스 다운 카드가 모두 올바른 위치에 있음을 증명하기 위해 (해결 방법을 밝히지 않고) 증명자는 다음을 수행해야합니다.

• 모든 곳에서 최고의 카드를 가져 가라 열 그리고 9 개의 더미를 만드십시오
• 모든 곳에서 최고의 카드를 가져 가라 기둥 그리고 9 개의 더미를 만드십시오
• 남은 카드를 모두 가져 가십시오 부문 그리고 9 개의 더미를 만드십시오

그런 다음 각 파일을 섞고 뒤집습니다..

1-9 사이의 모든 숫자는 모든 스도쿠 행, 열 및 섹터에 표시되어야합니다. 따라서 행, 열 및 섹터 파일에서 프로 버 카드의 모든 파일에 1-9라는 각 카드가 포함 된 경우 솔루션이 있어야한다는 것을 알고 있습니다..

제로 지식 증명을위한 응용 프로그램

물론, 비교적 젊은 영 지식 증명 분야는 아직 그럴만한 가치가 있다는 것을 인정하지 못했습니다. 그러나 그들은 매우 귀중한 것으로 판명 될 수 있습니다.

많은 수학 문제는 스도쿠 퍼즐과 유사합니다 (예 : 그래프 채색 문제). 위의 원리를 사용하여 다양한 문제에 성공적으로 적용 할 수 있다면 계산 리소스와 수학 문제를보다 효율적으로 사용하고 교환 할 수 있습니다. 또는 수학적인 문제를 더 빨리 해결.

Ronen Gradwohl, Moni Naor, Benny Pinkas 및 Guy Rothblum에게 추천