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.


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

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

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.