Polynomial Tropical Key Exchange (PTKE): A Hybrid Post-Quantum Protocol

Abstract

The emergence of large-scale quantum computers threatens classical public-key cryptosystems based on integer Factorization and discrete logarithms. This paper introduces the Polynomial Tropical Key Exchange (PTKE), a novel hybrid key-exchange protocol that combines tropical algebra with standard symmetric cryptographic primitives. Unlike previous tropical schemes that rely on a single matrix power Ml, PTKE uses a secret tropical polynomial f(x)=⨁k=0d ckxk evaluated at a public matrix M, followed by multiplication with a secret commuting matrix A drawn from a prescribed commuting family. The security analysis introduces the Tropical Polynomial Factorization Problem (TPFP), a new structured decomposition problem associated with recovering private decompositions of PTKE public keys. While related tropical problems are known to be NP-hard, the precise computational complexity of TPFP remains open. Security is based on the working assumption that no efficient algorithm exists for solving protocol-generated instances of TPFP. We prove the correctness of the protocol and analyze its resistance to currently known tropical cryptanalytic attacks. No efficient quantum algorithm for solving PTKE instances is currently known. The protocol is integrated with SHA-256 and AES-256-GCM to derive standard symmetric session keys. Experimental results demonstrate that PTKE is practical for the proposed parameter ranges, making PTKE a promising direction for further research in post-quantum cryptography.