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

##### 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.

Available format(s)
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Keywords
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
History
2022-09-26: approved
See all versions
Short URL
https://ia.cr/2022/1253

CC BY

BibTeX

@misc{cryptoeprint:2022/1253,
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{https://eprint.iacr.org/2022/1253}},
url = {https://eprint.iacr.org/2022/1253}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.