How does the security parameter within a digital locker help prove that it unlocked correctly?

Question

I refer to Canetti et all, "Reusable Fuzzy Extractors for Low-Entropy Distributions", available here.

Paraphrasing the relevant part from §3:-

The locking algorithm $lock(key,val)$ outputs the pair $nonce,H(nonce,key) \oplus (val||0^s)$, where H is a cryptographic hash function, nonce is a nonce, ||denotes concatenation, and s is a security parameter.

s creates a certainty of $1−2^{−s}$ that the unlocking was successful. Surely there must be some relationship omitted from the paper between s, |(nonce,key)| and |val| for the XOR operation to be useful. It has the smell of HMAC about it.

How can what appears to be padding with s zeros help prove that the locker was correctly opened? Is it some strange mathematical way to simply guarantee the bit length of (nonce + key)?

---

Note. My confusion is increased by the fact that the nonce output from the lock function does not seem to be an input for the unlock function.

Answer 1

They mention $H(nonce, key)$ is modeled as a random oracle. Then, $H(nonce, key) \oplus M\cong U\oplus M$ where $U$ is uniformly random, so the encryption scheme (essentially) becomes the one time pad. This is a fairly standard construction.

One "flaw" with the one-time pad is that everything has a valid decryption. Given that this is the case, how can you be sure you have the "right" key for some ciphertext? The solution they mention is looking for the string $0^s$ at the end of your plaintext. This will:

1. Always appear if you have the correct key for some ciphertext

2. Almost never appear if you have the incorrect key for some ciphertext (specifically, it will appear with probability $2^{-s}$, so you'll detect the incorrect key was used with probability $1-2^{-s}$).

This is morally equivalent to something like a checksum, and can probably be formalized using the terminology of error-correcting codes (but I won't attempt to).