3 ms·

I'm stymied about parable 99. The nomenclature implies that Mr. Xi knew the basics of encryption. No mention whether the decryption function was provided or pre

I'm stymied about parable 99. The nomenclature implies that Mr. Xi knew the basics of encryption. No mention whether the decryption function was provided or previously agreed upon (e.g. "let's agree on GPG"). I think the decryption function or method is the key to answering the question. Am I missing something else?

partifex 9y ago
I understood it to be using a one time pad for encryption. At the start the "alien" would give an arbitrary sequence of numbers like "2, 4, 6", claiming it's an encrypted solution. Suppose the winning lottery numbers turn out to be "5, 5, 5". The alien then retrospectively generates a one time pad such that Initial Sequence + One Time Pad = Correct Sequence, in this case "3, 1, -1".
saulrh 9y ago
There are encryption schemes which allow you to choose the key to produce any arbitrary decryption from a given ciphertext. For a trivial example, consider the one-time pad scheme that's simply "plaintext XOR key" and "ciphertext XOR key"; by choosing a key that's equal to "plaintext XOR ciphertext" you can construct a key for any ciphertext from a plaintext or any plaintext from a ciphertext. Mr. Xi uses this to produce the just-released lottery numbers from the ciphertext regardless of the numbers or the ciphertext.
- modalduality 9y ago
  yup! they should have used a commitment scheme instead - for example, SHA256(winning numbers || 512-bit nonce). To reveal, reveal the winning numbers and the nonce and Mr X can check that the hash matches. The nonce is to introduce more entropy so Mr X can't just bruteforce the hash, but since finding any collision is difficult, it doesn't let the alien cheat by trying different nonces (unlike with different keys with encryption schemes).
xenophonf 9y ago
The scammer gave Mr. X the key, and once the winning lotto numbers were published, the scammer provided the ciphertext. I assumed an encryption scheme that was commutative, like the XOR operator (one-time pad).

partifex 9y ago

I understood it to be using a one time pad for encryption. At the start the "alien" would give an arbitrary sequence of numbers like "2, 4, 6", claiming it's an encrypted solution. Suppose the winning lottery numbers turn out to be "5, 5, 5". The alien then retrospectively generates a one time pad such that Initial Sequence + One Time Pad = Correct Sequence, in this case "3, 1, -1".

saulrh 9y ago

There are encryption schemes which allow you to choose the key to produce any arbitrary decryption from a given ciphertext. For a trivial example, consider the one-time pad scheme that's simply "plaintext XOR key" and "ciphertext XOR key"; by choosing a key that's equal to "plaintext XOR ciphertext" you can construct a key for any ciphertext from a plaintext or any plaintext from a ciphertext. Mr. Xi uses this to produce the just-released lottery numbers from the ciphertext regardless of the numbers or the ciphertext.

modalduality 9y ago
yup! they should have used a commitment scheme instead - for example, SHA256(winning numbers || 512-bit nonce). To reveal, reveal the winning numbers and the nonce and Mr X can check that the hash matches. The nonce is to introduce more entropy so Mr X can't just bruteforce the hash, but since finding any collision is difficult, it doesn't let the alien cheat by trying different nonces (unlike with different keys with encryption schemes).

xenophonf 9y ago

The scammer gave Mr. X the key, and once the winning lotto numbers were published, the scammer provided the ciphertext. I assumed an encryption scheme that was commutative, like the XOR operator (one-time pad).