In this paper, we elaborate the security threats that exist on hybrid cryptosystem based on satisfiability problem. In such system the encryption is carried out by generating 3-SAT clauses by random insertion of literal in a given 2-SAT clause instance. The solution of 2-SAT clause instance gives the secret key and the placement of literal for conversion to 3-SAT gives the position vector. Two crucial parameter for encryption. Thus, the system seems to be robust. However, the security of such system is at stake, when we apply the polynomial solvability formulation of 3-SAT[2]. Here, we propose a chosen plain text attack on such system using polynomial solvability of 3-SAT as reported in[3]. We observe that the complexity of the attack is O(3n), where n is the number of clauses.

1. L Rezkallah, S. Bouroubi An new hybrid cryptosystem based on the satisfiability Problem , downloaded from the site www.laid3.usthb.dz/road/horizontal/ road3909.pdf
2. Narendra .S. Chaudhari, ,Feb 2011 Polynomial Solvability of 3-SAT -Part III: Polynomial algorithm for 3-SAT ,NHSS,Udaipur,India, ISBN : 978-81-7906-266-1 pp-71-76.
3. Narendra .S. Chaudhari, Feb 2011 Polynomial Solvability of 3-SAT - Part II: Algorithmic formulations for 2-SAT, NHSS, Udaipur, India, ISBN :978-81-7906-266-1 pp-59-64 .
4. Jaya Thomas, Narendra .S. Chaudhari , Apr 2011,Polyno- mial Solvability of Satisfiability and its Implication to Hyb- rid Cryptosystem Security International Conference on Em- -erging Trends in Networks and Computer Communication (ETNCC), 2011.Udaipur,pp:521-54.
5. Kobayashi, K; Tadaki, K; Kasahara, M; Tsuiji, S; A Knapsack cryptosystem based on multiple knapsacks ,ISITA 2010, pp428 – 432.
6. K.B. Lakshmanan and Ravi Janardan , A Public-Key Cryptosystem based on the Matrix Cover {NP} - Complete Problem. Advances in Cryptology: Proceedings of Crypto 82, R. L. Rivest and A. Sherman and D. Chaum,editors. , volume 0, Plenum Press, New York, 1983. Pages 21-37.
7. A. Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem, IEEE Trans. Inform.Theory, vol. IT-30, 1984, pp. 699-704.
8. Peter W. Shor, 1997 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer Siam Journal on Computing - SIAMCOMP , vol. 26, no. 5, pp. 1484-1509.
9. Massimo Caboara , Fabrizio Caruso, and Carlo Traverso October 2010, Lattice Polly Cracker cryptosystems Journal of Symbolic Computation Volume 46, Issue 5, May 2011, pp. 534-549.
10. Rainer Steinwandt, Willi Geiselmann , Regine Endsuleit 2002, Attacking a polynomial-based cryptosystem: Polly Cracker International Journal of Information Securi- -ty Volume 1, Number 3, pp143-148.
11. R. C. Merkle and M. E. Hellman, "Hiding Information and Signatures in Trapdoor Knapsacks," IEEE Trans. Inform. Theory, vol. 24, 1978, pp. 525-530.

Public Key Satisfiability 2-SAT 3-SAT NP-complete Secret key