Construction of pseudorandom permutations

✍ Scribed by Yasuhiro Ohnishi; Akira Maruoka

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 682 KB
• Volume: 25
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690250903

✦ Synopsis

Abstract

The permutation from {0, 1}^2n^ to {0, 1}^2n^ represented by S(f) in DES (Data Encryption Standard) is used as the basic operation. Let f be a function from {0, 1}^n^ to {0, 1}^n^ and ⊕ denote bitwise exclusive or. Then S(f) is defined S(f)(L.R) = R.[L⊕f(R)] where L, R ϵ {0, 1}^n^, Moreover, let S(f~2~, f~1~, f~o~) denote the composition of S(f~2~, S(f~1~) and S(f~o~), and {S(f~2~, f~1~,f~o~)} denote a set of S(f~2~,f~1~,f~o~) obtained when f~o~,f~1~ and f~2~ are chosen randomly from a set of pseudorandom functions. Luby et al. have shown that {S(f~2~,f~1~,f~o~)} is pseudorandom.

This paper investigates the case in which there are two different pseudorandom functions and shows that while {{S(f~1~, f~1,~, f~o~)} and {S(f~1~, f~o~, f~o~)} are pseudorandom, {S(f~o~, f~1~, f~o~)} is not.