Security of the Misty Structure Using Involutions as Round Functions

Jooyoung LEE  Bonwook KOO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.9   pp.1612-1619
Publication Date: 2010/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.1612
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Misty structure,  involution,  pseudorandomness,  

Full Text: PDF(996.1KB)>>
Buy this Article

In this paper, we study the security of the Misty structure, where each round function is chosen at random from the set of involutions. Based on the game-playing framework, we prove the pseudorandomness of the 3-round R-Misty structure and the 4-round L-Misty structure as well as the super-pseudorandomness of the 5-round R-Misty structure for m 2n/2, where m denotes the number of queries and 2n denotes the block size. We also give similar results for the Misty structures such that each round function is chosen at random from the set of involutions with a constant number of fixed points. Our results generalize the results of giving the first construction of a (strong) pseudorandom permutation based on random involutions (without any restriction on the number of fixed points), and suggest a new criterion for design of block ciphers in an involutional Misty structure that each round function should have a constant number of fixed points.