Analysis of the Success Rate of the LLL Lattice Basis Reduction

The security of an MH plaintext is intended to be based on the subset sum problem (SSP). However, when the density of a knapsack is less than 0.9408, SSP can be solved in polynomial time through the LLL lattice basis reduction algorithm for seeking the shortest non-zero vector in a lattice. In this paper, we discuss the method of attack on the MH cryptosystem, and analyze the effect of the length and density of a knapsack on the success rate of the LLL lattice basis reduction. In theory, when the density is less than 0.9408, the success rate is high. From the data we get by experiments, we observe that when the density is fixed and the length is increased, the success rate decreases, and when the length is fixed and the density is increased, the success rate also decreases. Concretely, when the length is 80 and the density is 0.8, the success rate is closed to 50%, when the density is increased to 0.952 and the length remains unchanged, the rate is less than 50%, and when the density is increased to 1.509 and the length remains unchanged, the rate decreases to 35%.