해시넷
영지식증명 편집하기
편집을 되돌릴 수 있습니다.
이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 저장해주세요.
| 최신판 | 당신의 편집 | ||
| 41번째 줄: | 41번째 줄: | ||
=== 스도쿠 게임 === | === 스도쿠 게임 === | ||
| − | 영지식증명은 [[스도쿠]](sudoku) 게임에도 적용될 수 있다. 스도쿠 게임(sudoku game)은 정사각형 모양의 보드에 1~9까지 숫자를 넣되, 총 9*9=81개의 칸에 대해, 반드시 하나의 가로줄에 1~9의 숫자를 각각 한 번씩 사용해야 하고, 하나의 세로줄에 대해서도 1~9까지 숫자를 각각 한 번씩 사용해야 하며, 3*3 크기의 작은 정사각형 보드 안에도 1~9까지의 숫자가 오직 한 번만 사용되도록 만드는 게임이다. 이 게임의 정답을 | + | 영지식증명은 [[스도쿠]](sudoku) 게임에도 적용될 수 있다. 스도쿠 게임(sudoku game)은 정사각형 모양의 보드에 1~9까지 숫자를 넣되, 총 9*9=81개의 칸에 대해, 반드시 하나의 가로줄에 1~9의 숫자를 각각 한 번씩 사용해야 하고, 하나의 세로줄에 대해서도 1~9까지 숫자를 각각 한 번씩 사용해야 하며, 3*3 크기의 작은 정사각형 보드 안에도 1~9까지의 숫자가 오직 한 번만 사용되도록 만드는 게임이다. 이 게임의 정답을 맞춘 사람인 증명자는 자신이 발견한 정답을 검증자에게 공개하지 않으면서도 자신이 정답을 찾았다는 사실을 증명해야 하는데, 이때 영지식증명 방법을 사용할 수 있다. |
# 증명자는 9*9 = 81개의 정사각형 보드를 다른 종이로 덮어서 검증자가 볼 수 없도록 한다. | # 증명자는 9*9 = 81개의 정사각형 보드를 다른 종이로 덮어서 검증자가 볼 수 없도록 한다. | ||
| 48번째 줄: | 48번째 줄: | ||
# 증명자는 검증자가 요청한 특정 부분의 정답을 공개한다. 증명자가 공개한 부분에 1~9의 숫자가 각각 한 번씩만 사용되었다면, 증명자가 스도쿠 문제의 정답을 알고 있다는 증명이 된다. | # 증명자는 검증자가 요청한 특정 부분의 정답을 공개한다. 증명자가 공개한 부분에 1~9의 숫자가 각각 한 번씩만 사용되었다면, 증명자가 스도쿠 문제의 정답을 알고 있다는 증명이 된다. | ||
| − | 하지만, 위 과정을 오직 한 번만 수행할 경우, 증명자가 우연히 해당 줄의 정답을 | + | 하지만, 위 과정을 오직 한 번만 수행할 경우, 증명자가 우연히 해당 줄의 정답을 맞춘 것일 수도 있기 때문에, 검증자는 전적으로 증명자를 신뢰할 수 없다. 따라서 위 과정은 여러 회 반복해서 수행되어야 한다. 두번째 과정에서 증명자는 다시 자신이 알고 있는 정답의 숫자를 랜덤하게 1:1로 바꿔치기한다. 만약 이러한 셔플링 과정을 수행하지 않는다면, 검증자가 증명자가 알아낸 정답을 추측할 수 있기 때문에 증명자는 매번 이러한 셔플링을 수행해야 한다. 결국 위 과정을 상당히 여러 회 반복하였음에도 불구하고, 증명자가 매번 정답을 맞춘다면, 검증자는 증명자가 정답을 알고 있을 확률이 매우 높다고 결론을 내릴 수 있다. 이처럼 영지식증명 방법을 이용해 증명자는 자신이 찾아낸 스도쿠 게임의 정답을 공개하지 않고도 검증자에게 자신이 정답을 알고 있다는 사실을 증명할 수 있게 된다. |
이 실험에서 증명자는 오직 검증자에게만 자신이 정답을 안다는 사실을 증명할 수 있다. 이 실험을 관찰하는 다른 제3자들은 증명자가 정말로 정답을 알고 있는지 확신할 수가 없다. 왜냐하면 제3의 관찰자는 증명자와 검증자가 사전에 미리 짜고 그 순서대로 특정 줄의 값만 1~9가 되도록 조작했을 수도 있기 때문이다. 하지만 검증자는 자신이 정말로 랜덤하게 특정 가로줄이나 세로줄을 지정했다는 사실을 알고 있기 때문에, 증명자가 정답을 알고 있다고 확신할 수 있게 된다. 이처럼 영지식증명을 이용하면, 오직 해당 증명 과정에 참여한 증명자와 검증자만 사실을 확신할 수 있으며, 제3자의 관찰자는 증명자가 정말로 해당 내용을 알고 있는지 확신할 수 없다. | 이 실험에서 증명자는 오직 검증자에게만 자신이 정답을 안다는 사실을 증명할 수 있다. 이 실험을 관찰하는 다른 제3자들은 증명자가 정말로 정답을 알고 있는지 확신할 수가 없다. 왜냐하면 제3의 관찰자는 증명자와 검증자가 사전에 미리 짜고 그 순서대로 특정 줄의 값만 1~9가 되도록 조작했을 수도 있기 때문이다. 하지만 검증자는 자신이 정말로 랜덤하게 특정 가로줄이나 세로줄을 지정했다는 사실을 알고 있기 때문에, 증명자가 정답을 알고 있다고 확신할 수 있게 된다. 이처럼 영지식증명을 이용하면, 오직 해당 증명 과정에 참여한 증명자와 검증자만 사실을 확신할 수 있으며, 제3자의 관찰자는 증명자가 정말로 해당 내용을 알고 있는지 확신할 수 없다. | ||
