Attacking Tropical Stickel Protocol by MILP and Heuristic Optimization Techniques

Sulaiman Alhussaini; Serge˘ı Sergeev

Paper 2024/1169

Attacking Tropical Stickel Protocol by MILP and Heuristic Optimization Techniques

Sulaiman Alhussaini, University of Birmingham

Serge˘ı Sergeev

, University of Birmingham

Abstract

Known attacks on the tropical implementation of Stickel protocol involve solving a minimal covering problem, and this leads to an exponential growth in the time required to recover the secret key as the used polynomial degree increases. Consequently, it can be argued that Alice and Bob can still securely execute the protocol by utilizing very high polynomial degrees, a feasible approach due to the efficiency of tropical operations. The same is true for the implementation of Stickel protocol over some other semirings with idempotent addition (such as the max-min or fuzzy semiring). In this paper, we propose alternative methods to attacking Stickel protocol that avoid this minimal covering problem and the associated exponential time complexity. These methods involve framing the attacks as a mixed integer linear programming (MILP) problem or applying certain global optimization techniques.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: public key cryptography key exchange protocol cryptographic attack tropical cryptography
Contact author(s): saa399 @ student bham ac uk
s sergeev @ bham ac uk
History: 2024-07-22: approved; 2024-07-19: received; See all versions
Short URL: https://ia.cr/2024/1169
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1169,
      author = {Sulaiman Alhussaini and Serge˘ı Sergeev},
      title = {Attacking Tropical Stickel Protocol by {MILP} and Heuristic Optimization Techniques},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1169},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/1169}},
      url = {https://eprint.iacr.org/2024/1169}
}