Advanced
Selective Encryption Algor ithm Based on DCT for GIS Vector Map
Selective Encryption Algor ithm Based on DCT for GIS Vector Map
Journal of Korea Multimedia Society. 2014. Jul, 17(7): 769-777
Copyright © 2014, Korea Multimedia Society
  • Received : March 14, 2014
  • Accepted : June 05, 2014
  • Published : July 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
P.N. Giao
Dept. of IT Convergence and Applications Eng., Pukyong National University
Gi-Chang Kwon
Dept. of IT Cooperative System, Gyeongbuk Provincial College
Suk-Hwan Lee
Dept. of Information Security, Tongmyong University
Ki-Ryong Kwon
Dept. of IT Convergence and Applications Eng., Pukyong National University

Abstract
With the rapid interest in Geographic Information System (GIS) contents, a large volume of valuable GIS dataset has been distributed illegally by pirates, hackers, or unauthorized users. Therefore the problem focus on how to protect the copyright of GIS vector map data for storage and transmission. At this point, GIS security techniques focusing on secure network and data encryption have been studied and developed to solve the copyright protection and illegal copy prevention for GIS digital map. But GIS vector map data is very large and current data encryption techniques often encrypt all components of data. That means we have encrypted large amount of data lead to the long encrypting time and high complexity computation. This paper presents a novel selective encryption scheme for GIS vector map data protection to store, transmit or distribute to authorized users using K-means algorithm. The proposed algorithm only encrypts a small part of data based on properties of polylines and polygons in GIS vector map but it can change whole data of GIS vector map. Experimental results verified the proposed algorithm effectively and error in decryption is approximately zero.
Keywords
1. INTRODUCTION
GIS is a system which designed to capture, store, manipulate, analyze, and manage all kinds of the geographic information and it is the merging system of cartography, statistical analysis, and database technology [1 - 2] . It consists of hardware, software, and GIS data. GIS allows us to view, understand, question, interpret, and visualize data in many ways that reveal relationships, patterns, and trends in the form of maps, globes, reports, and charts.
GIS has been used in military and commercial applications for many years. The main component of GIS is the data. The GIS data has two important properties. Firstly, the effort it takes to put it in a form suitable for use in the GIS applications. This effort increases its cost. Secondly, in most cases the GIS Data contains confidential information which must be kept away from unauthorized users. Such confidential information includes GIS layers containing troop locations and additional information like movements and mines places in a tactical environment. Hence, it is very important to protect the GIS data. Moreover, the GIS data is too expensive so we have to prevent illegal duplication and distribution of it. Nowadays, it is too easy for a company to buy some GIS layers, make illegal copies from them and distribute or sell them many times without taking any permission from the original GIS data provider. So we have to enforce some kinds of access control on it because the GIS data is sensitive and must not be accessed by unauthorized users.
In section 2, we introduce related works, and in section 3 we present selective encryption scheme for GIS vector map data protection. Finally, we implement the proposed scheme, and show experimental results in section 4.
2. RELATED WORKS
The GIS vector map data includes layers. Each layer is a basic unit of geographical objects which are described and managed in a map. These objects describe the topography and geographical features of real objects or a certain place. Each layer consists of an amount of vector data which uses pairs of coordinates to describe as point, polyline and polygon [3 - 4] , as shown Fig. 1 . Officially, the point is used to present simple or small objects in the reality on the map while polyline and polygon are used to present complex and large objects. Thus, our algorithm only performs selective encryption for polylines and polygons in GIS vector map.
PPT Slide
Lager Image
An example GIS vector map with city, river and country layers; (a) Railway layer, (b) Lake layer, (c) Building layer, and (d) Railway + Lake + Building layers.
The general approach of selective encryption is to separate the content into two parts. The first part is the public part, which is un-encrypted and accessible by all users [5 - 11] . The second part is the protected part; it is encrypted. Only authorized users have access to protected part. Polylines and polygons are selected, and encrypted by random keys combine with randomization and clustering process by K-means algorithm [12] , random algorithms in DCT domain based on their geographical features [13] . Our algorithm encrypts only some selective DC values of polylines, polygons in DCT domain but it changes the whole map.
3. PROPOSED SELECTIVE ENCRYPTION ALGORITHM
Our method aims to encrypt GIS vector map perceptually and entirely using a few of selected values, it is called as vector map selective encryption.
- 3.1 Selective Encryption Process
The selective encryption algorithm follows as Fig. 2 . Our algorithm consists of processes as data extraction to have polylines and polygons, polylines and polygons clustering using K clusters, vertices randomization of polylines and polygons by random coefficients using random key. Next, it applies DCT processing for randomized vertices to get DCT coefficients, and then multiply DC coefficients of each cluster with a random value which is created by another random key. Finally, it performs inverse discrete cosine transform (IDCT).
PPT Slide
Lager Image
Selective encryption algorithm for polyline/polygon.
In order to encrypt selectivity, we compute the total number of polylines NPLi , total number of polygons NPGi in i th layer. Each polyline/polygon has attributes such as the number of parts and the number of points. These attributes in each polyline/polygon is different. So, we used them to classify NPLi polylines, NPGi polygons into K clusters using K-means algorithm. We have NPLi polylines, NPGi polygons in i th layer, and we need to cluster them into K groups where K ={ kg | g ∈[1, K ]}. Each group kg in K groups is described by a centroid Cg ={ xcg , ycg }. Considering number of parts Npa-ij and number of points Npo-ij in j th polyline/polygon are coordinates in two dimensional space. And j th polyline/polygon is represented as a point which has coordinates ( Npa-ij , Npo-ij ) in that two dimensional space. The j th polyline/polygon is classified in group kg using the shortest Euclidean distance to Cg follow as equation (1). Djg is the Euclidean distance from j th polyline/polygon to centroid Cg , and calculated by equation (2).
PPT Slide
Lager Image
PPT Slide
Lager Image
Then, we find NL i-max of the max number of vertices in a polyline, and NG i-max of the max number of vertices in a polygon in i th layer. With values NL i-max , NG i-max and K , we generated random NL i-max coefficients where RL ={ rlk | k {1, NL i-max ]} for polylines, random NG i-max coefficients where RG ={ rgk | k {1, NG i-max ]} for polygons by random key R1 using equations (3) and (4):
PPT Slide
Lager Image
PPT Slide
Lager Image
From NL i-max and NG i-max coefficients, we randomize them with vertices in polylines, polygons follow as equations (5) and (6). These random coefficients will be applied to all polylines/polygons in a layer depend on the number of vertices in a polyline/polygon because number of vertices in a polyline NLi NL i-max , number of vertices in a polygon NGi NG i-max . And each layer will be applied different random coefficients. After randomization step polylines/polygons are encrypted by random key R 1 , and we receive NPLi new polylines with PL′i ={ pl′ij | j ∈[1, NPLi ] }={ ul′ i,j,k | j ∈[1, NPLi ], k ∈[1, NLij ]}, and NPGi new polygons with
PG′i ={ pg′ij | j ∈[1, NPGi ] }={ ug′ i,j,k | j ∈[1, NPGi ], k ∈[1, NGij ]}. Fig. 3 (a) shows a randomized example for polyline.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Example of randomization and multiplication for polyline, (a) Randomized example for polyline, (b) Multiplying DC coefficient with random value.
We continue to apply DCT for these new polylines/polygons to get a set of transformed polylines DLi by equation (7) and a set of transformed polygons DGi by equation (8).
PPT Slide
Lager Image
PPT Slide
Lager Image
After DCT processing, we continue to encrypt polylines/polygons one more time by multiplying DC coefficients of transformed polylines/polygons with one corresponding random value to their group, from K random values follow as equations (9), (10) and Fig. 3 (b). K random values are Rv ={ rvg | g ∈[1, K ]}, and generated by random key R2 using the used random algorithm above.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Finally, we perform IDCT to get encrypted polylines EPLi , polygons EPGi by equations (12) and (13).
PPT Slide
Lager Image
PPT Slide
Lager Image
for i ∈[1, NM ].
- 3.2 Selective decryption process
The decryption algorithm for these polylines and polygons shown by Fig. 4 is the inverse process of selective encryption given at Fig. 2 . Similar with the selective encryption process, we must also extract the protected data which consists of encrypted polylines and encrypted polygons, compute number of polylines and polygons, and find maximum number of vertices in polylines and polygons. The next step is to divide them into several groups by using K-means algorithm, similar with the encryption process, because the encryption changes the value of vertices only. Then, random coefficients and random values are generated again by random generator using random keys. Firstly, encrypted polylines and encrypted polygons are transformed using DCT and the DC coefficients are divided by random values. Secondly, they are inversed using IDCT to get randomized polylines and polygons again. Finally, we perform inverse randomization by dividing values of polylines/polygons in IDCT domain for random coefficients to have decrypted polylines and polygons.
PPT Slide
Lager Image
Selective decryption algorithm for polyline/polygon.
4. EXPERIMENTAL RESULTS
We used 1:5000, 1:10000, and 1:100000 scalingmaps in our experiments. Firstly, we experimented with each polyline layer and polygon layer with the scale of 1:5000. Then, we tested the full layers of 1:10000 and 1:100000 scale. Experimental results with polyline layer, polygon layer and full maps show that all maps are changed as given by Fig. 5 and Fig. 6 . Unauthorized user cannot see anything on map because we changed polylines and polygons through four processes: randomization, DCT, multiplication, and IDCT using random keys R 1 , R 2 .
PPT Slide
Lager Image
Experimental result with scaling layers 1:5000; (a) original polyline layer, (b) encrypted polyline layer, (c) original polygon layer, and (d) encrypted polygon layer.
PPT Slide
Lager Image
Experimental result with full scaling map 1:10000, 1:100000; (a) original map 1:10000, (b) encrypted map 1:10000, (c) original map 1:100000, and (d) encrypted map 1:100000.
Our selective encryption scheme only changes values of vertices in polylines and polygons of the map. It did not alter the size of encrypted file. The result of loss accuracy is shown in Table 1 . In addition, DCT and IDCT are not processes absolutely. That means, if we have an input sequence xn , and we perform DCT to get xk , and next we perform IDCT to get input sequence again x′n , it shows that x′n is not absolutely equal to xn because the cosine value is not integer. However, in GIS vector map data, vertices are stored in double type such that the errors between original vertices and decrypted vertices values are approximately zero as given by Table 2 .
The result of loss accuracy
PPT Slide
Lager Image
The result of loss accuracy
The error between original coordinates and decrypted coordinates
PPT Slide
Lager Image
The error between original coordinates and decrypted coordinates
Finally, the distance between maps dM is computed by equation (14):
PPT Slide
Lager Image
We used polyline map, polygon map to experiment other three times. Each time, we encrypted maps with different passwords which are used to create random keys as figure 3 . Then we calculate dM distances of each experimental time. In Table 3 , experimental results show that dM distance of two maps which are encrypted by different passwords from an original map is depend on passwords.
Experimental distance measure
PPT Slide
Lager Image
Experimental distance measure
5. CONCLUSION
Our paper focuses on the issues how to encrypt GIS vector map selectivity with low complexity. We classified objects and encrypted them by random algorithms in DCT domain. Only some values are selected to encrypt by random processes but it made changing whole map. Experimental results showed that the proposed algorithm has very effective with a large volume of GIS dataset. Decrypting results also show the error in decryption process approximates zero. Our algorithm can be applied to various file formats or standard vector map because only polyline and polygon objects are encrypted and can be used for map database security of GIS map service on/off-lines. Furthermore, our algorithm can be applied to various vector contents such as CAD and 3D content fields. Next time, we will continue to improve our algorithm by reducing number of selective values to reduce complexity while not change effectively.
BIO
Giao Pham Ngoc
Giao Pham Ngoc received a B.S. degree in School of Electronic & Telecommunication from Hanoi University of Science & Technology (HUST) in 2011, and Master degree from Pukyong National University (PKNU) in 2014. Currently, he is an researcher in Multimedia Communication & Signal Processing Lab in PKNU. His research interests include video processing & application, GIS applications, data security, and smart system.
Gi-Chang Kwon
Gi-Chang Kwon received a B.S., a M.S., and Ph.D. degrees from Andong National University in 1985, Daegu Univsrsity in 1993, and Yeongnam University in 2000. Currently, he is a professor in Department of IT Cooperative System at Geongbuk Provincial College. His research interests include multimedia contents and image processing, digital contents and smart system.
Suk-Hwan Lee
He received a B.S., a M.S., and a Ph. D. degrees in Electrical Engineering from Kyungpook National University, Korea in 1999, 2001, and 2004 respectively. He is currently an associate professor in Department of Information Security at Tongmyong University. His research interests include multimedia security, digital image processing, and computer graphics.
Ki-Ryong Kwon
He received the B.S., M.S., and Ph.D. degrees in electronics engineering from Kyungpook National University in 1986, 1990, and 1994 respectively. He worked at Hyundai Motor Company from 1986-1988 and at Pusan University of Foreign Language from 1996-2006. He is currently a professor in Department of IT Convertgence and Application Engineering at the Pukyong National University. He has researched University of Minnesota in USA on 2000~2002 with Post-Doc. and Colorado State University on 2011~2012 with visiting professor. He is currently the General Affair Vice President of Korea Multimedia Society. His research interests are in the area of digital image processing, multimedia security and watermarking, bioinformatics, weather radar information processing.
References
Foote K.E. , Lynch M. 2011 Geographic Information Systems as an Integrating Technology: Context, Concepts, and Definitions
Goodchild M.F. 2010 “Twenty Years of Progress: GIS Science in 2010,” Journal of Spatial Information Science (1) 3 - 20
(2004) Geographic Information System http://en.wikipedia.org/wiki/Geographic_information_system
(2006) GIS Vector Map http://en.wikipedia.org/wiki/Vector_map
Massoudi A. , Lefebvre F. , De Vleeschouwer C. , Macq B. , Quisquater J.-J. 2008 “Overview on Selective Encryption of Image and Video: Challenges and Perspectives,” Hindawi Publishing Corporation EURASIP Journal on Information Security Article ID:179290 2008 (5) 18 -
Abomhara M. 2011 Enhancing Selective Encryption for H.264/AVC Using Advanced Encryption Standard University of Malaya Kuala Lumpur
Hasan M.Y. , Ahmed F.A. , Abdelhamid K. 2009 “Image Adaptive Selective Encryption of Vector Quantization Index Compression,” Proceeding of IEEE International Conference on Image Processing 1277 - 1280
Puech W. , Rodrigues J.M. 2005 “Crypto-Compression of Medical Images By Selective Encryption of DCT,” Proceeding of European Signal Processing Conference Vol. 1 225 - 228
Sharma S. , Pateriya P. 2012 “A Study on Different Approaches of Selective Encryption Technique,” International Journal of Computer Science & Communication Networks 2 (6) 658 - 662
Jang. B.J. , Moon. K.S. , Lee. S.H. , Kwon. K.R. 2011 “Effective Compression Technique for Secure Transmission and Storage of GIS Digital Map,” Journal of Korea Multimedia Society 14 (2) 210 - 218    DOI : 10.9717/kmms.2011.14.2.210
Nazneen M.G , Banu S. , Tabassum Z. , Fatima K. , Shariff A. 2013 “Selective Bitplane Encryption for Secure Transmission Of Image Data In Mobile Environment,” International Journal of Scientific & Technology Research 2 (6) 92 - 96
Queen Mac 1967 Some Methods for Classification and Analysis of Multivariate Observations University of California Press Berkeley, Calif. Vol. 1 281 - 297
Strang G. 1999 “The Discrete Cosine Transform,” Society for Industrial and Applied Mathematics 41 (1) 135 - 147