<p>Construction of provably-secure block ciphers are considered in the following papers:</p>

<ul>
<li><a href="http://portal.acm.org/citation.cfm?id=12167" rel="nofollow">Pseudo-Random Permutation Generators and Cryptographic Composition</a> by Luby &amp; Rackoff. Full version of this paper can be found in <a href="http://link.aip.org/link/?SMJCAT/17/373/1" rel="nofollow">How to Construct Pseudorandom Permutations from Pseudorandom Functions</a>.</li>
<li><a href="http://portal.acm.org/citation.cfm?doid=258533.258581" rel="nofollow">On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited</a> by Naor &amp; Reingold. This is in fact a revised version of the above ideas by Luby &amp; Rackoff. Full version can be found in <a href="http://www.wisdom.weizmann.ac.il/~naor/PAPERS/lr_abs.html" rel="nofollow">here</a>.</li>
</ul>

<p>The construct by <strong>Pat Morin</strong> and many others are reviewed in <a href="http://www.springerlink.com/content/hv06442h435q1233/" rel="nofollow">Building Secure Block Ciphers on Generic Attacks Assumptions</a>.</p>

CC BY-SA 2.5
2011-03-17T20:53:31.567Z
The paper "Building Secure Block Ciphers on Generic Attacks Assumptions" is interesting, but it doesn't actually review Morin's paper -- it only mentions it (en passant, without much discussion). But it helped a lot already! Thank you!
Jay
CC BY-SA 2.5
2011-03-05T03:11:42.473Z
A [paper by Dodis & Puniya](https://cs1.cs.nyu.edu/~dodis/ps/vrp.ps) proves more properties of the Luby-Rackoff (Feistel) construction, like security even if some of the internal states are leaked.
mikero
CC BY-SA 2.5
2011-03-04T11:44:50.443Z
2011-03-04T11:44:50.443Z
Sadeq Dousti
<p>I have read the <a href="http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf" rel="nofollow">paper by Anderson and Biham</a> [0] describing the ciphers Bear and Lion, which combine a PRG and a hash function (each cipher does that in a different way). the authors proved that a key recovery attack on the ciphers would imply breaking the PRG and hash function used. 
I also read the <a href="http://leonardo.ee.queensu.ca/sac/sac96/papers/paper3.ps" rel="nofollow">paper by Morin</a> [1] in which he shows a man-in-the-middle attack on Bear and Lion, and also proposes a new cipher (Aardvark) of the same kind, immune to such attack.</p>

<p>Was there any attack on Aardvark?</p>

<p>And are there other block ciphers with proof of security?</p>

<p>The references are the following (sorry, I couldn't find exactly the publication years and conference names)</p>

<p>[0] Ross Anderson and Eli Biham. <em>Two Practical and Provably Secure Block Ciphers: BEAR and LION</em>. </p>

<p>[1] Pat Morin (1996). <em>Provably Secure and Efficient Block Ciphers</em>.</p>

CC BY-SA 2.5
2011-03-04T09:20:35.133Z
Wrong link for Morin's paper.
Anthony Labarre
<reference-request><cr.crypto-security><cryptographic-attack>
Provably secure block ciphers
Jay
# Provably secure block ciphers

(Asked by: username_0 on 2011-03-03)

I have read the [paper by Anderson and Biham](http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf) [0] describing the ciphers Bear and Lion, which combine a PRG and a hash function (each cipher does that in a different way). the authors proved that a key recovery attack on the ciphers would imply breaking the PRG and hash function used.
I also read the [paper by Morin](http://leonardo.ee.queensu.ca/sac/sac96/papers/paper3.ps) [1] in which he shows a man-in-the-middle attack on Bear and Lion, and also proposes a new cipher (Aardvark) of the same kind, immune to such attack.

Was there any attack on Aardvark?

And are there other block ciphers with proof of security?

The references are the following (sorry, I couldn't find exactly the publication years and conference names)

[0] Ross Anderson and Eli Biham. *Two Practical and Provably Secure Block Ciphers: BEAR and LION*.

[1] Pat Morin (1996). *Provably Secure and Efficient Block Ciphers*.

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

> **Comments:**
> **username_1**: Wrong link for Morin's paper.  

---

## 1 answers

### Answer by username_2 on 2011-03-04. Score: 2 | Accepted answer

Construction of provably-secure block ciphers are considered in the following papers:

* [Pseudo-Random Permutation Generators and Cryptographic Composition](http://portal.acm.org/citation.cfm?id=12167) by Luby & Rackoff. Full version of this paper can be found in [How to Construct Pseudorandom Permutations from Pseudorandom Functions](http://link.aip.org/link/?SMJCAT/17/373/1).
* [On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited](http://portal.acm.org/citation.cfm?doid=258533.258581) by Naor & Reingold. This is in fact a revised version of the above ideas by Luby & Rackoff. Full version can be found in [here](http://www.wisdom.weizmann.ac.il/~naor/PAPERS/lr_abs.html).

The construct by **Pat Morin** and many others are reviewed in [Building Secure Block Ciphers on Generic Attacks Assumptions](http://www.springerlink.com/content/hv06442h435q1233/).

> **Comments:**
> **username_3**: A [paper by Dodis & Puniya](https://cs1.cs.nyu.edu/~dodis/ps/vrp.ps) proves more properties of the Luby-Rackoff (Feistel) construction, like security even if some of the internal states are leaked.  
> **username_0**: The paper "Building Secure Block Ciphers on Generic Attacks Assumptions" is interesting, but it doesn't actually review Morin's paper -- it only mentions it (en passant, without much discussion). But it helped a lot already! Thank you!  

---

