2
$\begingroup$

Is that possible to prove that 'I do not know something' (i.e, the private key for a cryptocurrency wallet) using cryptography?

The problem might be nonsense at first glance. But the intuition for this might be to prove that I do not hold the crypto coins under a specific wallet.

|improve this question
$\endgroup$
4
$\begingroup$

You are asking for some cryptographic function whose output changes based on whether or not your mind holds a particular piece of information. There is no function which is capable of knowing what is in your mind. You can cryptographically prove ownership, but you cannot do the opposite.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ The first two sentences are a little of a non-sequitur, no? Obviously no function can read your mind, but that argument could apply just as well to the opposite question of whether it can prove that you know something, and obviously such primitives exist, not through mind-reading but through proving that you hold a particular piece of information. Mind-reading has nothing to do with whether such a function can exist or not. $\endgroup$ – Thomas Mar 4 '18 at 9:44
  • $\begingroup$ You can prove that you know something simply by being able to provide a representation of that something, for example a cryptographic hash. $\endgroup$ – forest Mar 4 '18 at 14:37
  • $\begingroup$ You can also do things that would mimic the concept of proofs of ignorance, and ensure (under some minimal trust assumption in a setup phase) that a party cannot know a specific piece of information - that's non trivial, but not infeasible, and clearly not "obviously impossible". $\endgroup$ – Geoffroy Couteau Mar 4 '18 at 17:39
  • $\begingroup$ @GeoffroyCouteau Could you explain how that could possibly work? A person can hold knowledge of something and I cannot think of any way for them to prove that they don't. The closest possible thing would be a well-documented chain of custody for a piece of information to ensure you never came in contact with it, but then that would be a legal solution, not a cryptographic solution. $\endgroup$ – forest Mar 5 '18 at 2:29
  • 1
    $\begingroup$ Sure, hence I did not post my comment as an answer, nor downvoted yours - I was just pointing to the fact that things are not necessarily obvious: even if it seems impossible to provide a solution, an intuition that it cannot be done does not preclude the existence of sufficient solutions in various scenarios. $\endgroup$ – Geoffroy Couteau Mar 5 '18 at 9:02
2
$\begingroup$

Anyone can prove, using the implied ledger, that for any particular public key the coins are not held by that particular public key, in much the same way one normally proves they are held before accepting a transaction.

But you could be palming a copy of a different private key in your other hand which does hold the coins according to the ledger.

The story you tell to your interrogator about how the coins got to that other key is a question that falls outside the domain of cryptography. You may wish to consult a solicitor if it comes to that, or work on interrogation resistance techniques if your business turns out to fall outside the legal domain too.

|improve this answer
$\endgroup$
2
$\begingroup$

Just to add to the discussion, from a completely definitional point of view, of course it makes sense to consider the concept of no-knowledge. For example, consider the usual definition of proof of knowledge:

We say that $P$ knows $x$ if there is an efficient extractor $E$ that can interact with $P$ to obtain (extract) $x$.

What do we get if we negate this definition? The result would look something like this

We say that $P$ does not know $x$ if for every efficient algorithm $E$ the probability that $E$ outputs $x$ after interacting with $P$ is negligible.

Notice that nothing prevents such definition to exist, and, in fact, it makes a lot of sense! We can say that you don't know something if no matter who you interact with, you never make use of that "something". Now, a different question is whether or not this definition is achievable in any concrete model, which I believe is one of the main arguments against the idea on this question.

As a side note, it may be worth to take a look at this (already hinted by @Geoffroy Couteau). From the abstract: Loosely speaking, such a proof system [proof of ignorance] allows a prover to generate an instance x according to D along with a proof that she does not know a witness corresponding to x.

|improve this answer
$\endgroup$

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.