International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Akinori Hosoyamada , NTT Social Informatics Laboratories
Takanori Isobe , University of Hyogo / NICT / PRESTO
Yosuke Todo , NTT Social Informatics Laboratories
Kan Yasuda , NTT Social Informatics Laboratories
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: 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.
Video from ASIACRYPT 2022
  title={A Modular Approach to the Incompressibility of Block-Cipher-Based AEADs},
  author={Akinori Hosoyamada and Takanori Isobe and Yosuke Todo and Kan Yasuda},