On Provable White-Box Security in the Strong Incompressibility Model
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-08-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/11162 |
| _version_ | 1797718860850266112 |
|---|---|
| author | Estuardo Alpirez Bock Chris Brzuska Russell W. F. Lai |
| author_facet | Estuardo Alpirez Bock Chris Brzuska Russell W. F. Lai |
| author_sort | Estuardo Alpirez Bock |
| collection | DOAJ |
| description |
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.
|
| first_indexed | 2024-03-12T08:56:22Z |
| format | Article |
| id | doaj.art-ff4106cff73147e89c5175de651ebc5c |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-03-12T08:56:22Z |
| publishDate | 2023-08-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-ff4106cff73147e89c5175de651ebc5c2023-09-02T16:01:07ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252023-08-012023410.46586/tches.v2023.i4.167-187On Provable White-Box Security in the Strong Incompressibility ModelEstuardo Alpirez Bock0Chris Brzuska1Russell W. F. Lai2Xiphera LTD, Espoo, FinlandAalto University, Espoo, FinlandAalto University, Espoo, Finland 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. https://tches.iacr.org/index.php/TCHES/article/view/11162White-Box CryptographyIncompressibilityBounded-RetrievalLeakage ResilienceImpossibilityProvable Security |
| spellingShingle | Estuardo Alpirez Bock Chris Brzuska Russell W. F. Lai On Provable White-Box Security in the Strong Incompressibility Model Transactions on Cryptographic Hardware and Embedded Systems White-Box Cryptography Incompressibility Bounded-Retrieval Leakage Resilience Impossibility Provable Security |
| title | On Provable White-Box Security in the Strong Incompressibility Model |
| title_full | On Provable White-Box Security in the Strong Incompressibility Model |
| title_fullStr | On Provable White-Box Security in the Strong Incompressibility Model |
| title_full_unstemmed | On Provable White-Box Security in the Strong Incompressibility Model |
| title_short | On Provable White-Box Security in the Strong Incompressibility Model |
| title_sort | on provable white box security in the strong incompressibility model |
| topic | White-Box Cryptography Incompressibility Bounded-Retrieval Leakage Resilience Impossibility Provable Security |
| url | https://tches.iacr.org/index.php/TCHES/article/view/11162 |
| work_keys_str_mv | AT estuardoalpirezbock onprovablewhiteboxsecurityinthestrongincompressibilitymodel AT chrisbrzuska onprovablewhiteboxsecurityinthestrongincompressibilitymodel AT russellwflai onprovablewhiteboxsecurityinthestrongincompressibilitymodel |