Cryptology ePrint Archive: Report 2021/675

3-round Feistel is Not Superpseudorandom Over Any Group

Hector B. Hougaard

Abstract: Luby and Rackoff used a Feistel cipher over bit strings to construct a pseudorandom permutation from pseudorandom functions in 1988 and in 2002, Patel, Ramzan, and Sundaram generalized the construction to arbitrary abelian groups. They showed that the 3-round Feistel cipher is not superpseudorandom over abelian groups but left as an open problem a proof for non-abelian groups. We give this proof.

Keywords: Feistel, non-abelian group, pseudorandom.

Category / Keywords: cryptographic protocols / Feistel, non-abelian group, pseudorandom

Date: received 24 May 2021

Contact author: hector at cy2sec comm eng osaka-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20210525:071001 (All versions of this report)

Short URL: ia.cr/2021/675


[ Cryptology ePrint archive ]