Paper 2023/1007

On Provable White-Box Security in the Strong Incompressibility Model

Estuardo Alpirez Bock, Xiphera LTD
Chris Brzuska, Aalto University
Russell W. F. Lai, Aalto University

Incompressibility is a popular security notion for white-box cryptography and captures that a large encryption program cannot be compressed without losing functionality. Fouque, Karpman, Kirchner and Minaud (FKKM) defined strong incompressibility, where a compressed program should not even help to distinguish encryptions of two messages of equal length. Equivalently, the notion can be phrased as indistinguishability under chosen-plaintext attacks and key-leakage (LK-IND-CPA), where the leakage rate is high. In this paper, we show that LK-IND-CPA security with superlogarithmic-length leakage, and thus strong incompressibility, cannot be proven under standard (i.e. single-stage) assumptions, if the encryption scheme is key-fixing, i.e. a polynomial number of message-ciphertext pairs uniquely determine the key with high probability. Our impossibility result refutes a claim by FKKM that their big-key generation mechanism achieves strong incompressibility when combined with any PRG or any conventional encryption scheme, since the claim is not true for encryption schemes which are key-fixing (or for PRGs which are injective). In particular, we prove that the cipher block chaining (CBC) block cipher mode is key-fixing when modelling the cipher as a truly random permutation for each key. Subsequent to and inspired by our work, FKKM prove that their original big-key generation mechanism can be combined with a random oracle into an LK-IND-CPA-secure encryption scheme, circumventing the impossibility result by the use of an idealised model. Along the way, our work also helps clarifying the relations between incompressible white-box cryptography, big-key symmetric encryption, and general leakage resilient cryptography, and their limitations.

Available format(s)
Publication info
Published by the IACR in TCHES 2023
White-Box CryptographyIncompressibilityBounded-RetrievalLeakage ResilienceImpossibilityProvable Security
Contact author(s)
estuardo alpirezbock @ xiphera com
chris brzuska @ gmail com
russell lai @ aalto fi
2023-06-29: approved
2023-06-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Estuardo Alpirez Bock and Chris Brzuska and Russell W. F. Lai},
      title = {On Provable White-Box Security in the Strong Incompressibility Model},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1007},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.