Suppose we have a secure trapdoor function defined on (G, F, F^-1) where G is a randomized algorithm outputs a key pair (pk, sk). Why would this trapdoor function become insecure if we apply F directly to plaintext message? E(pk,m) = c = F(pk, m)

  • $\begingroup$ What exactly do you mean with "directly on plaintext"? Without a secure padding scheme or without hashing the input before encryption? Or something else? $\endgroup$ – Nova Mar 18 '15 at 4:19
  • $\begingroup$ It's just a very simple encryption where G() generate (pk, sk); F(pk, .) is a deterministic algorithm that defines a function X->Y ;F^-1(sk, .) defines a function Y -> X that inverts F(pk,.) $\endgroup$ – hvuong91 Mar 18 '15 at 4:33
  • $\begingroup$ Yeah, I did understand that, but I don't know what you mean with the "apply F directly to the plaintext message" << What do you want to do instead? Hashing the message? Or applying a padding scheme like OAEP? $\endgroup$ – Nova Mar 18 '15 at 4:35
  • $\begingroup$ Instead of using a random hashing function to get k = H(x) where x is random and output ciphertext c = (F(pk,x), E(k,m)), the scheme above just simply outputs c= F(pk, m) $\endgroup$ – hvuong91 Mar 18 '15 at 4:45
  • $\begingroup$ What does "secure" mean in this context? It can't be IND-CPA, because that does not work with a deterministic encryption function. It can't be in the context of signatures, because there you use $F^{-1}$ to generate the signature. $\endgroup$ – tylo Mar 19 '15 at 10:05

Trapdoor functions only provide one-wayness. This means, that if one uses a trapdoor function to encrypt this may leak large parts of the plaintext. Suppose I have a trapdoor function $F(pk,m)$ for say n-bit messages $m$. I can now define an adapted trapdoor function working on $2n$ bit messages as

$F'(pk,m_1||m_2) = m_1 || F(pk,m_2)$

This is still a secure trapdoor function but, leaks half of the bits of the "plaintext".


An eavesdropper could easily test any candidate message to determine
whether or that candidate message was the plaintext message.

def test_candidate_message_(pk,c,candidate):
 if c == F(pk,candidate):
  return True
  return False
  • $\begingroup$ Can you give a simple example how an eavesdropper can break this scheme? $\endgroup$ – hvuong91 Mar 18 '15 at 4:10
  • $\begingroup$ I just did that. $\;$ $\endgroup$ – user991 Mar 18 '15 at 4:14
  • $\begingroup$ How would that change if the message was first hashed before using the trapdoor function? $\endgroup$ – Nova Mar 18 '15 at 5:18
  • $\begingroup$ @Nova : $\:$ The eavesdropper would first hash candidate before using the trapdoor function. $\hspace{.69 in}$ $\endgroup$ – user991 Mar 18 '15 at 5:43
  • $\begingroup$ @RickyDemer: Yes, that's right, but that is exactly what hvuong91 did ask: Why does that become insecure if we don't do that? It would not change anything, because the attacker would still be able to try that. It's both insecure, and the question asks why not hashing is insecure while hashing is secure. $\endgroup$ – Nova Mar 18 '15 at 5:47

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.