Paper 2025/2182
Cryptanalysis on Asymmetric Structured Key Agreement Schemes
, Tokyo University of ScienceAbstract
We study several asymmetric structured key agreement schemes based on noncommutative matrix operations, including the recent proposal of Lizama as well as the strongly asymmetric algorithms SAA-3 and SAA-5 of Accardi et al.\ We place them in a common algebraic framework for public key agreement and identify simple structural conditions under which an eavesdropper can reconstruct an effective key-derivation map and reduce key recovery to solving linear systems over finite fields. We then show that the three matrix-based schemes mentioned above all instantiate our algebraic framework and can therefore be broken in polynomial time from public information alone. In particular, their security reduce to the hardness of linear-algebraic problems and does not exceed that of the underlying discrete logarithm problem. Our results demonstrate that the weakness of these schemes is structural rather than parametric, and that minor algebraic modifications are insufficient to repair them.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- CryptoanalysisAsymmetric Key AgreementMatrix-based key agreementNon-commutative
- Contact author(s)
- kjimbo @ rs tus ac jp
- History
- 2025-12-02: approved
- 2025-12-02: received
- See all versions
- Short URL
- https://ia.cr/2025/2182
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/2182,
author = {Koki Jimbo},
title = {Cryptanalysis on Asymmetric Structured Key Agreement Schemes},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2182},
year = {2025},
url = {https://eprint.iacr.org/2025/2182}
}
