5
votes
Division of two Elliptic curve points in KZG polynomial commitment scheme!
In this lecture, they use multiplicative notation for the pairing groups instead of additive notation. Thus, division is well-defined. Division is just the inverse of the group operation.
The choice ...
- 920
4
votes
Accepted
Assumptions on zero-knowledge proofs without trusted setup
Strongly unforgeable digital signatures exist from one-way function, so they are indeed a Minicrypt assumption, even though most efficient construction use public key cryptography.
For succinct zero-...
- 18.6k
3
votes
Accepted
PLONK: Why is the quotient polynomial multiplied by different powers of a challenge?
The quotient challenge is necessary for soundness. In particular, if the prover wants to show that there exists quotients $q_1=f_1/z_H$, $q_2=f_2/z_H$, and $q_2=f_2/z_H$. To do so, it can instead send ...
- 920
3
votes
Accepted
What does preprocessed polynomial mean in the context of PLONK?
Pre-processing means part of the one-time initial set up computation of the system prior to the generation of any proofs. This set-up phase is allowed to use considerably more resources.
If we look to ...
- 20k
3
votes
Accepted
Securely derive multiple EC keys from master EC key and prove it
Alice doesn't have to do anything.
A' = (a+r)*G = a*G + r*G = A + r1*G
Bob can compute these keys himself. That's usually how key diversification works. If he wants ...
- 1,221
3
votes
Accepted
Is the permuation check range in the PLONK Paper incorrect?
The argument in the paper is correct. Verifying (a) confirms that $Z(g)=1$, verifying
$$Z(a)f'(a)=g'(a)Z(a\mathbf g)$$
for $a=\mathbf g,\mathbf g^2,\mathbf g^3\ldots \mathbf g^{n-1}$ then inductively ...
- 20k
3
votes
Verify HMAC tag without knowing the key
There are obviously constructions other than HMAC that work. Public key signing works obviously with Alice sending Bob her public key.
HMAC has no algebraic structure to allow this to work. Zero ...
- 1,221
2
votes
Accepted
Deterministic EC key derivation with anonymity and proofs
Alice has a master private key scalar $a$, with corresponding public key $A=aG$. $G$ is a well-known base point on the curve.
Alice deterministically creates a new identity associated with a ...
- 4,552
2
votes
Accepted
Can a 3-coloring for a graph be represented as a circuit?
The beauty of QAP is that it is NP-Complete. Thus, the 3-coloring problem reduces to QAP. In fact, any problem in NP can be represented using QAP constraints.
More practically, all that is required is ...
- 920
2
votes
Accepted
Question about the PLONK permutation check
The checks a) and b) are done over every element $a\in H$ (Notice the statement "for all $a\in H$"). The product check requires that the verifier check that $Z(g)=1$ (the inductive base case)...
- 920
2
votes
How exactly bilinear pairing multiplication in the exponent of g is used in zk-SNARK polynomial verification step?
A Bilinear Pairing has many properties including
$e(A^\alpha, B) = e(A, B^\alpha) = {e(A, B)}^{\alpha}$ (where $\alpha$ is a scalar)
i.e. you can move the exponent of the left hand side term to the ...
- 2,290
1
vote
Accepted
Fiat-Shamir with interactions
For the Fiat-Shamir transform, HVZK becomes ZK because the verifier sends nothing to the prover. The ZK simulator generates $(a,e,z)$ from the HVZK simulator and reprograms the oracle so that $H(a)=e$....
- 396
1
vote
Accepted
Ensure deniability of an interactive zero knowledge proof
Note:All the math in this answer assumes
prime order finite field with generator G
Capital letters are group elements (EG: P,<...
- 1,221
Only top scored, non community-wiki answers of a minimum length are eligible