Paper 2022/1253

A Modular Approach to the Incompressibility of Block-Cipher-Based AEADs

Akinori Hosoyamada, NTT Social Informatics Laboratories
Takanori Isobe, University of Hyogo, National Institute of Information and Communications Technology, PRESTO
Yosuke Todo, NTT Social Informatics Laboratories
Kan Yasuda, NTT Social Informatics Laboratories

Incompressibility is one of the most fundamental security goals in white-box cryptography. Given recent advances in the design of efficient and incompressible block ciphers such as SPACE, SPNbox and WhiteBlock, we demonstrate the feasibility of reducing incompressible AEAD modes to incompressible block ciphers. We first observe that several existing AEAD modes of operation, including CCM, GCM(-SIV), and OCB, would be all insecure against white-box adversaries even when used with an incompressble block cipher. This motivates us to revisit and formalize incompressibility-based security definitions for AEAD schemes and for block ciphers, so that we become able to design modes and reduce their security to that of the underlying ciphers. Our new security notion for AEAD, which we name whPRI, is an extension of the pseudo-random injection security in the black-box setting. Similar security notions are also defined for other cryptosystems such as privacy-only encryption schemes. We emphasize that whPRI ensures quite strong authenticity against white-box adversaries: existential unforgeability beyond leakage. This contrasts sharply with previous notions which have ensured either no authenticity or only universal unforgeability. For the underlying ciphers we introduce a new notion of whPRP, which extends that of PRP in the black-box setting. Interestingly, our incompressibility reductions follow from a variant of public indifferentiability. In particular, we show that a practical whPRI-secure AEAD mode can be built from a whPRP-secure block cipher: We present a SIV-like composition of the sponge construction (utilizing a block cipher as its underlying primitive) with the counter mode and prove that such a construction is (in the variant sense) public indifferentiable from a random injection. To instantiate such an AEAD scheme, we propose a 256-bit variant of SPACE, based on our conjecture that SPACE should be a whPRP-secure cipher.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
white-box cryptography incompressibility mode of operation public indifferentiability
Contact author(s)
akinori hosoyamada bh @ hco ntt co jp
takanori isobe @ ai u-hyogo ac jp
yosuke todo xt @ hco ntt co jp
kan yasuda hy @ hco ntt co jp
2022-09-26: approved
2022-09-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Akinori Hosoyamada and Takanori Isobe and Yosuke Todo and Kan Yasuda},
      title = {A Modular Approach to the Incompressibility of Block-Cipher-Based AEADs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1253},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.