Advanced
Selective Encryption Scheme for Vector Map Data using Chaotic Map
Selective Encryption Scheme for Vector Map Data using Chaotic Map
Journal of Korea Multimedia Society. 2015. Jul, 18(7): 818-826
Copyright © 2015, Korea Multimedia Society
  • Received : April 10, 2015
  • Accepted : June 01, 2015
  • Published : July 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
N.V. Bang
Dept. of IT Convergence and Applications Eng., Pukyong National University
Kwang-Seok Moon
Dept. of Electronics Eng., Pukyong National University
Sanghun Lim
Korea Institute of Civil Engineering and Building Technology
Suk-Hwan Lee
Dept. of Information Security, Tongmyong University
Ki-Ryong Kwon
Dept. of IT Convergence and Applications Eng., Pukyong National University
krkwon@pknu.ac.kr

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. 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 the selective encryption scheme using hybrid transform for GIS vector map data protection to store, transmit or distribute to authorized users. In proposed scheme, polylines and polygons in vector map are targets of selective encryption. We select the significant objects in polyline/polygon layer, and then they are encrypted by the key sets generated by using Chaotic map before changing them in DWT, DFT domain. Experimental results verified the proposed algorithm effectively and error in decryption is approximately zero.
Keywords
1. INTRODUCTION
The vector map, is also called GIS vector map, is a vector–based collection of Geographic Information System (GIS) data about earth at various levels of detail. Vector map is created and developed by the merging system of cartography, statistical analysis, and database technology based on vector model [1 , 2] . Vector data provide a way to represent real world features within the GIS environment because vector data has advantages as need a small space or place for storage data; has a high spatial resolution and graphic representation spatial data closely likes handed map; easily for making projection and coordinates transformation [3 , 4] . For those advantages, vector map is used in many domains, and GIS applications use vector map have provided general users with easy access to services via mobile devices or internet access. But the producing process of a vector map is considerably complex and the maintenance of a digital map requires substantial monetary and human resources. And any companies can buy it, make illegal copies from them and distribute or sell them easily many times without taking any permission from the original GIS data provider. Moreover, applications of vector map in military domain require the high security, and must be kept away from unauthorized users. So vector map is necessary to be protected and prevent illegal duplication and distribution of it.
Our paper is organized as follows. In section 2, we discuss the related works and in section 3, we explain the proposed selective encryption algorithm in detail. Then, in section 4 we perform experiments and discuss about the experimental results, evaluate the performance of algorithm. Finally, we conclude this paper in section 5.
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 [5 , 6] , as shown Fig. 1 .
PPT Slide
Lager Image
An example GIS vector map; (a) Forest layer, (b) Road layer.
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. Polyline is used to represent objects as road, contour line, and railway, so on. Polygon is used to represent objects as building, area, lake, boundaries and so on. 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 [7 - 11] . The second part is the protected part; it is encrypted.
From these reasons, our algorithm only performs selective encryption for polylines and polygons in GIS vector map. Only authorized users have access to protected part. Polylines and polygons are selected, and encrypted by the key sets generate from Chaotic map before changing them in DWT, DFT domain based on their geographical features [12 , 13] . Our algorithm encrypts only some coefficients in DWT domain by changing DC value in DFT domain but it changes the whole map.
3. PROPOSED ALGORITHM
Our method aim to encrypt GIS vector map perceptually and entirely using a few of selected values, it is called as vector map selective encryption.
- 3.1 Encryption process
The schematic diagram of the proposed technique is illustrated in Fig. 2 , and the step-by-step procedure is explained hereafter.
PPT Slide
Lager Image
Schematic diagram for proposed encryption technique.
  • An original GIS vector map isM={Li|i∈[1,NM}] withNMlayers in a map. A layerLiis a set of objects of polylines and polygonsLi={Oij|i∈[1,Ni} withNiis the total number of objects inLi.
  • An objectOijhave properties the total number of points (vertices) and the area of bounding box. Calculate the area threshold (Aith) and the point threshold (Pith) for each layer.
  • Identify the significant objects by comparing the total number of points and the area of bounding box with two thresholds. For an insignificant object, leave it unencrypted. For a significant object, using encryption block to encrypt it by key sets generated from Chaotic map and user’s password before changing them in DWT, DFT domain.
- 3.1.1 Object classification
Our algorithm only performs selective encryption for polyline/polygon in GIS vector map. However, each polyline/polygon layer has many objects and if we encrypt all of them, we also need many computation time. Each object has attributes such as the number of points (P), the area of bounding box (A), as shown in Fig. 3 (a). Many objects are created from a few points and the value of bounding box’s area is very small when compare with other objects in a layer. This object is very simple and mark it as an insignificant object, as shown in Fig. 3 (b). With objects include many points and the area of bounding box is larger than, it also complex than and mark it as a significant object, as shown in Fig. 3 (c).
PPT Slide
Lager Image
An example about objects in a layer.
Thus, we used probability distribution to define thresholds in each layer and identify which object is a significant or insignificant object by comparing object’s features with thresholds.
The area threshold ( Aith ) and the point threshold ( Pith ) in a layer are defined as following:
  • A layerLi:Li={Oij|j∈[1,Ni},Niis the total number of objects inLi.
  • A objectOijinclude two features: The area of bounding box (Aij) and the total number of points (Pij).
  • Therefore, we have:Ai={Aij|j∈[1,Ni} and,Pi={Pij|j∈[1,Ni} in layerLi.
  • We used probability distribution to find threshold in setAi,Pi:
PPT Slide
Lager Image
PPT Slide
Lager Image
- 3.1.2 Chaotic map
The classical chaos system is a logistic map, which can be defined by following:
PPT Slide
Lager Image
Here 0≤ μ ≤4 is the coefficient of the map, k=0, 1, 2, . . . and all the values of { xi } appear in the range [0,1] for the initial value x0∈[0,1]. It is noted that Eq. (3) has the chaotic behavior [14 , 15] when μ appears in the range [3.57,4], and especially the chaotic behavior called Pomeau–Manneville scenario [16] when appears in the range [3.57,3.82].
- 3.1.3 Encryption block
We used the key to create two key sets (length of key set is 8) for a layer. It is created randomly the first key in each key set by SHA-512 algorithm from user key with key length is 512 bit. Other keys are generated by using Chaotic map as Eq. (3). Therefore, we have two key sets: a ={ ai | i ∈[1,8]}, b ={ bi | i ∈[1,8]} and DC encryption value:
PPT Slide
Lager Image
For a significant object, using encryption block to encrypt it, as shown in Fig. 4 (a) and illustrate in Fig. 5 , the step-by-step procedure is explained hereafter.
PPT Slide
Lager Image
Proposed (a) encryption and (b) decryption process for vector map.
PPT Slide
Lager Image
Selective encryption process.
  • We arrange all X, Y coordinates of the significant objects in a layer, into two 1D-arrays, given the length of segment is 8, the total number of segments in each array is:n=N/8,Nis the length of 1D-array.
  • With each segment, we encrypt all coordinates by using keys of two key sets a, b and create complex numbers as equation:
  • Zi=Xi*ai+j*Yi*bi,i∈[1,8].
  • Apply DWT-3 level for each segment to get a set of first transformed values. In each segment, select the first coefficient of first transformed values and continue to apply DFT to get a set of second transformed values.
  • After DFT processing, we continue to encrypt by multiplying the first DC coefficient with DFT encryption value by equation (4).
PPT Slide
Lager Image
  • We perform IDFT to get a set of encrypted values of second transformed values. Replace the first coefficient in each segment by one encrypted value in step 6 and IDWT-3 level with each segment to get a set of encrypted values of first transformed values.
  • Assign X, Y encrypted coordinates of the significant objects by image, real part of the encrypted complex values that is generated in step 7.
- 3.2 Decryption process
The reverse process is applied to decrypt the encrypted map. To perform decryption, after we calculate thresholds in a layer, we use the decryption block to decrypt the encrypted significant objects, as shown in Fig. 4 (b). If correct key is employed at the time of decryption, then the decrypted map would by a replica of the original map. In the case of an incorrect decryption key, the output map is vary.
4. EXPERIMENTAL RESULTS
- 4.1 Visualization
Experimental results figure 6 and figure 7 show the proposed algorithm changes whole maps. The proposed method has much lower computational complexity than AES (Advanced Encryption Standard ) or DES (Data Encryption Standard) because we only select some coefficients in DWT domain and one DC value in DFT domain, encrypt it by key values.
PPT Slide
Lager Image
Experimental results of polyline/polygon layer.
PPT Slide
Lager Image
Experimental result with full scaling layers 1:5000: (a) original map, (b) encrypted map.
- 4.2 Distance measure
The distance between original map and encrypted map is computed by equation (5):
PPT Slide
Lager Image
With L is a original map, ( L ) is corresponding encrypted map, N is the total number of objects in original map. And d ( Pij ) is distance between corresponding objects in ( L ) and L.
We used same original map to experiment with different passwords K1 # K2. Then we calculate D ( , L ) distance of each experimental time, as show in Table 1 . .
Experimental distance measure
PPT Slide
Lager Image
Experimental distance measure
- 4.4 Decryption error
Our selective encryption scheme only changes values of vertices in polylines and polygons of map. It did not alter the size of encrypted file, as shown in Table 2 . In addition, we use hybrid transform to encrypt coordinates, that means, if we have an input sequence zn , and we perform DFT to get Zk , and next we perform IDFT to get input sequence again n , it shows that n , is not absolutely equal to zn because sine and cosine value are 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 3 .
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.
- 4.5 Security
Cryptographic security : In our algorithm, by using dynamic thresholds to define a significant object in a layer, about 70% of data is encrypted by using the key sets are generated from user's password and Chaotic map. It would be very difficult to break the encryption algorithm or try to predict the encrypted part.
Key sensitivity analysis : We test to encrypt the original layer with a slightly different encryption key, and evaluates the difference between the obtained encrypted layers.
To perform these test, slightly different keys are generated by modifying coefficient μ in Eq. (3) and a pair of first key in each key set a, b. In the modified keys, excluding one are kept same as that of original key. For the original key K 1 (3.52,0.34,0.62)(Key K is represented by three parameters ( μ , a 1 , b 1 )), the modified keys are expressed as K 2 (3.42,0.34,0.62), K 3 (3.52,0.44,0.62) and K 4 (3.52,0.34,0.52). The original layer ( Fig. 6 (c)) is initially encrypted with key sets are generated from K 1 . The encrypted layer for this case is shown in Fig. 8 (b). The original layer is then encrypted with key sets are generated from slightly modified key K 2 , K 3 and K 4 . Fig. 8 (b)-(d) indicates the corresponding encrypted layers. It is observed that layers encrypted with slightly different keys are completely incomprehensible.
PPT Slide
Lager Image
Key sensitivity analysis for encryption process: (a)-(d) Encrypted layer with corresponding key K1, K2, K3 and K4.
5. CONCLUSION
Our paper focuses on the issues how to encrypt GIS vector map selectivity with low complexity. This considers the properties of object in a layer and selectively encrypts only the significant objects by key sets in DWT, DFT domain. Only some values are selected to encrypt 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. The proposed 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. Next time, we will continue to improve our algorithm by reducing number of selective values to reduce complexity while not change effectively.
BIO
Bang Nguyen Van
He received a B.S. degree in School of Electronic & Telecommunication from Hanoi University of Science & Technology (HUST) in 2014. Currently, he is a Master student in Multimedia Communication & Signal Processing Lab in Pukyong National University. His research interests include video processing & application, GIS applications, data security, and smart system.
Sanghun Lim
He received a B.S. degree in Electrical Engineering from Yonsei University in 1996 and a M.S., and Ph.D. degrees in Electrical & Computer Engineering from Colorado State University in 2002 and 2006, He worked research associate at CSU from 2006-2011 and research scientist at NOAA/CIRA in USA from 2011-2012. He is currently research fellow, Korea Institute of Civil Engineering and Building Technology. His research interests include radar meteorology/hydrology, radar system and signal processing.
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 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.
Kwang-Seok Moon
He received the B.S., and M.S., and Ph.D degrees in Electronics Engineering in Kyungpook National University, Korea in 1979, 1981, and 1989 respectively. He is currently a professor in department of Electronic engineering at Pukyong National University. His research interests include digital image processing, video watermarking, and multimedia communication.
References
Geographic Information Systems (GIS) https://en.wikipedia.org/wiki/Geographic_information_system
Goodchild M.F. 2010 “Twenty Years of Progress: GIS Science in 2010,” Journal of Spatial Information Science 1 (1) 3 - 20
Vector Data https://www.qgis.org/en/docs/gentle_gis_introduction/vector_data.html
Vector Map http://bgis.sanbi.org/gis-primer/page_19.htm
Bertino E. , Damiani M.L. “A Controlled Access to Spatial Data on Web,” Proceeding of AGILE Conference on Geographic Information Science 2004 369 - 377
Chena S.C. , Wangb X. , Rishea N. , Weiss M.A. 2003 “A Web-based Spatial Data Access System using Semantic R-trees,” Journal of Information Sciences 167 (1-4) 41 - 61    DOI : 10.1016/j.ins.2003.07.019
Bertino E. , Thuraisingham B. , Gertz M. , Damiani M.L. “Security and Privacy for Geospatial Data: Concepts and Research Directions,” Proceeding of the SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBS 2008 6 - 19
Rybalov N.B. , Zhukovsky O.I. “Access to the Spatial Data in the Web-Oriented GIS,” 2007 Proceeding of Siberian Conference on Control and Communications 104 - 107
Fuguang M. , Yong G. , Menglong Y. , Fuchun X. , Ding L. “The Fine-grained Security Access Control of Spatial Data,” Proceednig of 18th International Conference on Geoinformatics 2010 1 - 4
Wu F. , Cui W. , Chen H. 2008 “A Compound Chaos-Based Encryption Algorithm for Vector Geographic Data under Network Circumstance,” Proceeding of Cardholder Information Security Program Vol. 1 254 - 258
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
Zhu Ch. , Yang Ch. , Wang Q. 2008 "A Watermarking Algorithm for Vector Spatial Geo- Data based on Integer Wavelet Transform" The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 37 (B4) 15 - 18
Li A. , Lin B. , Chen Y. , Lu G. 2008 "Study on Copyright Authentication of GIS Vector Data Based on Zero-Watermarking" The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 37 (B4) 1783 - 1786
Chen S.L. , Hwang T. , Lin W.W. 2010 “Randomness Enhancement using Digitalized Modified Logistic Map,” IEEE Transactions on Circuits and SystemsI I : Express Briefs 57 (12) 996 - 1000    DOI : 10.1109/TCSII.2010.2083170
Chang S.M. , Li M.C. , Lin W.W. 2009 “Asymptotic Synchronization of Modified Logistic Hyper-chaotic Systems and its Applications,” Nonlinear Analysis: Real World Applicaions 10 (2) 869 - 880    DOI : 10.1016/j.nonrwa.2007.11.010
Liu Z. , Guo Q. , Xu L. , Ahmad M.A. , Liu S. 2010 “Double Image Encryption by using Iterative Random Binary Encoding in Gyrator Domains,” Optics Express 18 (11) 12033 - 12043    DOI : 10.1364/OE.18.012033