Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple Collisions
Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framewor...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2024-03-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/11407 |
| _version_ | 1797283879731593216 |
|---|---|
| author | Fukang Liu Abul Kalam Santanu Sarkar Willi Meier |
| author_facet | Fukang Liu Abul Kalam Santanu Sarkar Willi Meier |
| author_sort | Fukang Liu |
| collection | DOAJ |
| description |
Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important technique in FHE to address the issue of ciphertext expansion and reduce the client-side computational overhead. To apply the transciphering framework to the CKKS FHE scheme, a new transciphering framework called the Real-to-Finite-Field (RtF) framework and a corresponding FHE-friendly symmetric-key primitive called HERA were proposed at ASIACRYPT 2021. Although HERA has a very similar structure to AES, it is considerably different in the following aspects: 1) the power map x → x3 is used as the S-box; 2) a randomized key schedule is used; 3) it is over a prime field Fp with p > 216. In this work, we perform the first third-party cryptanalysis of HERA, by showing how to mount new algebraic attacks with multiple collisions in the round keys. Specifically, according to the special way to randomize the round keys in HERA, we find it possible to peel off the last nonlinear layer by using collisions in the last-round key and a simple property of the power map. In this way, we could construct an overdefined system of equations of a much lower degree in the key, and efficiently solve the system via the linearization technique. As a esult, for HERA with 192 and 256 bits of security, respectively, we could break some parameters under the same assumption made by designers that the algebra constant ω for Gaussian elimination is ω = 2, i.e., Gaussian elimination on an n × n matrix takes O(nω) field operations. If using more conservative choices like ω ∈ {2.8, 3}, our attacks can also successfully reduce the security margins of some variants of HERA to only 1 round. However, the security of HERA with 80 and 128 bits of security is not affected by our attacks due to the high cost to find multiple collisions. In any case, our attacks reveal a weakness of HERA caused by the randomized key schedule and its small state size.
|
| first_indexed | 2024-03-07T17:38:12Z |
| format | Article |
| id | doaj.art-b0d55b52d5a2447fa98f11f94969e4f0 |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-03-07T17:38:12Z |
| publishDate | 2024-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-b0d55b52d5a2447fa98f11f94969e4f02024-03-02T16:23:06ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2024-03-012024110.46586/tosc.v2024.i1.214-233Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple CollisionsFukang Liu0Abul Kalam1Santanu Sarkar2Willi Meier3Tokyo Institute of Technology, Tokyo, JapanIndian Institute of Technology Madras, Chennai, IndiaIndian Institute of Technology Madras, Chennai, IndiaUniversity of Applied Sciences and Arts Northwestern Switzerland (FHNW), Windisch, Switzerland Fully homomorphic encryption (FHE) is an advanced cryptography technique to allow computations (i.e., addition and multiplication) over encrypted data. After years of effort, the performance of FHE has been significantly improved and it has moved from theory to practice. The transciphering framework is another important technique in FHE to address the issue of ciphertext expansion and reduce the client-side computational overhead. To apply the transciphering framework to the CKKS FHE scheme, a new transciphering framework called the Real-to-Finite-Field (RtF) framework and a corresponding FHE-friendly symmetric-key primitive called HERA were proposed at ASIACRYPT 2021. Although HERA has a very similar structure to AES, it is considerably different in the following aspects: 1) the power map x → x3 is used as the S-box; 2) a randomized key schedule is used; 3) it is over a prime field Fp with p > 216. In this work, we perform the first third-party cryptanalysis of HERA, by showing how to mount new algebraic attacks with multiple collisions in the round keys. Specifically, according to the special way to randomize the round keys in HERA, we find it possible to peel off the last nonlinear layer by using collisions in the last-round key and a simple property of the power map. In this way, we could construct an overdefined system of equations of a much lower degree in the key, and efficiently solve the system via the linearization technique. As a esult, for HERA with 192 and 256 bits of security, respectively, we could break some parameters under the same assumption made by designers that the algebra constant ω for Gaussian elimination is ω = 2, i.e., Gaussian elimination on an n × n matrix takes O(nω) field operations. If using more conservative choices like ω ∈ {2.8, 3}, our attacks can also successfully reduce the security margins of some variants of HERA to only 1 round. However, the security of HERA with 80 and 128 bits of security is not affected by our attacks due to the high cost to find multiple collisions. In any case, our attacks reveal a weakness of HERA caused by the randomized key schedule and its small state size. https://tosc.iacr.org/index.php/ToSC/article/view/11407HERAalgebraic attackmultiple collisionsrandomized key schedule |
| spellingShingle | Fukang Liu Abul Kalam Santanu Sarkar Willi Meier Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple Collisions IACR Transactions on Symmetric Cryptology HERA algebraic attack multiple collisions randomized key schedule |
| title | Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple Collisions |
| title_full | Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple Collisions |
| title_fullStr | Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple Collisions |
| title_full_unstemmed | Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple Collisions |
| title_short | Algebraic Attack on FHE-Friendly Cipher HERA Using Multiple Collisions |
| title_sort | algebraic attack on fhe friendly cipher hera using multiple collisions |
| topic | HERA algebraic attack multiple collisions randomized key schedule |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/11407 |
| work_keys_str_mv | AT fukangliu algebraicattackonfhefriendlycipherherausingmultiplecollisions AT abulkalam algebraicattackonfhefriendlycipherherausingmultiplecollisions AT santanusarkar algebraicattackonfhefriendlycipherherausingmultiplecollisions AT willimeier algebraicattackonfhefriendlycipherherausingmultiplecollisions |