I pretty recently understood the concept of zero-knowledge proof (on a purely logical level, not mathematically speaking, thanks to this article). Despite being a very counter-intuitive principle, it turned out to be an actual and applicable system. I am now wondering if another counter intuitive problem is solvable: is it possible to prove that we don't (or are unable to) know an information? Or to rephrase it in a more formal way, is it possible to prove that such a system is impossible to create? Regards

  • $\begingroup$ Surely some enterprising cryptographer could formulate the problem in such a way that it could be done without completely trivializing the problem. For example, say we know for a fact that the prover has certain knowledge and we know for a fact that they do not have other knowledge. If we can keep private what we want them to prove they know/don't know, we can send multiple challenges. Some of these challenges would be for things we know they know, others will be for things we know they don't know, and one will be for the thing we really care about. $\endgroup$ – mikeazo Aug 25 '16 at 16:17
  • $\begingroup$ Since they don't know what the challenges are, if they try to cheat by withholding some information, we may be able to detect it. $\endgroup$ – mikeazo Aug 25 '16 at 16:17
  • $\begingroup$ Brilliant question! Unfortunately, I doubt it'll get any interesting answers as I doubt it's possible. $\endgroup$ – Elliot Gorokhovsky Aug 28 '16 at 1:09

Yes. ​ Just prove that such information doesn't exist.
(For example, that can be used to prove that one
doesn't know a boolean value x such that ​ x and not x .)

For P/poly provers, if such proofs exist then UNSAT has a usually-correct promiseMA protocol.
However, if public-coin collision-resistant hash families exist, then
a common random string is enough for arguments of non-knowledge.
For example, to argue that one does not know a string
such that ​ Hcommon_random_string(0||x) = y , ​ argue that one
does know a string x such that ​ Hcommon_random_string(1||x) = y .

  • $\begingroup$ "does does" should be "one does"? $\endgroup$ – mikeazo Aug 25 '16 at 16:22
  • $\begingroup$ What if such information does exist, you just don't know that it exists? $\endgroup$ – mikeazo Aug 25 '16 at 16:25
  • $\begingroup$ Yes; fixed now. ​ One checks whether-or-not such information exists. ​ (For that part of this answer, there's no known general way for the prover to be weaker than having a #P oracle.) ​ ​ ​ ​ $\endgroup$ – user991 Aug 25 '16 at 16:36
  • 1
    $\begingroup$ @mikeazo in that case it seems intuitively impossible. Any cheating prover (that knows the given information) could always reproduce the proof of an honest prover (that does not know) by simply ignoring the information he is proving he does not know. $\endgroup$ – Guut Boy Aug 25 '16 at 21:01

It is not possible to show directly, that a prover does not know a certain information. Basically, the prover could just ignore this piece of information and act like a prover without the information.

But let's assume there is an encoding of knowledge into integers, then we can do this:

  • Have the prover commit to all his known information (with an unconditionally hiding commitment).
  • Send him your challenge.
  • Let him prove, that the challenge is not equal to any of his commited values. This can be done, see the answers to this question, although these techniques are not really practical.

If you send the challenge in the clear, then the prover does know the information after the execution of the protocol. Since he has to prove inequality to all his commited values, he needs to know that value. If you do not want him to know the information, you could apply a hash function to all the values in the protocol, although this isn't zero knowledge.

If you decide not to require the zero knowledge property at all, the prover could just publish the hashes of all his knowlegde. And then you check whether the hash of the information is in there or not.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.