Blackle Mori (@suricrasia) - 2021
To create a no-knowledge proof, we first generate a random nonce
N = 636c20e9c79353fcf913edb6a9ba41da209ebe60b71be7986d274f5ed0b4a9e8
Then, we take H = SHA-256(N)
H = 1fd9ad1ee63ac57424213c3b855ed4a0bbced628f3a9b95ba7e75bd63749835d
Then we use this nothing-up-my-sleeve number...
(this is the string "--this is a no-knowledge proof--" in hexadecimal)
...to compute C = H xor S
C = 32f4d9768f49e51d57015d1beb31f9cbd5a1a14496cdde3e879729b9582fae70
And with that, we have proved that we do not know a value P such that C = SHA-256(P)
P = ????????????????????????????????????????????????????????????????
Have you ever wanted to prove that you didn't know something? Now you can! You can use this technique to prove that you don't know 256 bits of information. Of course, you cannot choose what information you don't know, it's entirely random. But it's the thought that counts, right?
Essentially we're taking advantage the preimage resistance of the SHA-256 hash function. Preimage resistance says that given a value B, it's computationally intractable to find a value A such that B = SHA-256(A).
If we wanted to forge a "no-knowledge" proof—that is, we actually know the value P but we want to prove that we don't—we'd be forced to reverse a SHA-256 hash. Thanks to preimage resistance, this is impossible (at least within our universe.)
If we have our final C value then the only way to generate P is by reversing the SHA-256 hash function, which is impossible due to its preimage resistance. If we compute P first and then use it to generate C, we would still need to provide H and N, and we're back at square one. We'd need to reverse the hash value H, which is intractable.
Nope! Credit for the idea goes to @chordowl on Twitter. I just coded up this page because it tickled my fancy.
No, a zero-knowledge proof is something else entirely. In a zero-knowledge proof, you prove that you know something without revealing any information about what that something is. One common example is proving you've solved the three-colouring problem on a graph without revealing the actual colouring. You can find an excellent explanation of the proof process over at Zero Knowledge Proofs: An illustrated primer.
Perhaps! There has been research into applying zero-knowledge proofs to cryptographic signatures. In these systems, your secret key is a nonce value and the public key is its hash. As part of the signature-making process, you create a zero-knowledge proof that you know the preimage to the public key. One specific scheme is called "ZKB++" and is presented in the paper Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives by Chase et. al.
So given the mathematics involved with ZKB++, we could create a zero-knowledge proof that we have some H = SHA-256(N), without revealing either H or N. Using this system we can prove that we don't know something, without revealing any other information. Simply incredible.
Ok bye, have a good one.