Quote from: thanke on May 12, 2013, 03:55:20 PM

Quote from: iddo on May 12, 2013, 02:40:32 PM

You can prove that you know c_par such that both (I_L,I_R)=hash(c_par, K_par, i) and K_i=I_L*K_par, without revealing c_par itself, via zero-knowledge computational integrity (PCP) proofs.

Really, you can zero-knowledge prove that you know a preimage of a hash?

Yes, ~~you don't send the entire proof (this wouldn't be ZK and the proof is long anyway)~~, you just let the verifier query a few bits from the proof, and if you didn't know the preimage then the verifier will catch you w.h.p.

Edit: actually you can send a very short full proof by building a Merkle tree from blocks of the long PCP proof and using the Merkle root as seed for pseudorandom queries, see SNARKs for more info.