The issue of authenticity in data transfer is very important in many communications. In this paper, we propose an improved version of the visual digital signature sc heme with enhanced security. The improvement was ma de based on Yang’s non&expansion visual cryptography technique and Boolean operations. The security of the improve d version of the visual digital signature scheme is assured by the K&SAT (3 &SAT and 4&SAT) NP&hard problem. This is to compare with the security of the existing scheme which is based on the difficult y of solving random Boolean OR operations. Besides improved in security the propose scheme is also, efficient in generating shares, compared to the existing scheme where the probability of generating black shares is high.

 

[1]  Barker E., Barker W., Burr W., Polk W., and Smid M., Recommendation for Key Management&Part 1: General (Revised) , National Institute of Standards and Technology Special Publication, 2007.

[2]  Borgulya I., “An Evolutionary Framework for 3. SAT Problems,” Journal of Computing and Information Technology , vol. 10, no. 3, pp. 185. 191, 2003.

[3]  Bugacov A., Galstyan A., and Lerman K., “Threshold Behavior in Boolean Network Model for SAT,” in Proceedings of the International Conference on Artificial Intelligence , Las Vegas, pp. 1.6, 2003.

[4]  Cetin K., “Implementation of ElGamal Digital Signatures in C/C++ (ECE 575 Project),” Data Security and Cryptography , Electrical & Computer Engineering , Oregon State University, 2002.

[5]  Cook S., “The Complexity of Theorem.Proving Procedures,” in Proceedings of the 3 rd Annual ACM Symposium on Theory of Computing , New York, pp. 151.158, 1971.

[6]  Erickson J., “Lecture 21: NP.Hardness,” Algorithms Course Materials (Revision) , available at: http://compgeom.cs.uiuc.edu/~jeffe/ teaching/algorithms/notes/21.nphard.pdf, last visited 2009.

[7]  Garey M. and Ohnson S., Computers and Intractability: A Guide to the Theory of NP& Completeness , W.H. Freeman and Company, New York, 1990.

[8]  Giritli M., “From 3.SAT to {2+p}, {3}.SAT,” Master of Logic Thesis , University of Amsterdam, 2001.

[9]  Jaafar A. and Samsudin A., “Visual Digital Signature Scheme: A New Approach,” International Journal of Computer Science , vol. 37, no. 4, pp. 36.44, 2010.

[10]  Menai M. and Batouche M., “Solving the Maximum Satisfiability Problem using an Evolutionary Local Search Algorithm,” International Arab Journal of Information Technology , vol. 2, no. 2, pp. 154.161, 2005.

[11]  Menezes J., Oorschot C., and Vanstone A., Handbook of Applied Cryptography , CRC Press, Ontario, 1996.

[12]  Mézard M. and Zecchina R., “Random K. Satisfiability Problem: From an Analytic Solution to an Efficient Algorithm,” Physical Review E , vol. 66, no. 5, pp. 1.38, 2002.

[13]  Mitra D., “NP.Complete Problems,” available at: http://cs.fit.edu/~dmitra/Algorithms/lectures/NP. doc, last visited 2005.

[14]  Walton J., “Cryptographic Interoperability: Digital Signatures,” available at: http://www.codeproject.com/KB/security/CryptoI nteropSign.aspx, last visited 2009.

[15]  Yang N., “New Visual Secret Sharing Schemes using Probabilistic Method,” Pattern Recognition Letter , vol. 25, no. 4, pp. 481.494, 2004. 602 The International Arab Journal of Information Tech nology, Vol. 10, No. 6, November 2013 .