From msuinfo!agate!howland.reston.ans.net!pipex!lyra.csx.cam.ac.uk!pavo.csi.cam.ac.uk!cam-orl.co.uk!aph Tue Mar  1 15:21:03 1994
Newsgroups: sci.crypt
Path: msuinfo!agate!howland.reston.ans.net!pipex!lyra.csx.cam.ac.uk!pavo.csi.cam.ac.uk!cam-orl.co.uk!aph
From: aph@cam-orl.co.uk (Andrew Haley)
Subject: Re: Ladder DES
Message-ID: <1994Mar1.191523.29084@infodev.cam.ac.uk>
Sender: news@infodev.cam.ac.uk (USENET news)
Nntp-Posting-Host: okra.cam-orl.co.uk
Organization: Olivetti Research Ltd, Cambridge, England.
X-Newsreader: TIN [version 1.2 PL2]
References: <1994Feb22.083353.26012@cactus.org>
Date: Tue, 1 Mar 1994 19:15:23 GMT
Lines: 82

Terry Ritter (ritter@cactus.org) wrote:



:                     Ritter Software Engineering
:                         2609 Choctaw Trail
:                         Austin, Texas 78745
:                  (512) 892-0494, ritter@cactus.org



:           Ladder-DES: A Proposed Candidate to Replace DES

:                            Terry Ritter
:                          February 22, 1994

[ ...deleted... ]

:              A              B
:              |      k1      |
:              v      v       |
:             XOR <- DES1 ----|
:              |              |
:              |      k2      |
:              |      v       v
:              |---- DES2 -> XOR
:              |              |
:              v              v
:              C              D

It's worth pointing out that when used this way DES is always carried
out in the "forward" direction, even during decryption.  Because of
this, the "scrambling" function used in the "ladder" only needs to be
a pseudorandom function; it does not have to be a pseudorandom
permutation like DES.  A hash function with a 128-bit input and a 64
bit output could be used for this purpose.

[ ...deleted... ]

:  Conclusion

:  DES operations can be arranged into a "ladder-DES" constructs which
:  are especially-clean and familiar and seem to resist known attacks.
:  These constructs seem potentially stronger than normal DES and are
:  demonstrably faster than triple-DES.  Thus, ladder-DES could be a
:  reasonable candidate to replace DES.

These schemes have been the subject of much research in recent years.
The classic paper is [1], in which it is shown that three rounds in
the structure above are sufficient to prove perfectness (polynomial
time indistinguishability from a truly random permutation), provided
that the random functions are themselves perfect.

There have been many papers on schemes to reduce the key space by
using one of the pseudorandom functions more than once; a few examples
are given here.

Andrew.

[1] M. Luby and C. Rackoff, "How to construct pseudorandom
permutations from pseudorandom functions," SIAM J. Comput. vol 17,
pp. 373-386, 1988.

[2] Ulei M. Maurer, "A Simplified and Generalized Treatment of
Luby-Rackoff Pseudorandom Permutation Generators," Proc. EUROCRYPT
'92, pp. 239-255, 1993.

[3] Jacques Patarin, "How to construct pseudorandom and super
pseudorandom permutations from one single pseudorandom function,"
Proc. EUROCRYPT '92, pp. 256-266, 1993.

[4] Jacques Patarin, "New results on pseudorandom permutation
generators based on the DES scheme," Proc. CRYPTO '91, pp. 301-312,
1992.

[5] Josef Pieprzyk,, "How to construct Pseudorandom Permutations from
Single Pseudorandom Functions," Proc. EUROCRYPT '90, pp. 140-150,
1991.


-- 
"Always keep an open mind, but not so open that your brain falls out."