Path: illuminati.io.com!uunet!in1.uu.net!panix!cmcl2!oitnews.harvard.edu!das-
+     news2.harvard.edu!cantaloupe.srv.cs.cmu.edu!ralf
From: ralf+@cs.cmu.edu (Ralf Brown)
Newsgroups: sci.crypt

Subject: Generalized Feistel Networks
Date: 2 Apr 1995 23:59:33 GMT
Organization: School of Computer Science, Carnegie Mellon
Lines: 49
Message-ID: <3lndp5$nm4@cantaloupe.srv.cs.cmu.edu>
NNTP-Posting-Host: b.gp.cs.cmu.edu


[Does anyone know if the following idea I just had has ever been used?  Would
it be more secure than a regular Feistel cipher?]

As many of you know, Feistel ciphers are based on repeated iterations
("rounds") of the following for the two halves A and B of a block of some
predetermined size:
        A' = B
        B' = f(A,B), for some invertible function f
with the decryption transform for A',B' being
        B = A'
        A = f'(B,B'), where f' is the inverse of f

This idea can be generalized to the N parts of a block (said block naturally
being larger than in the N=2 case normally used).  For instance, if N=4,
then the subblocks A,B,C,D of a block would be transformed as follows for
encryption:
        A' = D
        B' = f(A,B)
        C' = f(B,C)
        D' = f(C,D)
with decryption using
        D = A'
        C = f'(D,D')
        B = f'(C,C')
        A = f'(B,B')

For N subblocks in a block, a minimum of N rounds are required to process
each subblock uniformly through the network, at which point every subblock
of the output depends on every subblock of the input.

Although this approach roughly doubles computation compared to the standard
Feistel network (a total of M*(N-1) applications of the mixing function for
N parts processed through M rounds, compared to M*(N/2) applications), it
also diffuses the bits over a much larger block--where a 32-bit processor
would have used a 64-bit block, it could now use a 512-bit block with 16
rounds.

We can further generalize by using multiple mixing functions--there could
be up to N-1 distinct mixing functions applied in each round.  This will
naturally require careful design to avoid sets of functions which neutralize
each other.


Comments, criticisms?  (no flames, please, if I've rediscovered the obvious)
-- 
Internet: RALF+@CS.CMU.EDU  | The University would disclaim this if it knew...
FIDO: Ralf Brown 1:129/26.1 | "Determine that the thing can and shall be done,
BIT: RALF%CS.CMU.EDU@MITVMA | and then we shall find the way." Abraham Lincoln