# Tag Info

7

By Theorem 3 on page 15 of this paper, no secure-with-abort protocol for equality of long strings can be within 1/5 of fair. If there is a protocol for equality on a domain of size at least 3 which is secure against honest-but-curious adversaries, then oblivious transfer protocols exist. If oblivious transfer protocols exist, then there are protocols for ...

4

One could split both secrets into smaller parts, commit to parts and "gradually" open that commitments to each other, so that no party is better than (ahead of the other) one such part. For example, let secret be a big number split into bits. With an additively homomorphic bit commitment scheme, the other party could verify that bit commitments correspond ...

4

This cannot be done. It is provably impossible. In order to explain this in technical terms, what you are looking for is a FAIR protocol to compute equality of long random strings (I added the latter since it adds a constraint and so in theory could make it easier). In any case, if I had such a protocol, then I could toss a fair unbiased coin. Here is the ...

4

Rough scetch, assuming Bob is standing next to you in the same room: Prepare cards with the correct numbers on them Lay down the cards according to the setup, face up Lay down the remaining cards with the correct solution, face down, so that Bob can't see them. Now you let Bob choose one column, row or sector. You pick up the cards in that row, column ...

3

SRP does DH key exchange with authentication, and has the capability to also authenticate the server as well (though usually the server is authenticated by keeping the verifier secret). If the key is generated strictly from a password and salt, with the salt stored on the server, you can do a dictionary attack on the verifier (e.g. if the server is ...

3

Having a client (ex. your web browser) use zero-knowledge proofs to authenticate itself to a server only makes sense if the server knows about the client's public key in advance, and if the client keeps the same private key forever. So you could have the client-side generate a keypair when you register your account, and the server records your public key ...

3

Yes, it is possible. Actually, any statement in NP can be proven in zero knowledge. This means that if something can be proven by releasing some information, it is possible to prove the same without releasing any information, i.e. in zero knowledge.

3

$ax^2+bx+c=0$ is the general expression of a quadratic equation in one variable. Here, there are more than one. You may want to look into how the degree of a multivariate polynomial is defined.

3

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 ...

3

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 ...

3

A zero-knowledge proof is a protocol by which the Prover demonstrate to the Verifier that he knows the solution to a given problem, without giving to the Verifier any additional information about the solution -- that is, no information that the Verifier could not already obtain alone. In the case of the discrete logarithm, the y value is not part of what the ...

3

The motivation, to me, is that in reality you can consider any router on the internet to be successfully executing an "intruder-in-the-middle" attack just by forwarding messages unchanged. After a successful execution of the identification scheme, Bob knows that someone on the channel is Alice, which is all the protocol was hoping to achieve. It was ...

2

Without a sign the verifier learns that the number he received is a QR modulo n. Whether a number is a QR is a hard problem as he does not know the factors of n.

2

In context of interactive proof systems (including zero-knowledge proofs) completeness means the same as the term correctness as used for many other (interactive) cryptographic schemes or protocols. I guess that's mainly due to historical reasons (there are even some people that use correctness instead of completeness in context of zero-knowledge proofs). ...

2

A straightforward way to prove this when you can prove AND as well as OR statements about discrete logarithms is to take all the $K=\binom{M}{N}$ subsets $A_i=\{A_{i_1},\ldots,A_{i_N}\}$ with $N$ elements of points from the set of your $M$ points and prove the statement PK\{(\alpha_1,\ldots,\alpha_N): \bigvee_{j\in K} \big( \bigwedge_{A_{j_i}\in A_j} ...

2

The common reference string in NIZK does not have to be uniformly distributed. It is to be sampled from whatever distribution the NIZK protocol specifies. However, the common random string in NIZK does have to be uniformly distributed, and the setup strings in NIZK also have to be uniformly distributed.

2

I believe a zero knowledge proof that $-1$ is a quadratric nonresidue would accomplish that. If we know that $n$ has two prime factors, and that $n \equiv 1 \pmod{4}$, then $n$ is either a product of two primes both $1 \bmod 4$, or two primes both $3 \bmod 4$. If it were the former, then $-1$ is a QR modulo $p$, and $-1$ is a QR modulo $q$, and hence $-1$ ...

2

This has some issues, with both soundness and zero-knowledge. The issue with zero-knowledge is that an eavesdropper who knows $L$ and overhears legitimate traffic can compromise the secret quite easily. While factoring is hard, taking a GCD is very efficient. That means that given $M=pr$ and $L=pq$, an eavesdropper Eve can efficiently compute $\gcd(M,L)=p$. ...

2

There are two answers. One, go non-interactive with the Fiat-Shamir transform. This requires the Random Oracle Model (ROM) to analyse, but the ROM is standard enough in cryptography and ROM proofs have been used in practice for long enough that this shouldn't worry you. It gets you full ZK, curiously enough for the exact same reason that plain Schnorr is ...

2

Answering the question in your title (and not addressing your proposed alternative which I don't quite understand) there is a zero knowledge proof of password protocol "SRP" which is fast and effective. SRP does not seem to have been given as wide publicity as it should get. Having implemented it, and being an advocate of its use, I don't really understand ...

2

You are on the right track. However, as Ricky Demer points out in the comments, your suggestion would not work because the input is encrypted with different public keys. To fix this you need to use the properties of the threshold-encryption scheme. In a threshold-encryption scheme the players run a key-generation protocol in order to generate a common ...

1

They both symmetrical encrypt their keys by itself in an algorithm (or aes with enough iterations) that it takes minutes, even hours to complete (this gives ek1). Then they will do the same thing again (encrypt ek1 by itself) (this gives ek2) and send ek2 to the other person when they both say they are done. If they don't align, both parties then send ek1 to ...

1

I'm new here so I'm not sure about the best way to hold this discussion. So, I am adding a different answer to relate to why my proof sketch showing the impossibility of the problem in this question, versus Ricky's proof above that the protocol in this paper (page 16) is impossible. The answer is very connected to technical details to how you define and ...

1

Yes. $\:$ The verifier(s) need(s) to know a statistically binding commitment to $\Psi \hspace{-0.02 in}$.

1

My guess is, responses $\hat x_{(g,i)}..\hat x_{(1,i)}$ ($s$ in the example) are computed modulo group order that is not available to verifiers of the statement claimed. Challenge difference is always one ($1$) while rewinding for binary ($0$/$1$) challenges, and it is not expected to be one for "large" challenges. Dividing by a non-one (in other words, ...

1

Soundness usually means "you can't prove a false statement". There are different ways to formalise this but usually the probability of an efficient algorithm coming up with a false statement and a proof that verifies is negligible in some parameter (such as the length of the statement). Soundness can be defined for any proof scheme, including ones that are ...

1

Firstly, note that Groth-Sahai framework doesn't provide proofs of knowledge of exponents, because all commitments to exponents in it are computationally irreversible. It only provides proofs that show that such exponents exist. That is, a prover can claim to know $x$ but actually only know $\mathcal{A}^x$ for some $\mathcal{A}$, and still be able to produce ...

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 ...

1

An efficient proof of "more or equal" statement about integers committed is possible starting from Lagrange 4-squares theorem as follows: use a group of a hidden order (that is, unknown to proving party), like RSA; find four integers such that sum of their squares is the difference of original numbers committed; commit that four numbers and send all ...

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