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.


1 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).

  • $\begingroup$ Thanks. I just didn't interpret $0^s$ that way - duh! It's obvious now. $\endgroup$
    – Paul Uszak
    Jul 28, 2019 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.