On Provable White-Box Security in the Strong Incompressibility Model
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2023-08-31
Major/Subject
Mcode
Degree programme
Language
en
Pages
21
167-187
167-187
Series
IACR Transactions on Cryptographic Hardware and Embedded Systems, Volume 2023, issue 4
Abstract
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.Description
Publisher Copyright: © 2023, Ruhr-University of Bochum. All rights reserved.
Keywords
Bounded-Retrieval, Impossibility, Incompressibility, Leakage Resilience, Provable Security, White-Box Cryptography
Other note
Citation
Bock, E A, Brzuska, C & Lai, R W F 2023, ' On Provable White-Box Security in the Strong Incompressibility Model ', IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2023, no. 4, pp. 167-187 . https://doi.org/10.46586/tches.v2023.i4.167-187