0
$\begingroup$

A Knowledge Proof is a mechanism by which a 'prover' entity can show to a 'verifier' entity that it possesses some certain information without revealing what that specific information is (within some arbitrarily small tolerance of certainty).

Is it possible for a 'prover' to show to a 'verifier' that it does not possess some certain information (without the 'prover' being computationally limited, etc.)?

$\endgroup$
5
  • $\begingroup$ If a prover is being beaten with a rubber hose to force him to divulge e.g. an AES key, he may be able to convince a verifier that such a key does not exist if one in fact does not exist. Unfortunately such a proof might be exponentially long. Is that the kind of deniability you had in mind? $\endgroup$
    – Kyle Jones
    Apr 17, 2021 at 0:43
  • $\begingroup$ @KyleJones Interesting point, but not quite. Imagine that the person with the correct AES Key had escaped, and the suspect under interrogation did not have knowledge of what the correct AES Key is. How can the suspect prove such a thing so that he is swiftly released? Must some other important assumptions be made in order to prove such a thing (such as a full tracking & logging of the suspect's past interactions, something more complicated, etc.)? $\endgroup$ Apr 18, 2021 at 18:33
  • $\begingroup$ I do not believe this is possible unless more assumptions are made. My argument is the following. Suppose there is a proof system such that prover A who knows the secret S, fails, while B who doesn't know S succeeds. As A has more knowledge than B, it can always simulate every interaction of B, and thus succeed as well... So in order for this to make sense, there needs to be something B knows that A doesn't. $\endgroup$ Aug 15, 2021 at 2:08
  • $\begingroup$ @c-x-berger Definitely interesting, though I don't quite understand how reversing a hash function would show that one doesn't have knowledge of some input. I was originally interested in this problem because of things like criminal torture etc., so I also had 2 parties in mind, which I don't think the article addresses (though I may have missed that). $\endgroup$ May 20 at 16:58

1 Answer 1

1
$\begingroup$

No. An algorithm that has access to some information can always ignore it and make decisions without looking at it, and then its externally observable behavior will be indistinguishable from an algorithm that doesn't have access to that information; so no verifier can tell the two apart.

I suggest being a bit cautious: when we talk about words like "knowledge" in the context of algorithm, we are applying some human intuition and interpretation to the underlying mathematics. The precise meaning is given by the formal mathematical definition.

Incidentally, it's called a proof of knowledge, not a knowledge proof.

$\endgroup$
1
  • $\begingroup$ Don't worry, I understand what 'knowledge' means in this case (I am thinking of a set of tokens, but we could also use the string-in-language-interpretation). Still, I had hoped for a bit of a more formal proof (though I shouldn't've expected one given the content of my question). $\endgroup$ Nov 17, 2020 at 18:32

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.