Improved cryptanalysis of a knapsack-based probabilistic encryption scheme

Wang et al. [B. Wang, Q. Wu, Y. Hu, Information Sciences 177 (2007)] proposed a knapsack-based probabilistic encryption scheme with non-binary coefficients which enjoys a high density larger than 1.06 in the worst case. In this work, we successfully attack this scheme by showing that a public key and a restriction on system parameters allow the attacker to recover a secret key in a cubic time complexity using modular equations. This approach is much more efficient than the previous attack by Youssef [A.M. Youssef, Information Sciences 179 (2009)], in which lattice basis reductions are used. Recovering secret keys can be done within 4 h and 4 days when n = 100 and 200, respectively. A simple modification that helps resist known attacks is also discussed.