Tag Info

4

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

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

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

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

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