# Tag Info

10

This is not an actual answer; I'm just sharing some results (which do not fit in one comment). Goldreich, Micali and Wigderson (J. ACM, 1991) proved that every language in NP has a zero-knowledge proof of language membership (assuming OWFs exist). To this end, their presented a ZK proof for graph 3-colorability. Later, Bellare and Goldreich (CRYPTO '92) ...

10

I'm one of the authors. Someone pointed me to this question. Based on a quick reading, here's an attempt at answering your concern. What may not be very clear from this version of the description of the simulator (this was the first time I was describing a simulator, and admittedly it reads a bit too much like machine language) is that the view output by ...

3

PCPs are very often used to construct ZKPs, especially for NP-complete languages. The idea is simple: you commit to every bit of PCP separately, and then the prover makes random queries to the PCP. Given the query and committed bit, you prove in ZK that the bits in concrete locations would make the prover to accept. Since the number of queries is small, the ...

3

The answer is yes, check the following paper: SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge Eli Ben-Sasson and Alessandro Chiesa and Daniel Genkin and Eran Tromer and Madars Virza http://eprint.iacr.org/2013/507 (also published at Crypto 2013)

3

So here is the right paper for my purposes: Joe Kilian, "A note on efficient zero-knowledge proofs and arguments." http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf To get the strongest result, we need to accept zero knowledge arguments rather than proofs (computationally bounded prover); these are what I am interested in but did not know ...

3

For symmetric-key encryption: If Alice and Bob know a proof that $D_K(E_K(x))=x$ for all $x,K$, then they should be able to prove this fact in zero knowledge. In particular, they can produce boolean circuits for $D_\cdot(\cdot)$ and $E_\cdot(\cdot)$, publish a commitment to each boolean circuit, and then turn their proof into a zero-knowledge proof. In ...

3

Yes, it would still be zero knowledge. However, it wouldn't be a proof of anything, since whether the colors matched or not, you still know nothing about whether the graph is actually 3-colored or not. It's not a trick question -- just a bad one.

2

I think you are confusing zero knowledge with soundness. Fix some language $L$. [Adaptive] soundness for NIZK says, roughly, that when $\sigma$ is chosen at random a prover cannot find a $y \not \in L$ and a proof $\pi$ for which a verifier will accept. Zero knowledge says that, for any $y \in L$, a simulator can output $(\sigma, \pi)$ that is ...

2

I'm not sure the solution you have given works. However, it can be adapted to work -- both for NIZK proofs and proofs of knowledge -- by using a coin-tossing protocol where "secure" here means in the sense of general secure two-party computation. This can be done based on one-way functions in polynomially many rounds, or based on stronger assumptions in ...

2

The most famous "efficient" NIZK is by Groth and Sahai: Jens Groth, Amit Sahai Efficient Non-interactive Proof Systems for Bilinear Groups, Eurocrypt 2008 If you are willing to use stronger security assumptions, you can get even better efficiency. See the following paper of Groth (and subsequent improvements by other people), for example: Jens Groth Short ...

2

Update: This answer is obsoleted by my other answer, with fully polylogarithmic bounds from appropriate references. On second thought, there's no need to reveal the Merkle tree gradually, so the lower communication version needs no extra rounds. The communication steps are The prover P randomizes its coloring, turns it into a (salted) Merkle tree, and ...

1

There is a recent surge in activity in succinct non-interactive zero knowledge arguments. It is known how for example construct an NIZK argument for Circuit-SAT where the argument length is a very small constant number of group elements (see Groth 2010, Lipmaa 2012, Gennaro, Gentry, etc, Eurocrypt 2013, etc). Based on an NP-reduction you can then clearly ...

1

There is a classical paper of Feige and Killian Zero Knowledge and the Chromatic Number that uses the ideas from Zero Knowledge Proofs in order to construct PCPs with certain "ZKP-type" properties. Using these properties they prove that it is NP-hard to color a $N^{0.01}$-colorable graph with $N^{0.99}$-colors. It should be noted that their result does not ...

1

Regarding your reference request, I remember the following paper off the top of my head: Willaim Aiello and Johan Hastad. 1991. Relativized perfect zero knowledge is not BPP. Inf. Comput. 93, 2 (August 1991), 223-240. http://dx.doi.org/10.1016/0890-5401(91)90024-V. Now, to answer your question: Consider any NP-complete language $L$, let $G$ be a generator ...

1

You can adapt the work of Okamoto-Chaum-Ohta to this case. Let $P$ be the prover, $V$ the verifier, $E$ the public encryption key + algorithm (common input to $P$ and $V$), and $D$ the secret decryption key + algorithm (private input to $P$). We assume that $E$ can be probabilistic (to satisfy semantic security, it has to be), and therefore it uses some ...

1

The prover and the simulator must both be able to generate the proof, but given different inputs. The Prove functionality gets as input the CRS $\sigma$, the statement $y$ and the witness $w$, and outputs $\pi$. The soundness requirement postulates that nobody should be able to create $\pi$ for $y \not\in L$, given $\sigma$ as an input. However, zero-...

1

Regarding the prover's witness, the standard zero-knowledge (ZK) definitions already imply that ZK holds even if the distinguisher is given this witness. I'm not sure what you mean by "the random bits used by the algorithm that generated the auxiliary input". Please clarify.

1

There is an elegant and rather efficient zero-knowledge protocol for these kinds of NP statements given in this paper: Marek Jawurek, Florian Kerschbaum, Claudio Orlandi: Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently (CCS 2013) In fact, SHA-256 preimage is the example they list in the abstract. Maybe this old ...

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