{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T04:45:52Z","timestamp":1693543552981},"reference-count":0,"publisher":"Universitatsbibliothek der Ruhr-Universitat Bochum","license":[{"start":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T00:00:00Z","timestamp":1693440000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["TCHES"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.46586\/tches.v2023.i4.167-187","type":"journal-article","created":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T09:34:53Z","timestamp":1693474493000},"page":"167-187","source":"Crossref","is-referenced-by-count":0,"title":["On Provable White-Box Security in the Strong Incompressibility Model"],"prefix":"10.46586","author":[{"given":"Estuardo","family":"Alpirez Bock","sequence":"first","affiliation":[]},{"given":"Chris","family":"Brzuska","sequence":"additional","affiliation":[]},{"given":"Russell W. F.","family":"Lai","sequence":"additional","affiliation":[]}],"member":"25480","published-online":{"date-parts":[[2023,8,31]]},"container-title":["IACR Transactions on Cryptographic Hardware and Embedded Systems"],"original-title":[],"link":[{"URL":"https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/download\/11162\/10601","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/download\/11162\/10601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T09:34:54Z","timestamp":1693474494000},"score":1,"resource":{"primary":{"URL":"https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/view\/11162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,31]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46586\/tches.v2023.i4.167-187","relation":{},"ISSN":["2569-2925"],"issn-type":[{"value":"2569-2925","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,31]]}}}