If I generate a random string and find that it happens to be a proof of Fermat's Last Theorem, that gives me a lot of evidence that Fermat's Last Theorem is true (I'd also be really surprised, but let's ignore that for now).

The zero-knowledge proof systems I'm aware of don't have this property: if I generate a random string and find that it happens to be a correct zero-knowledge proof of X, that provides zero evidence about whether X is true.

Formally, I'll say that a verifier V is a random-informative ZKP for a language L if:
- For a random x and y, V(x, y) is more likely to be 1 if x is in L.
- There is a simulator S such that (x, S(x)) is computationally indistinguishable from the distribution of (x, y) conditioned on V(x, y) = 1.

My question is: does every language in NP have a random-informative ZKP? I've checked a few examples and haven't found any random-informative ZKPs, but on the other hand it's easy to construct an oracle that makes random-informative ZKPs possible without making a problem in NP any easier.

I'll resolve the question as soon as I think it looks "pretty likely" one way or the other. I think that corresponds to something like an 80-90% chance, but for reference of some other claims:

- The first candidate for indistinguishability obfuscation made it seem "pretty likely" that indistinguishability obfuscation as possible.
- I think practically every standard complexity-theoretic conjecture is "pretty likely," all the way up to ETH but not SETH.

I think many of the cases where this question gets resolved it will be pretty obvious, e.g. we'll have some satisfying candidate construction or a reasonably convincing argument for why it shouldn't be possible. If that doesn't happen, it will probably be a push.

See a more detailed discussion on my Facebook post here (including a caveat that I want a random-informative ZKP which is either provably random-informative or subjectively random-informative, it can't just have a high subjective probability of objectively being random-informative): https://www.facebook.com/paulfchristiano/posts/pfbid02tWTuLpsGBtrzZzV6AAuSe5Adq1D2uWuXjmSQyzzxgaPKeR5WsV4AoYkPj2gBjaQsl