×

New secure partial encryption method for medical images using graph coloring problem. (English) Zbl 1348.94010

Summary: The traffic of digital images has been quickly increased in the network. Security of image processing became important for many sectors, namely for medical applications. Currently, the transmission of medical images is a daily routine. The large volume of data exchange has motivated the development of new methods to reduce the cost. Partial encryption is an approach to reduce the computational resources for huge volumes of multimedia. This paper introduces a new and secure approach, called graph coloring problem cryptography, to encrypt partially the medical images using the graph coloring problem (GCP). Before encrypting the medical images using advanced encryption standard algorithm, we use a GCP algorithm to localize and select some optimal positions of the pixels in the original images. Thus, the key of the cryptographic method is hard to be detected and extracted by the hackers. We get an acceptable percentage of the encrypted data for better security with a lower cost compared with the total image encryption.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
94A60 Cryptography
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alattar, A.M., Al-Regib, G.I., Al-Semari, S.A.: Improved selective encryption techniques for secure transmission of MPEG video bit-streams. In: ICIP 99, International Conference on Image Processing, IEEE, vol. 4, pp. 256-260 (1999)
[2] Said, A.: Measuring the strength of partial encryption scheme. In: ICIP 2005, IEEE International Conference in Image Processing, vol. 2, pp. 1126-1129. Genova (2005)
[3] Cheng, H., LI, X.: Partial encryption of compressed images and videos. IEEE Trans. Signal Process. 48(8), 2439-2451 (2000) · doi:10.1109/78.852023
[4] Rodrigues, J.-M., Puech, W., Bors, A.G.: A selective encryption for heterogenous color JPEG images based on VLC and AES stream cipher. CGIV’06, Leeds, (2006)
[5] Van Droogenbroeck, M.: Partial encryption of images for real-time applications. In: Fourth IEEE Benelux Signal Processing, Hilvarenbeek, pp. 11-15 (2004) · Zbl 0437.68021
[6] Puech, W., Rodrigues, J.M., Develay-Morice, J.E.: Transfert sécurisé d’images médicales par codage conjoint : cryptage sélectif par AES en mode par flot et compression JPEG (Safe transfer of medical images by conjoined coding: selective encryption by AES using the stream cipher mode OFB and JPEG compression). Traitement du signal (TS), numéro spécial Traitement du signal appliqué la cancérologie 23(3-4), 201-211 (2006) · Zbl 1145.94451
[7] Spanos, G.A., Maples, T.B.: Performance study of a selective encryption scheme for the security of networked, real-time video. In: Proceedings of 4th International Conference on Computer Communications and Networks, 20-23, (1995) · Zbl 0553.90059
[8] Bourbakis, N., Alexopoulos, C.: Picture data encryption using scan patterns. Pattern Recognit. 25(6), 567-581 (1992) · doi:10.1016/0031-3203(92)90074-S
[9] Jones, D.: Applications of splay trees to data compression. Commun. ACM 31(8), 996-1007 (1988) · doi:10.1145/63030.63036
[10] Matias, Y., Shamir, A.: A video scrambling technique based on space filling curves. In: CRYPTO ’87, 398-417, (1988) · Zbl 0626.68051
[11] Daemen, J., Rijmen, V.: The Design of Rijndael. Springer, NJ (2002) · Zbl 1065.94005 · doi:10.1007/978-3-662-04722-4
[12] Daemen, J., Rijmen, V.: AES Proposal the Rijndael Block Cipher. Technical report. Proton World Int.1, Katholieke Universiteit Leuven, ESAT-COSIC, Belgium (2002) · Zbl 1065.94005
[13] de Werra, D.: An introduction to timetabling. Eur. J. Oper. Res. 19(2), 151-162 (1985) · Zbl 0553.90059 · doi:10.1016/0377-2217(85)90167-5
[14] Gamache, M., Hertz, A., Ouellet, J.O.: A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding. Comput. Operat. Res. 34(8), 2384-2395 (2007) · Zbl 1144.90498 · doi:10.1016/j.cor.2005.09.010
[15] Lim, A., Wang, F.: Robust graph coloring for uncertain supply chain management. In: Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS’05)-Track 3-Volume 03. IEEE Computer Society, 11(8): 263-277, (2005)
[16] Allen, M., Kumaran, G., Liu, T.: A combined algorithm for graph-coloring in register allocation. In: Johnson, D.S., Mehrotra, A., Trick, M. (eds.) Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 100-111. Ithaca, New York (2002) · Zbl 0626.68051
[17] Barnier, N., Brisset, P.: Graph coloring for air traffic flow management. In: CPAIOR’02 : Fourth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems, pp. 133-147. Le Croisic (2002)
[18] Gamst, A.: Some lower bounds for a class of frequency assignment problems. IEEE Trans. Veh. Technol. 35, 8-14 (1986) · doi:10.1109/T-VT.1986.24063
[19] Douiri, S.M., Medeni, M.B.O., Elbernoussi, S., Souidi, E.: A new steganographic method for grayscale image using graph coloring problem. Appl. Math. Sci. 7(2), 521-527 (2013) · doi:10.12785/amis/070213
[20] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, Nantes (1979) · Zbl 0411.68039
[21] Leighton, F.T.: A graph coloring algorithm for large scheduling problems. J. Res. Natl. Bur. Stand. 84(6), 489-506 (1979) · Zbl 0437.68021 · doi:10.6028/jres.084.024
[22] Brlaz, D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251-256 (1979) · Zbl 0394.05022 · doi:10.1145/359094.359101
[23] Hertz, A., Werra, D.: Using tabu search techniques for graph coloring. Computing 39(4), 345-351 (1987) · Zbl 0626.68051 · doi:10.1007/BF02239976
[24] Dorne, R.; Hao, JK; Voss, S. (ed.); Martello, S. (ed.); Osman, IH (ed.); Roucairol, C. (ed.), Tabu search for graph coloring, t-colorings and set t-colorings metaheuristics, No. 117, 77-92 (1998), Dordrecht
[25] Douiri, S.M., Elbernoussi, S.: A new heuristic for the sum coloring problem. Appl. Math. Sci. 5(63), 3121-3129 (2011) · Zbl 1252.05059
[26] Chen, K., Ranmabadran, T.V.: Near-lossless compression of medical images through entropy coded DPCM. IEEE Trans. Med. Imaging 3(3), 538-548 (1994) · doi:10.1109/42.310885
[27] Puech, W., Rodrigues, J.M.: Crypto-Compression of Medical Images by Selective Encryption of DCT, EUSIPCO’05: European Signal Processing Conference, Sep 2005, Antalya (Turkey) (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.