Paper 2022/1244

A Modular Approach to the Security Analysis of Two-Permutation Constructions

Yu Long Chen, imec-COSIC, KU Leuven

Constructions based on two public permutation calls are very common in today’s cryptographic community. However, each time a new construction is introduced, a dedicated proof must be carried out to study the security of the construction. In this work, we propose a new tool to analyze the security of these constructions in a modular way. This tool is built on the idea of the classical mirror theory for block cipher based constructions, such that it can be used for security proofs in the ideal permutation model. We present different variants of this public permutation mirror theory such that it is suitable for different security notions. We also present a framework to use the new techniques, which provides the bad events that need to be excluded in order to apply the public permutation mirror theory. Furthermore, we showcase the new technique on three examples: the Tweakable Even-Mansour cipher by Cogliati et al. (CRYPTO ’15), the two permutation variant of the pEDM PRF by Dutta et al. (ToSC ’21(2)), and the two permutation variant of the nEHtM\(_p\) MAC algorithm by Dutta and Nandi (AFRICACRYPT ’20). With this new tool we prove the multi-user security of these constructions in a considerably simplified way.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
mirror theory two permutation calls constructions multi-user security modular framework
Contact author(s)
yulong chen @ kuleuven be
2022-09-19: approved
2022-09-19: received
See all versions
Short URL
No rights reserved


      author = {Yu Long Chen},
      title = {A Modular Approach to the Security Analysis of Two-Permutation Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1244},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.