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 ...
Wilson's user avatar
  • 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-...
Geoffroy Couteau's user avatar
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 ...
Wilson's user avatar
  • 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 ...
Daniel S's user avatar
  • 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 ...
Richard Thiessen's user avatar
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 ...
Daniel S's user avatar
  • 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 ...
Richard Thiessen's user avatar
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 ...
knaccc's user avatar
  • 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 ...
Wilson's user avatar
  • 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)...
Wilson's user avatar
  • 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 ...
user93353's user avatar
  • 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$....
lamontap's user avatar
  • 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,<...
Richard Thiessen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible