Cryptanalysis of two combinatorial public key cryptosystems

In this article, we analyse a new proposal for a knapsack-type cryptosystem, published by Wang and Hu (A novel combinatorial public key cryptosystem, Informatica, 611–626, 21, 2010), along with two cryptanalyses of it, carried out by Youssef (Cryptanalysis of a quadratic knapsack cryptosystem, Computers & Mathematics with Applications, 1261–1265, 61, 2011) and Lee (Cryptanalysis of a quadratic compact knapsack public-key cryptosystem, Computers & Mathematics with Applications, 3614–3621, 62, 2011). We also analyse another proposal for a combinatorial cryptosystem, written by the same authors, together with a cryptanalysis of it, authored by Xu et al. (Implicit polynomial recovery and cryptanalysis of a combinatorial key cryptosystem, Lecture Notes in Computer Science, 45–57, 7618, 2012). Both cryptosystems prove to be safe only if the keys have very large sizes, but this severely impacts the use of the systems from a practical point of view. Moreover, we also give evidence suggesting that the independence of the combinatorial system with respect to the integer factorization problem might be not so solid as claimed by the authors. Finally, we answer in the affirmative the open question about the computational complexity of the matrix combinatorial problem, by showing that it is solvable in polynomial time if the factorization of N is known.