Paper 2026/222

ITSAKE: an unconditionally secure authenticated key establishment protocol

Abstract

We introduce $\textrm{ITSAKE}$, a 2-message Information-Theoretic Secure Authenticated Key Establishment protocol. That is, $\textrm{ITSAKE}$ is a protocol to establish keys between two parties from a pre-shared secret. Beside correctness and key indistinguishability, it offers entity authentication and perfect forward secrecy. Moreover, synchronization problems are avoided because $\textrm{ITSAKE}$ satisfies the weak synchronization robustness property. The main advantage of $\textrm{ITSAKE}$ is that all these security properties are unconditionally proved, i.e., they do not rely on unproven mathematical assumptions or on limitations on the power of the adversary. We provide complete and detailed security proofs in a well-defined multi-party security model for symmetric-key authenticated key establishment protocols admitting concurrent runs in which the adversary has a complete control on the communication channel. The main drawback of $\textrm{ITSAKE}$ is the length of the pre-shared keys that the parties need to hold. To give an example, we present an instantiation of the protocol for which the master-key is just slightly longer than the total keying material that can be established. At this cost, one obtains fresher keys, authenticity of the partner, information-theoretic security, and avoids synchronization problems. $\textrm{ITSAKE}$ is meant to be used to protect highly confidential information, for which trust in unproven assumptions or in limitations on the adversary is undesired. Moreover, as memory devices are typically much less expensive than dedicated quantum apparatus, and as physical key exchanges performed occasionally may be more convenient than maintaining those quantum apparatus, $\textrm{ITSAKE}$ is a practical and cost-effective alternative to Quantum Key Distribution (QKD) in many of its potential use-cases, while offering the same security guarantees. Thus, $\textrm{ITSAKE}$ challenges the necessity of QKD in most settings where these guarantees are the main objective.