[andromeduck]

Building on the normal discrete log/hamiltonian problems, if you have a random source that can be globally trusted such as some hash, then I think you could pretty easily prove it to the world as such:

1. Create a series of n problems P, based on some secret S, and and publish them. 2. Get some source of randoms everyone can trust, such as PRF(P) where PRF is some expensive secure hash function 3. Publish the proof of knowledge revealing the the piece specified by the random source.

Anyone can create P but only someone with knowledge of S can tractably pass step 3 because being able to do so implies either being able to predict the output of the hash function in which case the PRF is insecure or or getting winning 2^n coin tosses even if an attacker has an infinite pool of half revealed challenges he can pull from.

[betterunix2]

Technically that is not "zero knowledge" since the definition of ZK requires interaction (so there is no "publishing" of a proof). What you described sounds like this construction of "non-interactive ZK:"

https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic

NIZK is a very different concept from ZK, because the verifier does learn something, in the sense that the verifier has received a string it could not compute on its own. In ordinary ZK the verifier cannot compute anything after running the protocol that it could not have computed beforehand (so it gains nothing from the interaction).

[andromeduck]

I'm not quite sure I follow. What does the verifier learn after NIZK? Isn't it the point that the verifier learns nothing other than the prover has some secret knowledge? Seems to me like it's just the same information rescheduled with the help of a PRF.

[betterunix2]

The verifier learns the NIZK itself; i.e. the verifier could not have computed the NIZK independently.

[SilasX]

I agree, in that a proves-for-one ZKP can be converted to a proves-for-n if all n parties can trust the source of randomness used to decide the choice of challenge.