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.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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 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
