# 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 §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:
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}$$).
• Thanks. I just didn't interpret $0^s$ that way - duh! It's obvious now. – Paul Uszak Jul 28 '19 at 23:35