No Knowledge Proof

   { I found the idea here https://suricrasia.online/no-knowledge.html, the
   page claims it comes from a Twitter user @chordowl. ~drummyfish }

   In the context of [1]cryptography no knowledge proof (NOT to be
   [2]confused with [3]zero knowledge proof) is a mathematical [4]proof of
   not knowing certain information. At the moment it seems to be kind of a
   [5]fun idea and curiosity without much use, but in math many fun ideas
   have found a serious use later on, so who knows. { If anyone knows of a
   legit use, let me know. ~drummyfish }

   The principle is this: supposed we have a one way (practically
   irreversible) [6]hash function H (such as [7]SHA-256). Also suppose we
   have all agreed on a special value y that's non-zero and has been
   constructed so that it most likely doesn't have any malicious properties,
   i.e. it is a so called nothing up my sleeve value and can be for example
   some sentence converted to ASCII -- more detail on this will follow later,
   now simply suppose we have some value y. Now by providing someone with a
   number x we prove we don't know a value z such that h(z) = h(x) xor y.

   How can this work? Well, imagine we knew z and we wanted to prove we
   didn't know it. We can compute h(x), (un)xor it with y, but now to compute
   x we'd have to reverse the hash h, i.e. compute x = h^(-1)(h(z) xor y).
   And from the definition of the hash we can't do this.

   Another possible intuitive explanation: basically we have a system here
   that creates pairs of numbers -- for any two numbers x and z the system
   defines whether they're linked or not (via the equation h(z) = h(x) xor
   y). The point is that given one of these numbers it is practically
   impossible to derive the other one due to the difficulty of reversing the
   hash function, so if we show we know one number (x) we are really showing
   we don't know the other number (z) because we simply can't have both.

   So the point of the [8]joke is that we can't choose the information we
   want to prove we don't know, but that's kind of logical as if we could, we
   would know it. We simply pick a number x and so prove we don't know some
   random number z with some properties related to x and y.

   A small vulnerability lies in the value y which is why it needs to be
   established carefully. We can't just accept someone else's x as a proof if
   it comes with a randomly looking y because then the proof may have been
   forged. How? Well, suppose there's been no y established; now again
   suppose we know some number z and want to prove we don't know it. We
   compute h(z), then we randomly choose some number x, compute h(x) and now
   we simply derive y as h(z) xor h(x). Now if someone accepts our y as
   valid, we have a forged fake proof as we know both the number x, i.e. a
   "proof" of not knowing z, but we also know z. So we have to make sure the
   one who is handing the proof (number x) did not pregenerate y this way.
   This opens up a possibility of attacking this proof by [9]brute forcing
   various y values, then taking those that somehow look "innocent" (e.g. by
   resembling some string or simple number sequence) and then trying to
   establish those as a legit nothing up my sleeve value.

   When thinking about it, it's not really that curious we can construct a no
   knowledge proof, in math we prove that we can't know something all the
   time (e.g. [10]undecidable problems).

Links:
1. cryptography.md
2. often_confused.md
3. zero_knowledge_proof.md
4. proof.md
5. fun.md
6. hash.md
7. sha_256.md
8. jokes.md
9. brute_force.md
10. decidability.md