<p>Yes, you can use Levin universal search to construct a "universal one-way function" (e.g., <a href="http://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture5.pdf">these lecture notes</a>). 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.</p>

<p>One-way function $\to$ pseudorandom generator:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>Pseudorandom generator $\to$ pseudorandom function:</p>

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

<p>Pseudorandom generator $\to$ block cipher / pseudorandom permutation:</p>

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

<p>Block cipher $\to$ CCA-secure encryption:</p>

<blockquote>
  <p>CBC mode + CBC-MAC</p>
</blockquote>

CC BY-SA 3.0
2016-04-10T07:24:30.033Z
Couldn't one use the PRF directly as a stream cipher with a Carter-Weigman MAC?
Demi
CC BY-SA 3.0
2016-04-10T16:04:05.590Z
Yes, once you have a PRF there are many options available. :)
mikero
CC BY-SA 3.0
2016-04-10T05:50:23.037Z
2016-04-10T05:50:23.037Z
mikero
<p>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.</p>

<cr.crypto-security><cryptographic-attack>
Is a "complete" cipher possible?
Demi
# Is a "complete" cipher possible?

(Asked by: username_0 on 2016-04-10)

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.

**Tags:** cr.crypto-security, cryptographic-attack


---

## 1 answers

### Answer by username_1 on 2016-04-10. Score: 6 | Accepted answer

Yes, you can use Levin universal search to construct a "universal one-way function" (e.g., [these lecture notes](http://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture5.pdf)). 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

> **Comments:**
> **username_0**: Couldn't one use the PRF directly as a stream cipher with a Carter-Weigman MAC?  
> **username_1**: Yes, once you have a PRF there are many options available. :)  

---

