In this paper, we first prove beyond-birthyday-bound security for the Misty structure. Specifically, we show that an r-round Misty structure is secure against CCA attacks up to O(2 rn r+7 ) query complexity, where n is the size of each round permutation. So for any > 0, a sufficient number of rounds would guarantee the security of the Misty structure up to 2n(1− ) query complexity.