In short:

Are lossy function the only way to prove security using leftover hash lemma for computationally secure protocols?


I recently discovered/understood the leftover hash lemma, that basically states that even if you have only partial knowledge about a binary string $s$ (the entropy still needs to be big enough), then you have no information about the xor (it also applies to other functions but xor is enough for me) of a random subset of this string.

However, it appears that this lemma is expressed in the unconditional/information theoretic setting, and most of the times in real applications we are interested in the computational setting. As far as I understand, people use lossy functions to go from computational setting to unconditional setting, and then they use leftover hash lemma. But you want to make sure that no adversary can distinguish whether you are using lossy functions or injective functions.

The problem is that in my case I need to send one bit of information to the adversary, and I have no argument to say why this bit could not leak whether we sampled a lossy function or an injective function... (I just know that this bit does not reveal too much about $s$ and that's why I wanted to use leftover hash lemma). Are lossy function the only way to prove security using leftover hash lemma for computationally secure protocols? Or is there any other lemma/method that I could apply when aborting could leak some partial information ?

-- EDIT --

To give more details, say I have a cryptographic function $f$ that encrypts a $t$ bits message, and let's define $y = f(x_1,\dots,x_t)$ a given encryption. Given $y$, I can show that no polynomially bounded adversary can obtain any information about $X = x_1, \dots, x_t$, so intuitively the (computational) "entropy" of X is $t$ (of course an unbounded adversary could obtain it, but in exponential time). Now, I send this $y$ to an adversary, and he can send me a message (that I interpret like a question), and I will answer to this message with a single bit $a$, and I abort if $a \neq 1$. I can easily show that no polynomially bounded adversary can guess with good probability the exact value of $x_1,\dots,x_t$ when the protocol does not abort (i.e. $a = 1$, I also assume that the probability to continue without abort is non negligible), so the advantage he can get from this bit is not huge. So intuitively, the entropy of $X|a=1$ is still of the order of $t$, but I don't know which part of $X$ has been leaked. So I really would like to be able to apply the leftover hash lemma to extract one bit of information from this string $X | a=1$...

BUT the leftover hash lemma does not apply here, because the entropy I'm using from the very beginning is not a real entropy, but more a "computational" equivalent. Indeed, if I know $y=f(X)$, the entropy of $X$ is 0 as $f$ is injective: an adversary could just try all possible values until he finds the good $X$. As far as I understand LHL, people solve this problem by in the proof by using another kind of function that are lossy, i.e. non injective, in order to be back to a real entropy (given $y$, I have lot's of possible preimages, so I cannot get $X$), and they say that an adversary cannot distinguish between the real usefull injective function and the lossy one. But here I can't do that as the bit $a$ could leak some information about whether I'm using a lossy function or an injective function... Any idea if I have another way to prove security here, as the result seems super natural? (I also need a quantum-resistant proof to simplify things)


  • $\begingroup$ Not sure that the LHL specifically mentions/requires XOR. LHL is typically used for randomness extraction calculations alongside (kinda) universal hash functions. It's more of a subtraction. And clearly a crypto hash can't be injective. – $\endgroup$ – Paul Uszak Apr 3 '19 at 15:07
  • $\begingroup$ You may also need to expand on your aborting use case. $\endgroup$ – Paul Uszak Apr 3 '19 at 15:07
  • $\begingroup$ @PaulUszak LHL mentions 2-universal hash functions, and XORing a random subset is just an example of such function. And when I'm talking about injectivity, I'm not talking about the injectivity of the XORed result (of course it can't be injective), but on the injectivity of the cryptographic function used before applying the XOR lemma, for example if you plan to encrypt a message. I'll try to edit the question to add more detail. $\endgroup$ – tobiasBora Apr 3 '19 at 16:26
  • $\begingroup$ @PaulUszak see update $\endgroup$ – tobiasBora Apr 3 '19 at 16:53
  • $\begingroup$ What is your question? What information do you have, what information does your peer have, and what information does the adversary have? What resources are you using? What are you trying to accomplish using these resources? $\endgroup$ – Squeamish Ossifrage Apr 4 '19 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.