How does the security parameter within a digital locker help prove that it unlocked correctly? I refer to Canetti et all, "Reusable Fuzzy Extractors for Low-Entropy Distributions", available here.

Paraphrasing the relevant part from &sect;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.
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:


Always appear if you have the correct key for some ciphertext
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).