New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting
The security of the post-quantum signature scheme Picnic is highly related to the difficulty of recovering the secret key of LowMC from a single plaintext-ciphertext pair. Since Picnic is one of the alternate third-round candidates in NIST post-quantum cryptography standardization process, it has b...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2022-09-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://ojs-dev.ub.rub.de/index.php/ToSC/article/view/9851 |
| _version_ | 1797690102918414336 |
|---|---|
| author | Fukang Liu Willi Meier Santanu Sarkar Takanori Isobe |
| author_facet | Fukang Liu Willi Meier Santanu Sarkar Takanori Isobe |
| author_sort | Fukang Liu |
| collection | DOAJ |
| description |
The security of the post-quantum signature scheme Picnic is highly related to the difficulty of recovering the secret key of LowMC from a single plaintext-ciphertext pair. Since Picnic is one of the alternate third-round candidates in NIST post-quantum cryptography standardization process, it has become urgent and important to evaluate the security of LowMC in the Picnic setting. The best attacks on LowMC with full S-box layers used in Picnic3 were achieved with Dinur’s algorithm. For LowMC with partial nonlinear layers, e.g. 10 S-boxes per round adopted in Picnic2, the best attacks on LowMC were published by Banik et al. with the meet-in-the-middle (MITM) method.
In this paper, we improve the attacks on LowMC in a model where memory consumption is costly. First, a new attack on 3-round LowMC with full S-box layers with negligible memory complexity is found, which can outperform Bouillaguet et al.’s fast exhaustive search attack and can achieve better time-memory tradeoffs than Dinur’s algorithm. Second, we extend the 3-round attack to 4 rounds to significantly reduce the memory complexity of Dinur’s algorithm at the sacrifice of a small factor of time complexity. For LowMC instances with 1 S-box per round, our attacks are shown to be much faster than the MITM attacks. For LowMC instances with 10 S-boxes per round, we can reduce the memory complexity from 32GB (238 bits) to only 256KB (221 bits) using our new algebraic attacks rather than the MITM attacks, while the time complexity of our attacks is about 23.2 ∼ 25 times higher than that of the MITM attacks. A notable feature of our new attacks (apart from the 4-round attack) is their simplicity. Specifically, only some basic linear algebra is required to understand them and they can be easily implemented.
|
| first_indexed | 2024-03-12T01:54:43Z |
| format | Article |
| id | doaj.art-e6b298044b2c4fa6831f6813594f3b73 |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-03-12T01:54:43Z |
| publishDate | 2022-09-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-e6b298044b2c4fa6831f6813594f3b732023-09-08T07:01:06ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2022-09-012022310.46586/tosc.v2022.i3.102-122New Low-Memory Algebraic Attacks on LowMC in the Picnic SettingFukang Liu0Willi Meier1Santanu Sarkar2Takanori Isobe3University of Hyogo, Hyogo, JapanUniversity of Applied Sciences and Arts Northwestern Switzerland (FHNW), Windisch, SwitzerlandIndian Institute of Technology Madras, Chennai, IndiaUniversity of Hyogo, Hyogo, Japan; National Institute of Information and Communications Technology (NICT), Tokyo, Japan; PRESTO, Japan Science and Technology Agency, Tokyo, Japan The security of the post-quantum signature scheme Picnic is highly related to the difficulty of recovering the secret key of LowMC from a single plaintext-ciphertext pair. Since Picnic is one of the alternate third-round candidates in NIST post-quantum cryptography standardization process, it has become urgent and important to evaluate the security of LowMC in the Picnic setting. The best attacks on LowMC with full S-box layers used in Picnic3 were achieved with Dinur’s algorithm. For LowMC with partial nonlinear layers, e.g. 10 S-boxes per round adopted in Picnic2, the best attacks on LowMC were published by Banik et al. with the meet-in-the-middle (MITM) method. In this paper, we improve the attacks on LowMC in a model where memory consumption is costly. First, a new attack on 3-round LowMC with full S-box layers with negligible memory complexity is found, which can outperform Bouillaguet et al.’s fast exhaustive search attack and can achieve better time-memory tradeoffs than Dinur’s algorithm. Second, we extend the 3-round attack to 4 rounds to significantly reduce the memory complexity of Dinur’s algorithm at the sacrifice of a small factor of time complexity. For LowMC instances with 1 S-box per round, our attacks are shown to be much faster than the MITM attacks. For LowMC instances with 10 S-boxes per round, we can reduce the memory complexity from 32GB (238 bits) to only 256KB (221 bits) using our new algebraic attacks rather than the MITM attacks, while the time complexity of our attacks is about 23.2 ∼ 25 times higher than that of the MITM attacks. A notable feature of our new attacks (apart from the 4-round attack) is their simplicity. Specifically, only some basic linear algebra is required to understand them and they can be easily implemented. https://ojs-dev.ub.rub.de/index.php/ToSC/article/view/9851LowMCPicnicpolynomial methodalgebraic attackcrossbred algorithmlow memory |
| spellingShingle | Fukang Liu Willi Meier Santanu Sarkar Takanori Isobe New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting IACR Transactions on Symmetric Cryptology LowMC Picnic polynomial method algebraic attack crossbred algorithm low memory |
| title | New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting |
| title_full | New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting |
| title_fullStr | New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting |
| title_full_unstemmed | New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting |
| title_short | New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting |
| title_sort | new low memory algebraic attacks on lowmc in the picnic setting |
| topic | LowMC Picnic polynomial method algebraic attack crossbred algorithm low memory |
| url | https://ojs-dev.ub.rub.de/index.php/ToSC/article/view/9851 |
| work_keys_str_mv | AT fukangliu newlowmemoryalgebraicattacksonlowmcinthepicnicsetting AT willimeier newlowmemoryalgebraicattacksonlowmcinthepicnicsetting AT santanusarkar newlowmemoryalgebraicattacksonlowmcinthepicnicsetting AT takanoriisobe newlowmemoryalgebraicattacksonlowmcinthepicnicsetting |