Akiyama et al. (Int. J. Math. Indust., 2019) proposed a post-quantum key exchange protocol that is based on the hardness of solving a system of multivariate non-linear polynomial equations but has a design strategy different from ordinary multivariate cryptography. Their protocol has two versions, an original one and a modified one, where the modified one has a trade-off that its security is strengthened while it has non-zero error probability in establishing a common key. In fact, the evaluation in their paper suggests that the probability of failing to establish a common key by the modified protocol with the proposed parameter set is impractically high. In this paper, we improve the success probability of Akiyama et al.'s modified key exchange protocol significantly while keeping the security, by restricting each component of the correct common key from the whole of the coefficient field to its small subset. We give theoretical and experimental evaluations showing that our proposed parameter set for our protocol is expected to achieve both failure probability $2^{-120}$ and $128$-bit security level.
翻译:Akiyama 等人(Int. J. Math. Indust., 2019) 提出了一个后二次关键交换协议,该协议基于解决多变量非线性多元方程式系统的难度,但有一个与普通多变量加密法不同的设计策略。其协议有两个版本,一个原始版本和一个修改版本,其中修改后的版本有一个权衡,即其安全得到加强,而其建立共同钥匙的概率为非零误差概率。事实上,他们文件中的评估表明,修改后的协议无法用拟议参数集建立共同钥匙的可能性不切实际地高。在本文件中,我们大大提高了Akiyama 等人修改的关键交换协议的成功概率,同时保持安全,将整个系数字段的正确共同钥匙的每个组成部分限制在小部分。我们给出了理论和实验性评估,表明我们为协议设定的拟议参数有望实现故障概率2 ⁇ -120美元和128美元的安全水平。