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