# Tag Info

7

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.

7

Sigma protocols as-is are secure only for honest verifiers. However, they can be easily compiled into full-blown zero knowledge protocols. If you don't want interaction, then the Fiat-Shamir transform suffices, with security in the random oracle model. With interaction, you can do the transform at little cost using commitments based on DDH. For more ...

6

I'm no FIPS expert but I strongly suspect the answer is no. FIPS is incredibly restrictive and laughably behind the times. To evaluate those algorithms that don't appear in FIPS, first make sure their component parts are secure (maybe even built with FIPS algorithms as subroutines). Then, if there are known answer tests anywhere, maybe from the authors of ...

6

This does seem to be zero knowledge; as you say, you don't actually commit to the adjacency list. Rather, you commit to a series of edges, in random order. Regarding the question: First, your assumption is that $n^2$ commitments, each to a single bit, is more expensive than $|E|$ commitments, each to $2\log n$ bits (to encode two numbers for the edge). This ...

6

There are certainly ZK proof systems which are not known to be POK, and for which no knowledge extractor is known. For example, take the Goldreich-Kahan 4-round ZK proof system. However, do we know of a non-trivial proof system that is provably not a proof of knowledge? Not that I know of.

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

5

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

5

There are many ways of doing this. A very nice read (but with informal presentation) is this paper by Fagin, Naor and Winkler on Comparing Information without Leaking It. A very fast protocol exists which requires a single oblivious transfer for every bit. Let $n$ be a security parameter; say $n=128$, and let $\ell$ be the bit-length of the inputs. For $i=... 5 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 are ... 5 The question mentions FIPS 140-2 Level 3 compliant. I answer this as if the question had said the intent is to validate the product as FIPS 140-2 Level 3. This may sound like hairsplitting, but there are many modules claiming to be FIPS 140-2 compliant, which factually could not be validated without large changes to functionality. FIPS 140-2 really intends ... 5 This is not zero knowledge. In particular, you give away information in the form of signatures on challenges. This is something that the verifier doesn't have and so it is something that is "learned". This can be meaningful for two reasons. Let's say that I want to prove to YOU that I wrote the book, but I don't want you to be able to convince anyone else ... 4 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 ... 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 I guess you are talking about Figure 5.3? It is said that the Schnorr proof (sigma protocol for discrete log relation) is insecure against cheating verifiers - it is only honest-verifier zero knowledge. Sigma protocols are always only defined in the honest-verifier zero-knowledge setting. To see why a cheating verifier is a problem in Figure 5.3 think ... 3 If you use a one-time pad as your encryption function then this simplifies to a proof that Alice knows some$F$that hashes to$H$.$K$can be trivially derived from$F$and$E(K, F)$by xor-ing. An interactive zero-knowledge proof of this simpler problem - Alice proving she knows a pre-image of$H(F)$- would go something like this: You need to use a ... 3 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 adversaries)... 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 Yes, you are right. In a proof, the soundness holds against a computationally unbounded prover and in an argument, the soundness only holds against a polynomially bounded prover. Arguments are thus often called "computationally sound proofs". 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 ... 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 doesn'... 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 Do you allow Bob to ask all the users having$F$to encrypt, then to upload the file with a same secret key deriving from$F$? Here would be the principle of the tweaked protocol : all the users must encrypt the file with the same key which depends on the file (calculated via another hash). The key would be a kind of shared key, but which can only decrypt ... 2 Consider a multiplicative group of an order$q$generated by some$g$. For simplicity, let commitment be$C_1 = g^{L_1}$. Consider a proof of knowledge of$L_1$committed to at$C_1$. At the first step of an interactive proof, choose some$L_2$at random and send$C_2 = g^{L_2}$to the verifying party. Second step, receive a challenge$c$. Third step, send a ... 2 I figured it out, it's quite simple actually. The$d$values (and$r$values) are all exponents and chosen from$\mathbb{Z}_q$. Thus all calculations on them directly take place in$\mathbb{Z}_q$. Applying mod$q$(not mod$p$) to all of my calculations on$d$and$r$fixed any problems with calculations. 2 Sure they can, it's called the socialist millionaires problem. The most common solution is to use Yao's protocol: Alice sends a garbled circuit of the equality function to Bob, and then Alice use oblivious transfers to send the keys necessary for the evaluation of the circuit to Bob. Another option is to rely on additively homomorphic IND-CPA encryption: ... 1 No, but if the problem isn't known to be in promiseMA then we do "assume that the prover can always solve the problem". http://cstheory.stackexchange.com/questions/696/mip-with-efficient-provers Graph isomorphism is trivially in NP, so for graph isomorphism, we just "assume that the prover" has an isomorphism between the graphs. Graph non-isomorphism is ... 1 This may look like a homework, so I would not present any complete "Ctrl-C Ctrl-V" -style solution. A proof for equality of logarithms was introduced at Chaum, Evertse and van de Graaf paper, "An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations", Eurocrypt 1987. At the core, Prover shows that the same single ... 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 Yes it proves that$y \ne 1 \pmod{n}$is not an$e$-th root. That is, no$x$exists such that$x^e = y \pmod{n}$. In particular, if$e | \phi(n)$then for any$x$it holds that$\left( x^{ \frac{\phi(n)} {e}} \right)^e = 1 \ne y$. This probably means one last final conclusion designed as a homework. Regarding GQ protocol: prover will be unable to pick an$...

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