Is a "complete" symmetric cipher possible? By this I mean a symmetric cipher that is provably secure under the assumption that a secure symmetric cipher exists.


1 Answer 1


Yes, you can use Levin universal search to construct a "universal one-way function" (e.g., these lecture notes). From this one-way function you can then construct symmetric-key encryption primitives (pseudorandom generators, block ciphers, CPA/CCA-secure encryption) using standard theoretical constructions.

One-way function $\to$ pseudorandom generator:

Håstad, J., Impagliazzo, R., Levin, L.A. and Luby, M., 1999. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4), pp.1364-1396.

Pseudorandom generator $\to$ pseudorandom function:

Goldreich, O., Goldwasser, S. and Micali, S., 1986. How to construct random functions. Journal of the ACM (JACM), 33(4), pp.792-807.

Pseudorandom generator $\to$ block cipher / pseudorandom permutation:

Luby, M. and Rackoff, C., 1988. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2), pp.373-386.

Block cipher $\to$ CCA-secure encryption:

CBC mode + CBC-MAC

  • 1
    $\begingroup$ Couldn't one use the PRF directly as a stream cipher with a Carter-Weigman MAC? $\endgroup$
    – Demi
    Commented Apr 10, 2016 at 7:24
  • 1
    $\begingroup$ Yes, once you have a PRF there are many options available. :) $\endgroup$
    – mikero
    Commented Apr 10, 2016 at 16:04
  • 1
    $\begingroup$ For improved efficiency, one can directly use "universal search to construct a" "universal PRF". ​ ​ $\endgroup$
    – user6973
    Commented Apr 29, 2016 at 16:01

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.