I am learning about one way permutations and one way functions and am not sure of the differences if there are any.

Also in the random oracle model are they both IND-CPA secure?


A one-way permutation is just a one-way function in which the function is a permutation (id est, a bijective function). Every OWP is a OWF, the converse is not true.

IND-CPA security is a security notion specifically related to encryption schemes. OWF and OWP are not encryption schemes, hence they cannot be said "IND-CPA secure"; however, one can construct an IND-CPA symmetric encryption scheme from any OWF, or OWP. (for asymmetric encryption schemes, stronger primitives are needed).

  • $\begingroup$ Thanks for the help! It's a bit more clear now. Can you give me an example of how one can construct an IND-CPA symmetric scheme from an OWF $\endgroup$ – Will Roberts Apr 18 '16 at 2:12
  • $\begingroup$ Essentially, the idea is to construct a pseudorandom generator from a OWF. Once this is done, just use the private key as the seed of the PRG and generate as much bits as your message lengths. To encrypt, just xor those pseudorandom bits with the message. The seminal paper showing how to construct PRGs from OWFs is this one, if you have trouble understanding it / are not familiar with reading research articles, just ask and I'll try to give an intuition of the construction. $\endgroup$ – Geoffroy Couteau Apr 18 '16 at 2:23
  • $\begingroup$ The paper giving a more efficient construction of PRGs from OWFs is this one. ​ ​ $\endgroup$ – user991 Apr 18 '16 at 2:36
  • $\begingroup$ Can't you use the G-L hardcore bit to get a much simpler PRG than the one from the HILL result? $\endgroup$ – pg1989 Apr 18 '16 at 2:44
  • $\begingroup$ Okay I'm still a bit unsure son how to achieve IND-CPA security using public key encryption in the random oracle model with OWP $\endgroup$ – Will Roberts Apr 18 '16 at 2:54

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.