NP破译的Knapsack体制

A NEW KNAPSACK CRYPTOSYSTEM

本文提出一种新的Knapsack体制,其安全性将基于线性问题——一个非常困难问题的求解。同时指出通过(W,M)变换,新体制的安全性将主要依赖于矩阵复盖的NP——完全性问题。

This paper presents a new type of Knapsack cryptosystem.The security of the system rests in part on the difficulty of solving linear problem. If the system is transformed through (W,M), then the security only rests in part on a NP-completeness problem (Matrix Cover problem).