[2021/08/10][짤막한 이야기 - 영지식증명(응용)]

[2021/08/10][짤막한 이야기 - 영지식증명(응용)]
“영지식증명”은 대화형(Interactive) 성질을 가지고 있으며, 이에 따라 많은 대화를 교환해야함을 한계점으로 지적한 바 있다(너무 오래전에 포스팅했지만..).
영지식증명에 "비대화형(Non-Interactive)" 성질을 추가하여야 한 쪽("증명자" 혹은 "검증자")의 연결이 끊어져도 증명 프로토콜의 수행이 가능하다.
”앨리스(Alice)”가 “밥(Bob)”에게 Y(=G^X)에서의 X값을 알고 있음을 증명하고 싶다.
1) 앨리스는 T (=G^V, V는 랜덤값)를 밥에게 송신한다.
2) 밥은 앨리스에게 랜덤값 C를 송신한다.
3) 앨리스는 C를 이용하여 R (=V-C*X)을 계산하여 밥에게 회신한다.
4) 밥은 T가 (G^R)*(Y^C)와 같은지 검증한다. 다를 경우 앨리스는 증명에 실패한다.
5) 이 과정에서 밥은 X값을 알 수 없기 때문에 영지식성을 만족하지만, 앨리스가 X를 정확히 알고 있음을 검증할 수 있다.
비대화형 영지식증명이라면 증명자는 검증자가 오프라인인 상태에서도 증명증거를 생성할 수 있어야 한다.
즉, 위 예시의 프로토콜을 밥 뿐만 아니라 임의의 검증자가 검증할 수 있도록 변형하여야 한다.
2번 과정의 C를 어떻게든 생략하면 될 것 같아 보인다. 어떻게 하면 될까?
[관련된 짤막한 이야기 - 영지식증명(한계)[2021/05/08]]
#이야기 #루니프 #암호학 #영지식증명 #대화형 #비대화형

[2021/08/10] [Short Story - Zero-Knowledge Proof(Application)]
"Zero-Knowledge Proof" has an interactive property and has been pointed out as a limitation that many messages need to be exchanged accordingly (Although I posted it too long ago...).
"Non-Interactive" property must be added to the demonstration of zero-knowledge to enable the performance of the demonstration protocol even if one side ("Prover" or "Verifier") is disconnected.
Alice would like to prove to Bob that Alice knows the X value in Y (=G^X).
1) Alice sends T (=G^V, V is a random value) to Bob.
2) Bob sends a random value of C to Alice.
3) Alice calculates R (=V-C*X) using C and returns to Bob.
4) Bob verifies whether T is the same as (G^R)*(Y^C). If not the same, Alice fails to prove.
5) In this process, the zero-knowledge property is satisfied because Bob does not know the value of X, but Bob can verify that Alice knows X exactly.
If it is non-interactive zero-knowledge proof, the prover should be able to generate proof even when the verifier is offline.
In other words, the protocols in the examples above should be modified so that proof can be verified by any verifiers as well as Bob.
It seems that we can somehow omit C from Step 2. What should we do?
[Related Short Story - Zero-Knowledge Proof(Limitation)[2021/05/08]]
#Story #LootNiP #Cryptography #ZeroKnowledgeProof #Interactive #NonInteractive