The decision version and the computational version of the subset sum problem are known to be NPcomplete and NPhard, respectively. The conventional knapsack schemes are based on the difficulty of the computational version of the subset sum problem. In this paper, we shall propose a new knapsack scheme which is based on not computational version but on decision version of the subset sum problem. In the proposed scheme, the public sequence would be indistinguishable from uniformly distributed sequence. We shall discuss on the security of the proposed scheme and show that the proposed scheme is secure against the conventional attacks.
展开▼
