Tag Info

New answers tagged

1

The initial idea of Fiat and Shamir was to eliminate the interaction in public coin protocols (note that public coin means that the random choices of the verifier are made public) and was used to convert three move public coin identification scheme into conceptually simple signature schemes (it has later been proven by Pointcheval and Stern that under the ...


0

To answer your question (ignoring for a moment the inaccuracy of the definition), if am understanding you correctly you are wondering if $p \leq \kappa(|x|)$ how can there exist a $q(|x|)$ so that $K$ outputs a witness with probability $\frac{p - \kappa(|x|)}{q(|x|)}$ (because in this case the probability might be negative). I will try to explain this. ...


0

How can I be sure that the prover actually has a three-coloring? Prover responds with colors of just one single edge chosen by Verifier. In case he has valid coloring, his response is consistent with commitments with probability $1$; if not - he errs with a small probability, as answered by tylo. I'm writing this to stress that Prover is given an ...


2

I assume you are familiar with $P$ and $NP$. Also, my knowledge of SNARKs is based mostly on the work of Parno et al., other work may differ in some fine details. So, a SNARK is a succinct non-interactive argument of knowledge. Leaving the "knowledge" part aside for the moment, let's look at "plain" succinct non-interactive arguments (called SNARGs in the ...


0

Yes they are applicable to groups other than elliptic curves with bilinear pairing, if that's what you mean with "groups which induces Bilinear map". Consider for example the group $\mathbb{Z}_q$. They DO have a bilinear operation, namely $f: \mathbb{Z}_q \times \mathbb{Z}_q \to \mathbb{Z}_q$ s.t. $f(x,y)=xy$.


0

An interactive proof system, including one with zero knowledge property (a zero-knowledge proof) is to recognize a language. That is, to decide whether an input belongs to a subset or the whole set (universe). Proof of knowledge is an interactive system with a knowledge extractor algorithm. Now consider Pedersen commitments, where any group element could be ...


1

U-Prove TokenID is a hash output, so it may be not the best way to prove "not the same" statement. One would also consider inequality proof for a subset of user attributes instead. For each such attribute pair, "not the same" would mean an inverse exists for attribute difference, modulo group order. One would prove knowledge of such inverses while keeping ...


1

To prove that product holds over integers, one would start from commitments with groups of a hidden order. That is, proving party should not know order of the group, which is the case with RSA-like multiplicative group. Consider Prover responses $\rho_x = tx + \alpha_x$, $\rho_y = ty + \alpha_y$, $\rho_z = tz + \alpha_z$ to Verifier challenge $t$ with ...



Top 50 recent answers are included