Post-Quantum Static-Static Key Agreement Using Multiple Protocol Instances

Some key agreement protocols leak information about secret keys if dishonest participants use specialized public keys. We formalize these protocols and attacks, and present a generic transformation that can be made to such key agreement protocols to resist such attacks. Simply put, each party generates k different keys, and two parties perform key agreement using all k(2) combinations of their individual keys. We consider this transformation in the context of various post-quantum key agreement schemes and analyze the attacker's success probabilities (which depend on the details of the underlying key agreement protocol) to determine the necessary parameter sizes for 128-bit security. Our transformation increases key sizes by a factor of k and computation times by k(2), which represents a significant cost-but nevertheless still feasible. Our transformation is particularly well-suited to supersingular isogeny Diffie-Hellman, in which one can take k = 113 instead of the usual k = 256 at the 128-bit quantum security level. These results represent a potential path forward towards solving the open problem of securing long-term static-static key exchange against quantum adversaries.

如果不诚实的参与者使用特殊的公钥，一些密钥协商协议会泄露有关密钥的信息。我们将这些协议和攻击形式化，并提出一种可对这类密钥协商协议进行的通用转换，以抵御此类攻击。简而言之，各方生成k个不同的密钥，双方使用其各自密钥的所有k²种组合来执行密钥协商。我们在各种后量子密钥协商方案的背景下考虑这种转换，并分析攻击者的成功概率（这取决于基础密钥协商协议的细节），以确定实现128位安全性所需的参数大小。我们的转换使密钥大小增加了k倍，计算时间增加了k²倍，这是一项重大成本——但仍然可行。我们的转换特别适用于超奇异同源迪菲 - 赫尔曼（supersingular isogeny Diffie - Hellman），在128位量子安全级别下，其中可以取k = 113，而不是通常的k = 256。这些结果为解决针对量子对手保护长期静态 - 静态密钥交换这一开放问题提供了一条潜在的前进路径。