crmoreo.blogg.se

Merkle, R.C., Hellman, M.E.: Hiding Information and Signatures in Trapdoor Knapsacks. Mazo, J.E., Odlyzko, A.M.: Lattice Points in High-Dimensional Spheres. Journal of the Association for Computing Machinery 32(1), 229–246 (1985) Lagarias, J.C., Odlyzko, A.M.: Solving Low-Density Subset Sum Problems. Designs, Codes and Cryptography 43(1), 47–59 (2007) (Preliminary version appeared in 2004) Izu, T., Kogure, J., Koshiba, T., Shimoyama, T.: Low-Density Attack Revisited. Wiley-Interscience, Chichester (1991)Ĭover, C.M.: Enumerative Source Encoding. Computational Complexity 2, 111–128 (1992)Ĭover, T.M., Thomas, J.A.: Elements of Information Theory. Springer, Heidelberg (1985)Ĭoster, M.J., Joux, A., LaMacchia, B.A., Odlyzko, A.M., Schnorr, C.P., Stern, J.: Improved Low-Density Subset Sum Algorithms. 11–20 (1998)Ĭhor, B., Rivest, R.L.: A Knapsack-type Public Key Cryptosystem based on Arithmetic in Finite Fields. KeywordsĪjtai, M.: The Shortest Vector Problem in L 2 is NP-hard for Randomized Reductions. Next, we show that the critical bound goes to 1 if the Hamming weight decreases, which means that it is quite difficult to construct a low weight knapsack scheme which is supported by an argument of density. Furthermore, we show that if D < 0.8677, the knapsack scheme is solved by lattice attack. We obtain a critical bound of density which depends only on the ratio of the message length and its Hamming weight. Next, we derive conditions for our density so that a knapsack scheme is vulnerable to lattice attack. In this paper, we first introduce a new notion of density D, which naturally unifies the previous two densities. However, the usual density and the pseudo-density are not sufficient to measure the resistance to the lattice attack individually. In Asiacrypt2005, Nguyen and Stern introduced pseudo-density and proved that if the pseudo-density is low enough (even if the usual density is not low enough), the knapsack scheme can be broken by a single call of SVP/CVP oracle.

To prevent the lattice attack, Chor and Rivest proposed a low weight knapsack scheme, which made the density higher than critical density.

Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of its low density.