A non-interactive zero-knowledge proof scheme: The prover commits (shuffle+lock) the graph N times: s[0..N]. He then calculate r=hash(s[0] || s[1] || .. || s[N]). And then he use the random bits in r generate N pseduorandom numbers c[0..N]. For each i=0..N, use c[i] to select a fixed edge in s[i] and reveal the keys k[i][0] and k[i][1] for the two nodes of the edge. The final message consists of s[0..N] and k[0..N][0..1]. The verifier is able to use these information to replay the steps to verify the prover's claim.

Another thing I learned from the video is how to "lock" messages cryptographically and allow the verifier to verify any message without revealing the others. First, the prover calculate h[i] = hash(m[i] || nounce[i]) and send h[0..N] to the verifier. The verify choose any integer t between 0 and N and send to prover. The prover will then send back (m[t], nounce[t]) to the verifier that h[t] is indeed calculated from m[t]. Here h[t] is the locked message m[t] and nounce[t] is the key.

I'd like to note the AirTag privacy-preserving tracking scheme I learned:

1. the tag shares its key pair with its owning host as part of the pairing process
2. the tag broadcasts its public key when away from its host
3. nearby phones pick up the broadcast and send a location report to the apple server, which includes:
   • the phone's gps location encrypted using the tag's public key
   • the hashed public key of the tag
4. the apple server store the location reports for each hashed public key
5. the host can request the apple server to download location report for the tag using a public key. then it decrypts the gps location using the private key it got during pairing

The basilisk collection (also known as the basilisk file or basilisk.txt) is a collection of over 125 million partial hash inversions of the SHA-256 cryptographic hash function. Assuming state-of-the art methods were used to compute the inversions, the entries in the collection collectively represent a proof-of-work far exceeding the computational capacity of the human race.

This is a grand work of fiction.

The author has another fiction on the concept named "Clairvoyant Computing": https://suricrasia.online/unfiction/CSC218-Software-Precognance.pdf

A tool that solves Caesar Cipher automatically. It can solve simple substitution ciphers often found in newspapers.

Can two potentially dishonest players play a fair game of poker without using any cards (eg. via the mail, or via the telephone) and without using any mutually trusted intermediate?

<blockquote>starting point and ending point are</blockquote>