TY - JOUR
AU - Alpirez Bock, Estuardo
AU - Brzuska, Chris
AU - Lai, Russell W. F.
PY - 2023/08/31
Y2 - 2023/09/25
TI - On Provable White-Box Security in the Strong Incompressibility Model
JF - IACR Transactions on Cryptographic Hardware and Embedded Systems
JA - TCHES
VL - 2023
IS - 4
SE - Articles
DO - 10.46586/tches.v2023.i4.167-187
UR - https://tches.iacr.org/index.php/TCHES/article/view/11162
SP - 167-187
AB - <p><em>Incompressibility</em> 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 <em>strong incompressibility</em>, where a compressed program should not even help to <em>distinguish</em> 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<em> rate</em> is high.<br>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 <em>key-fixing</em>, 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 <em>random oracle</em> into an LK-IND-CPA-secure encryption scheme, circumventing the impossibility result by the use of an idealised model.<br>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.</p>
ER -