Cryptanalysis of a knapsack-based probabilistic encryption scheme

Wang et al. [B. Wang, Q. Wu, Y. Hu, A knapsack-based probabilistic encryption scheme, Information Sciences 177(19) (2007) 3981-3994] proposed a high density knapsack-based probabilistic encryption scheme with non-binary coefficients. In this paper, we present a heuristic attack that can be used to recover the private key parameters from the known public key parameters. In particular, we show that the restrictions imposed on the system parameters allow the attacker to recover a short list of candidates for the first half of the public key. The second half of the public key can then be recovered using an attack based on lattice basis reduction. Finally, by encrypting an arbitrary plaintext using the known public key then decrypting the resulting ciphertext using these estimated candidate solutions, the right private key can be uniquely determined. (C) 2009 Elsevier Inc. All rights reserved.