# Is a “complete” cipher possible?

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

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