Suppose I have a symmetric semantic-secure encryption system $\Pi = (Enc, Dec)$ and an OWF $f$.

Now, define the following encryption scheme $\Pi^{'} = (Enc^{'}, Dec^{'})$ where , $Dec^{'} = Dec$ and $Enc^{'}(k, m) = Enc(k,m)\mathbin\|f(k)$

Is that encryption still secure? I already tried to formally prove this claim with a hybrid argument, i.e. claim that

$Enc(k, m0)\mathbin\| f(k) \approx Enc(k, m0)\mathbin\| f(r) \approx Enc(k, m1)\mathbin\| f(r) \approx Enc(k, m1)\mathbin\| f(k) $

However, this proof turned out to be wrong (for example, maybe $Enc$ and $f$ both reveal the first bit of $k$ in the clear).

  • $\begingroup$ That's exactly my intuition but I learned in the hard way that my intuition might be very misleading... The issue is that OWF says its "hard to find preimage" but not that "it doesn't give information on the preimage" - so in particular maybe the OWF and Enc both reveal some partial information on k, such that every "hint" alone is useless but given the two hints simultaneously k can be found efficiently? $\endgroup$ – Bartolinio Dec 24 '19 at 13:54
  • $\begingroup$ Consider the encryption scheme that so happens to apply $f$ to its key before using the output as a regular key. $\endgroup$ – Maeher Dec 24 '19 at 15:39

It's possible to have a secure encryption scheme that ignores the first half of its key, and a secure OWF that leaks the entire second half of its input. Composing them as in your question results in something profoundly insecure.

| improve this answer | |
  • $\begingroup$ can we call such cipher semantically secure? $\endgroup$ – kelalaka Dec 27 '19 at 19:00

Your Answer

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

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