Gröbner Basis Cryptanalysis of Ciminion and Hydra
Ciminion and Hydra are two recently introduced symmetric key Pseudo- Random Functions for Multi-Party Computation applications. For efficiency, both primitives utilize quadratic permutations at round level. Therefore, polynomial system solving-based attacks pose a serious threat to these primitives...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2025-03-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/12076 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850028024433475584 |
|---|---|
| author | Matthias Johann Steiner |
| author_facet | Matthias Johann Steiner |
| author_sort | Matthias Johann Steiner |
| collection | DOAJ |
| description |
Ciminion and Hydra are two recently introduced symmetric key Pseudo- Random Functions for Multi-Party Computation applications. For efficiency, both primitives utilize quadratic permutations at round level. Therefore, polynomial system solving-based attacks pose a serious threat to these primitives. For Ciminion, we construct a quadratic degree reverse lexicographic (DRL) Gröbner basis for the iterated polynomial model via linear transformations. With the Gröbner basis we can simplify cryptanalysis, as we no longer need to impose genericity assumptions to derive complexity estimates. For Hydra, with the help of a computer algebra program like SageMath we construct a DRL Gröbner basis for the iterated model via linear transformations and a linear change of coordinates. In the Hydra proposal it was claimed that rH = 31 rounds are sufficient to provide 128 bits of security against Gröbner basis attacks for an ideal adversary with ω = 2. However, via our Hydra Gröbner basis standard term order conversion to a lexicographic (LEX) Gröbner basis requires just 126 bits with ω = 2. Moreover, using a dedicated polynomial system solving technique up to rH = 33 rounds can be attacked below 128 bits for an ideal adversary.
|
| format | Article |
| id | doaj-art-accd099d9fdc45a3bf9b9fcd8d7cf47a |
| institution | DOAJ |
| issn | 2519-173X |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj-art-accd099d9fdc45a3bf9b9fcd8d7cf47a2025-08-20T02:59:57ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2025-03-012025110.46586/tosc.v2025.i1.240-275Gröbner Basis Cryptanalysis of Ciminion and HydraMatthias Johann Steiner0https://orcid.org/0000-0001-5206-6579Alpen-Adria-Universität Klagenfurt, Klagenfurt am Wörthersee, Austria Ciminion and Hydra are two recently introduced symmetric key Pseudo- Random Functions for Multi-Party Computation applications. For efficiency, both primitives utilize quadratic permutations at round level. Therefore, polynomial system solving-based attacks pose a serious threat to these primitives. For Ciminion, we construct a quadratic degree reverse lexicographic (DRL) Gröbner basis for the iterated polynomial model via linear transformations. With the Gröbner basis we can simplify cryptanalysis, as we no longer need to impose genericity assumptions to derive complexity estimates. For Hydra, with the help of a computer algebra program like SageMath we construct a DRL Gröbner basis for the iterated model via linear transformations and a linear change of coordinates. In the Hydra proposal it was claimed that rH = 31 rounds are sufficient to provide 128 bits of security against Gröbner basis attacks for an ideal adversary with ω = 2. However, via our Hydra Gröbner basis standard term order conversion to a lexicographic (LEX) Gröbner basis requires just 126 bits with ω = 2. Moreover, using a dedicated polynomial system solving technique up to rH = 33 rounds can be attacked below 128 bits for an ideal adversary. https://tosc.iacr.org/index.php/ToSC/article/view/12076Gröbner basisCiminionHydra |
| spellingShingle | Matthias Johann Steiner Gröbner Basis Cryptanalysis of Ciminion and Hydra IACR Transactions on Symmetric Cryptology Gröbner basis Ciminion Hydra |
| title | Gröbner Basis Cryptanalysis of Ciminion and Hydra |
| title_full | Gröbner Basis Cryptanalysis of Ciminion and Hydra |
| title_fullStr | Gröbner Basis Cryptanalysis of Ciminion and Hydra |
| title_full_unstemmed | Gröbner Basis Cryptanalysis of Ciminion and Hydra |
| title_short | Gröbner Basis Cryptanalysis of Ciminion and Hydra |
| title_sort | grobner basis cryptanalysis of ciminion and hydra |
| topic | Gröbner basis Ciminion Hydra |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/12076 |
| work_keys_str_mv | AT matthiasjohannsteiner grobnerbasiscryptanalysisofciminionandhydra |