[2021/05/08][짤막한 이야기 - 영지식증명(한계)]

[2021/05/08][짤막한 이야기 - 영지식증명(한계)]
“영지식증명”은 증명자가 지식을 보여주기 위한 최고의 수단이다.
왜냐하면 증명자의 지식을 제시하면서도 그 외의 정보는 아무것도 노출하지 않기 때문이다.
그러나 영지식증명에는 한계점이 있다.
앞선 예시(너무 오래전에 포스팅했지만..)를 다시 한번 생각해보자.
(잘 기억나지 않는다면 이전 게시글을 확인하고 오는 것이 좋다.)
동굴의 마법의 주문을 알고 있음을 증명하기 위해서는 검증자가 원하는 방향으로 나와야 한다.
즉, 검증자와 한번은 대화를 해야하는 것이다.
그러나 한번만으로는 50% 확률로 검증에 통과할 수 있기 때문에 불충분하다.
그렇다고 검증자가 원했던 10번을 다 통과하면 증명자는 정말 비밀정보(마법의 주문)를 알고 있는 것일까?
즉, 대화의 횟수는 충분히 많아야 안전하다고 보는 것이 기본적인 영지식증명의 한계점이다.
더 정확히는 N번의 대화가 있을 때 1/(2^N)의 확률로 영지식증명을 깰 수 있다는 것이다.
이러한 “대화형 영지식 증명”을 “Interactive Zero-Knowledge Proof System”이라고 한다.
이의 한계점을 해결하기 위해서라도 “비대화형 증명”에 대한 개념을 알아야 한다.
#이야기 #루니프 #영지식증명 #대화형

[2021/05/08][Short Story - Zero-Knowledge Proof(Limitation)]
“Zero-Knowledge Proof” is the best means for the prover to demonstrate his knowledge.
This is because while presenting the prover's knowledge, no other information is exposed.
However, there is a limitation of zero-knowledge proof.
Consider the previous example(I posted it too long ago, but...).
(If you don't remember well, it's a good idea to check the previous post.)
To prove that the prover knows the magic spell of the cave, the verifier must come out in the desired direction.
In other words, the prover has to talk to the verifier at least once.
However, it is insufficient because it can pass verification with a 50% probability of passing once.
But if the prover passes the 10 times the verifier wanted, does the prover really know the secret information (magic spell)?
In other words, the limitation of basic zero-knowledge proof is that the number of conversations must be sufficiently large to be considered safe.
More precisely, when there are N interactions, the zero-knowledge proof can be broken with a probability of 1/(2^N).
This is called the “Interactive Zero-Knowledge Proof System”.
To solve its limitations, you need to know the concept of “Non-Interactive Proof”.
#Story #LootNiP #ZeroKnowledgeProof #Interactive