Blackle Mori (@suricrasia) - 2021
To create a no-knowledge proof, we first generate a random nonce
N = 3a37a855f8267690fe64cbfd7f612249d6f016929605cbd26ae8c6a4005f2388
Then, we take H = SHA-256(N)
H = ddb27a4a601086054ae8a9a8d50ef1b5c03f2ea5100a4bf627323eecd1383e2a
Then we use this nothing-up-my-sleeve number...
S =
(this is the string "--this is a no-knowledge proof--" in hexadecimal)
...to compute C = H xor S
C = f09f0e220963a66c39c8c888bb61dcdeae5059c9756e2c9307424c83be5e1307
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.
Novelty :3
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.