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

5

If one-way functions exist, then there is a distribution over graphs (or SAT formulas, or ...) having the property you're asking for. In short, just put the OWF through the Cook-Levin reduction. In a little more detail, Cook-Levin transforms the NP witness-finding question "what is a preimage of $y = f(x)$?" (for random unknown $x$) into the NP ...

5

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

4

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

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

4

Even following your edits, there's still some confusion about honest verifier zero knowledge and plain-old (i.e., "possibly malicious verifier") zero knowledge, which is a much stronger property. Your description of HVZK is essentially correct, but with the following clarifications: A 3-move protocol between a prover P and a verifier V for a language ...

4

What does this mean, exactly? The purpose of the environment is to model "everything else happening in the universe" besides the protocol execution. In the UC model, the adversary is allowed to talk to the environment during the execution of the protocol. So UC security means "security no matter what else is going on in the world, even if other things ...

3

There is quite a bit of confusion in your question. First, differentiate between the real and ideal models. The adversary in the ideal model sends the adversary's input and gets its output (and can also sometimes determine if the honest party gets output, depending on the model). We often call the ideal adversary a "simulator" since this is how we build the ...

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

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

3

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

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

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

Yes, it's okay. This is actually mentioned in passing in the SRP 6 design paper. Previous versions used a random $u$ where an attacker who saw (or could predict) it before revealing $A$ could compute $A = g^a v^{-u}$ and use this to effectively cancel out the long term secret. With $u$ derived from a hash, even if the attacker saw $B$, the dependence of $u$ ...

2

The objective of the simulator is to make the simulated world (often called the ideal world) indistinguishable from the real world (running the actual protocol). See my write-up on the UC framework here for more detail. In the proof setup, the entity attempting to distinguish between the two worlds is often assumed to provide the inputs to the parties. That ...

2

The probabilistic nature is not specific to special-honest verifier zero-knowledge but that's what zero-knowledge is about. With zero-knowledge you want to formulate that such an interactive proof does not leak any information besides the validity of the claim, as it is efficiently simulatable meaning that real and simulated transcripts are not ...

2

The simulator obtains "client $B$'s input" in the same way the simulator obtains $\:\{\hspace{-0.03 in}0,\hspace{-0.04 in}0\hspace{-0.03 in}\}\;$. Even in the real world, the server computes its response without using any secrets, that response is the only message $B$ receives, and (from your description) no other party gives any output. $\:$ Thus, it ...

1

I've found some lecture notes where, in section 2.4, they give the steps that a simulator would do in order to simulate the view of the honest prover talking to the honest verifier (HVZK). In response to the first question, in the case when the simulator initially guessed wrong the challenge coming from the verifier, the verifier is rewinded but the ...

1

The simplest example I know of is actually for a pathological case. Namely, it is presented in Chapter 2 of the book of Hazay and Lindell as an example of a two-party MPC protocol which is secure against a malicious adversary but not against a semi-honest one (in the classical sense, for this reason they prefer the notion of augmented semi-honest ...

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

$$(x,r) = g^x h^r$$ $$C = (x,r)^ \mu$$ Now you have two standard proofs of knowledge.

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