Equivalent key attack against a public-key cryptosystem based on subset sum problem

摘要

The decisional version and computational version of the subset sum problem are known to be NP-complete and NP-hard. At International Symposium on Information Theory and its Applications 2012, Yasuyuki Murakami, Shinsuke Hamasho and Masao Kasahara presented a knapsack scheme based on the decisional version of the odd order subset sum problem. They claimed that the public sequence is indistinguishable from uniformly distributed sequences. In this study, the authors present an equivalent key attack against this scheme. More precisely, they firstly observe that there are many groups of equivalent keys, which satisfy several necessary conditions. Subsequently, they show that one can recover a group of equivalent keys by using the orthogonal lattice technique. The feasibility of the attack is validated by the experimental data when the bit length of secret keys is not too large. Hence, the security of the proposed scheme is overestimated.