New answers tagged

0 votes

Chaum-Pedersen protocol adapted to elliptic curves

After the Fiat–Shamir heuristic is applied, the non-interactive version would be: $Y_1=xG$ and $Y_2=xH$, where $G$ and $H$ are generator points on the curve and $x$ is a scalar. We intend to prove ...
  • 4,367
1 vote

PLONK Product Check Proof. Why is the 2nd condition required?

The correct checks are 1) $t(\omega^{k-1}) = 1$ and 2) $t(\omega\cdot x) - t(x)\cdot f(\omega \cdot x) = 0$ for all $x \in \Omega$ The prover is supplying values in a black box way. The second ...
  • 19.2k
1 vote
Accepted

Looking for the proof of the prod check gadget referred to by Boneh in his PLONK video

maybe the lecture video on youtube can help you to understand: https://youtu.be/LbpPCN-f_XA?t=952 BTW, the equation in the first of 4 slides you don't understand is just stating the hypothesis in the ...
  • 670
2 votes
Accepted

zerocoin ZKSoK Pedersen commitment process

Yes, the value $S$ is public. From the notation on page 5, "All values not enclosed in ()’s are assumed to be known to the verifier." This makes sense in the scheme, since, once a coin is ...
  • 124
1 vote

What is the difference between those two KZG Polynomial Commitment Schemes?

Both represent the same thing. The first one uses the additive notation & the 2nd one uses the multiplicative notation. That is the only difference. KZG actually uses an Elliptic Curve Group, so ...
  • 2,251
2 votes

Textbook RSA security for fully random message

Your description of the algorithm looks a lot like RSA-KEM, which is considered secure. However, note that the (b) argument of the security proof indicates that "the input is independent of the ...
  • 89.2k
1 vote

NIZK Proof of Knowledge of a Standard RSA Signature on a message (without signer participation)

Is the above scheme actually secure i.e., can the Prover construct a $\pi$ which the Verifier will accept without having seen the signature and can the Verifier recover $\sigma$ from $\pi$? No, the ...
  • 139k
3 votes
Accepted

What is the modern terminology for a digital signature scheme with a shadow?

In modern terminology, a digital signature scheme with a shadow is a (digital) signature scheme giving (total) message recovery. The shadow is the message representative. The paper linked in the ...
  • 132k
1 vote

Make sure of Quadratic Arithmetic Program validity

Recall the QAP equivalence condition. If $r_1, \ldots, r_n$ are uniformly chosen elements in the field $\mathbb{F}$, and $\{u_i(X),v_i(X),w_i(X)\}_{i=1}^m$ are all degree $n-1$ polynomials in $\mathbb{...
  • 124
1 vote

How to implement CRS model in the real world?

You are correct: CRS can be realized by a set of trusted parties. To my knowledge, the closest reference to a practical solution to a CRS is the one that Zerocash uses, and that we can read from: ...
2 votes
Accepted

How to compare two field elements in Arithmetic Circuit?

As far as I know, "the bigger one" has no canonical definition in a finite field. At least, there is no total order compatible with addition, that is such that $a\le b$ and $a'\le b'$ ...
  • 132k
3 votes

How to compare two field elements in Arithmetic Circuit?

You have misread my answer here. When converting a boolean circuit into an equivalent arithmetic circuit, you need to (1) Take your inputs over the field and convert them into bitstrings (e.g. through ...
5 votes
Accepted

How can a verifier benefit from being malicious or dishonest in a Zero Knowledge interactive proof?

For many concrete HVZK proof systems, we actually don't have an attack against zero-knowledge when the verifier is dishonest - but we don't have a security proof either! In particular, in many $\Sigma$...
1 vote

Is this Zero Knowledge interactive proof for Quadratic non-residuosity proper?

First, this is not supposed to be a proof of knowledge, so any references to "knowledge" are largely irrelevant. The prover is merely required to convince the verifier that $x$ is in fact a ...
  • 6,476

Top 50 recent answers are included