Cryptanalysis of the quantum public-key cryptosystem OTU under heuristics from Szemerédi-type statements
Cryptanalysis of the quantum public-key cryptosystem OTU under heuristics from Szemerédi-type statements
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Shoichi Kamada
中科院分区：
文献类型：
--
作者：
Shoichi Kamada
。背包密码是公钥密码，其安全性主要取决于子集和问题的难度。许多背包方案都可以通过低密度攻击来破解，低密度攻击是利用格子中最短向量或最近向量对应于子集和问题的解的情况的攻击方法。对于子集和问题的随机实例的解的汉明权是任意的情况，如果密度小于0.9408，则该实例几乎可以通过单次调用点阵预言机来求解。 Coster 等人从理论上证明了这一事实。在 Crypto 2000 中，Okamoto、Tanaka 和 Uchiyama 引入了量子公钥密码系统的概念，并提出了背包密码系统，即所谓的 OTU 密码系统。然而，没有已知的算法可以破解 OTU 密码系统。在本文中，我们引入了 Szemer´edi 型假设，它是对 Szemer´edi 算术级数定理陈述的模仿。从这个数学角度来看，我们清楚什么是平均情况和最坏情况。对于低密度攻击，我们为正交格提供比高斯启发式更好的启发式。因此，我们表明 OTU 方案可以在一些启发式假设下被打破。
. The knapsack cryptography is the public-key cryptography whose security depends mainly on the hardness of the subset sum problem. Many of knapsack schemes were able to break by low-density attacks, which are attack methods to use the situation that a shortest vector or a closest vector in a lattice corresponds to a solution of the subset sum problem. For the case when the Hamming weight of a so-lution for a random instance of the subset sum problem is arbitrary, if the density is less than 0.9408, then the instance can be solvable almost surely by a single call of lattice oracle. This fact was theoretically shown by Coster et al. In Crypto 2000, Okamoto, Tanaka and Uchiyama introduced the concept of quantum public key cryptosystems and proposed a knapsack cryptosystem, so-called OTU cryptosystem. However, no known algorithm breaks the OTU cryptosystem. In this paper, we introduced Szemer´edi-type assumptions, which are the imitations of the statement of Szemer´edi’s theorem on arithmetic pro-gressions. From this mathematical point of view, we make clear what the average case and the worst case are. For low density attacks, we give better heuristics for orthogonal lattices than Gaussian heuristics. Consequently, we show that the OTU scheme can be broken under some heuristic assumptions.