History of ZKP
创始人
2024-11-15 02:33:20
0

History of ZKP

Let’s start with classical proofs. So when we think of a classical proof, we think about these various esteemed provers, Gauss, Euclid, Emmy Noether, Alan Turing, and our own, Steve Cook. And we think about theorems, the kind of theorems that you learn perhaps in geometry in class where there’s a bunch of axioms, there’s a claim that you’re trying to prove or theorem,you make a sequence of derivations from the axioms and then eventually you declare the theorem as proved. It could be the prime number theorem, the Pythagorean theorem, and so forth. But today, we’re going to think of proofas an interactive process where there is the prover. But maybe more importantly for our study, there is a verifier. So there is an explicit referenceto whoever it is that’s reading the proof and verifying it is correct. And we think about this as follows. There’s a claim, which is an input to both prover and the verifier. Both of the prover and the verifier are actually algorithms. And the prover sends a string, which we will refer to in this slide as a proof. The verifier reads this. So if you would like to think about that geometric proof, verifier is the teacher reading your proof and at the end accepting is it correct or reject. Accepting the claim as being proved or not. In fact in computer science, we often talk about efficiently verifiable proofs or NP proofs. And those are proofs where the string that the prover sends to the verifier is short. And the verifier, in addition, doesn’t have all the time in the world to read it, he has polynomial time. Now to be more explicit, what does it mean by short? What do we mean by polynomial? What we mean is that the string that the prover sends to the verifier is of size polynomial in the length of the claim. So we think about the claim as string x, binary string. The message here is string, binary string w, the length of w is polynomial in the length of x.

Claim: N is a product of 2 large primes

proof = {p, q}
If N = pq, V accepts
Else V rejects

After interaction, V knows:

  1. N is product of 2 primes
  2. The two primes p and q

Claim: y is a quadratic residue mod N
i.e
∃ x ∈ Z n ∗ s . t . y = x 2 m o d N \exist x \in Z^*_n s.t. y = x^2 mod N ∃x∈Zn∗​s.t.y=x2modN

Proof = x
If y = x^2 mod N, V accepts
Else V rejects

After interaction, V knows:

  1. y is a quadratic residue mod
  2. Square root of y(hard problem equivalent to factoring N)

相关内容

热门资讯

专业讨论!德扑之星真破解套路(... 专业讨论!德扑之星真破解套路(辅助挂)软件透明挂(有挂了解)-哔哩哔哩;人气非常高,ai更新快且高清...
每日必看!智星德州菠萝外挂检测... 每日必看!智星德州菠萝外挂检测(辅助挂)软件透明挂(有挂教学)-哔哩哔哩1、玩家可以在智星德州菠萝外...
透视透明挂!轰趴十三水有后台(... 轰趴十三水有后台赢率提升策略‌;透视透明挂!轰趴十三水有后台(辅助挂)软件透明挂(有挂详情)-哔哩哔...
发现玩家!德扑ai助手软件(辅... 发现玩家!德扑ai助手软件(辅助挂)透视辅助(有挂教学)-哔哩哔哩;玩家在德扑ai助手软件中需先进行...
一分钟了解!x-poker辅助... 一分钟了解!x-poker辅助软件(辅助挂)辅助透视(有挂攻略)-哔哩哔哩1、每一步都需要思考,不同...
一分钟揭秘!德州最新辅助器(辅... 一分钟揭秘!德州最新辅助器(辅助挂)透视辅助(有挂攻略)-哔哩哔哩;德州最新辅助器最新版本免费下载安...
玩家攻略推荐!德州辅助(辅助挂... 玩家攻略推荐!德州辅助(辅助挂)辅助透视(有挂了解)-哔哩哔哩是由北京得德州辅助黑科技有限公司精心研...
揭秘真相!pokernow德州... 《揭秘真相!pokernow德州(辅助挂)辅助透视(有挂介绍)-哔哩哔哩》 pokernow德州软件...
五分钟了解!德州之星辅助器(辅... 五分钟了解!德州之星辅助器(辅助挂)辅助透视(有挂透明)-哔哩哔哩1、很好的工具软件,可以解锁游戏的...
推荐一款!pokermaste... 1、推荐一款!pokermaster有外挂(辅助挂)透视辅助(有挂教学)-哔哩哔哩;详细教程。2、p...