On the independence heuristic in the dual attack
Post-quantum cryptography deals with the development and analysis of cryptographic schemes that are assumed to be secure even against attackers with access to a powerful quantum computer. Along the main candidates for quantum-safe solutions are cryptographic schemes, whose security is based on class...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2025-07-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2024-0028 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849425417942859776 |
|---|---|
| author | Bashiri Kaveh Wiemers Andreas |
| author_facet | Bashiri Kaveh Wiemers Andreas |
| author_sort | Bashiri Kaveh |
| collection | DOAJ |
| description | Post-quantum cryptography deals with the development and analysis of cryptographic schemes that are assumed to be secure even against attackers with access to a powerful quantum computer. Along the main candidates for quantum-safe solutions are cryptographic schemes, whose security is based on classic lattice problems such as the bounded-distance decoding (BDD) problem or the learning with error problem. In this work, we contribute to the analysis of an attack category against these problems called dual attack. In recent years, a lot of notable progress was achieved in this topic. Our first contribution is to provide theoretical counterarguments against a so-called independence assumption, which was used in earlier works on this attack, and which was shown in a previous work to be contradicting practical experiments. Then, we provide estimates on the success probability and the cost of the dual attack against the decisional version of the BDD problem. These estimates are derived both rigorously and heuristically. Finally, we also provide experimental evidence that confirms these results. |
| format | Article |
| id | doaj-art-b119cc587c7d433983cef95e6a3aad09 |
| institution | Kabale University |
| issn | 1862-2984 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj-art-b119cc587c7d433983cef95e6a3aad092025-08-20T03:29:47ZengDe GruyterJournal of Mathematical Cryptology1862-29842025-07-01191p. 4031510.1515/jmc-2024-0028On the independence heuristic in the dual attackBashiri Kaveh0Wiemers Andreas1Bundesamt für Sicherheit in der Informationstechnik (BSI), Bonn, GermanyBundesamt für Sicherheit in der Informationstechnik (BSI), Bonn, GermanyPost-quantum cryptography deals with the development and analysis of cryptographic schemes that are assumed to be secure even against attackers with access to a powerful quantum computer. Along the main candidates for quantum-safe solutions are cryptographic schemes, whose security is based on classic lattice problems such as the bounded-distance decoding (BDD) problem or the learning with error problem. In this work, we contribute to the analysis of an attack category against these problems called dual attack. In recent years, a lot of notable progress was achieved in this topic. Our first contribution is to provide theoretical counterarguments against a so-called independence assumption, which was used in earlier works on this attack, and which was shown in a previous work to be contradicting practical experiments. Then, we provide estimates on the success probability and the cost of the dual attack against the decisional version of the BDD problem. These estimates are derived both rigorously and heuristically. Finally, we also provide experimental evidence that confirms these results.https://doi.org/10.1515/jmc-2024-0028dual attacklearning with errorslatticescryptanalysis06b9994a60 |
| spellingShingle | Bashiri Kaveh Wiemers Andreas On the independence heuristic in the dual attack Journal of Mathematical Cryptology dual attack learning with errors lattices cryptanalysis 06b99 94a60 |
| title | On the independence heuristic in the dual attack |
| title_full | On the independence heuristic in the dual attack |
| title_fullStr | On the independence heuristic in the dual attack |
| title_full_unstemmed | On the independence heuristic in the dual attack |
| title_short | On the independence heuristic in the dual attack |
| title_sort | on the independence heuristic in the dual attack |
| topic | dual attack learning with errors lattices cryptanalysis 06b99 94a60 |
| url | https://doi.org/10.1515/jmc-2024-0028 |
| work_keys_str_mv | AT bashirikaveh ontheindependenceheuristicinthedualattack AT wiemersandreas ontheindependenceheuristicinthedualattack |