Data scrambler knight tour algorithm
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2024.3.03Keywords:
data scrambling, knight open tour problem, linear time complexity, guess probability, scrambling depthAbstract
Nowadays, data scrambling remains a vital technique to protect sensitive information by shuffling it in a way that makes it difficult to decipher or reverse-engineer while still maintaining its usability for legitimate purposes. As manipulating the usability of the scrambled data remains a challenge on the background of risking losing data and getting them re-identified by attackers, scrambling and descrambling should be accomplished faster by not increasing data loss and re-identification risks. A scrambling algorithm must have a linear time complexity, still shuffling the data to minimize the risks further. A promising approach is based on the knight open tour problem, whose solutions appear like a random series of knight positions. Hence, a knight open tour algorithm is formalized, by which the knight seems to move chaotically across the chessboard. The formalization is presented as an indented pseudocode to implement it efficiently, whichever programming language is used. The output is a square matrix representing the knight open tour. Based on the knight tour matrix, data scrambler and descrambler algorithms are presented in the same manner. The algorithms have a linear time complexity. The knight-tour scrambling has a sufficiently low guess probability if an appropriate depth of scrambling is used, where the data is re-scrambled repetitively. The scrambling depth is determined by repetitive application of the chessboard matrix, whose size usually increases as the scrambling is deepened. Compared to the pseudorandom shuffling of the data along with storing the shuffled indices, the knight-tour descrambling key is stored and sent far simpler yet ensures proper data security.
References
S.A. Abdelhameed, S.M. Moussa, and M.E. Khalifa, “Privacy-preserving tabular data publishing: A comprehensive evaluation from web to cloud,” Computers & Security, vol. 72, pp. 74–95, 2018. doi: https://doi.org/10.1016/j.cose.2017.09.002
N. Li, N. Zhang, S.K. Das, and B. Thuraisingham, “Privacy preservation in wireless sensor networks: A state-of-the-art survey,” Ad Hoc Networks, vol. 7, issue 8, pp. 1501–1514, 2009. doi: https://doi.org/10.1016/j.adhoc.2009.04.009
L. Zhang, S. Hao, J. Zheng, Y. Tan, Q. Zhang, and Y. Li, “Descrambling data on solid-state disks by reverse-engineering the firmware,” Digital Investigation, vol. 12, pp. 77– 87, 2015. doi: https://doi.org/10.1016/j.diin.2014.12.003
S. Kim, M. Kyoung Sung, and Y. Dohn Chung, “A framework to preserve the privacy of electronic health data streams,” Journal of Biomedical Informatics, vol. 50, pp. 95–106, 2014. doi: https://doi.org/10.1016/j.jbi.2014.03.015
S. De Capitani di Vimercati, S. Foresti, G. Livraga, and P. Samarati, “Chapter 18 — Digital infrastructure policies for data security and privacy in smart cities,” in J.R. Vacca (Ed.), Smart Cities Policies and Financing. Elsevier, 2022, pp. 249–261. doi: https://doi.org/10.1016/B978-0-12-819130-9.00007-3
R. Amdouni, M. Gafsi, R. Guesmi, M.A. Hajjaji, A. Mtibaa, and E.-B. Bourennane, “High-performance hardware architecture of a robust block-cipher algorithm based on different chaotic maps and DNA sequence encoding,” Integration, vol. 87, pp. 346–363, 2022. doi: https://doi.org/10.1016/j.vlsi.2022.08.002
I.C. Semanjski, “Chapter 5 — Data analytics,” in I.C. Semanjski (Ed.), Smart Urban Mobility. Elsevier, 2023, pp. 121–170. doi: https://doi.org/10.1016/B978-0-12-820717-8.00008-7
P. Pandya, “Chapter 15 — Advanced Data Encryption,” in J.R. Vacca (Ed.), Cyber Security and IT Infrastructure Protection. Syngress, 2014, pp. 325–345. doi: https://doi.org/10.1016/B978-0-12-416681-3.00015-X
P. Sun, “Security and privacy protection in cloud computing: Discussions and challenges,” Journal of Network and Computer Applications, vol. 160, Article ID 102642, 2020. doi: https://doi.org/10.1016/j.jnca.2020.102642
N. Sa’adah, “Trusted Data Transmission Using Data Scrambling Security Method with Asymmetric Key Algorithm for Synchronization,” EMITTER International Journal of Engineering Technology, vol. 6, issue 2, p. 217, 2018. doi: https://doi.org/10.24003/emitter.v6i2.267
P. Pandya, “Chapter 70 — Advanced Data Encryption,” in J.R. Vacca (Ed.), Computer and Information Security Handbook (Second Edition). Morgan Kaufmann, 2013, pp. 1127–1138. doi: https://doi.org/10.1016/B978-0-12-394397-2.00070-2
T. Stapko, “CHAPTER 8 — Choosing and Optimizing Cryptographic Algorithms for Resource-Constrained Systems,” in T. Stapko (Ed.), Practical Embedded Security. Newnes, 2008, pp. 149– 171. doi: https://doi.org/10.1016/B978-075068215-2.50009-4
D.S. Guamán, D. Rodriguez, J.M. del Alamo, and J. Such, “Automated GDPR compliance assessment for cross-border personal data transfers in android applications,” Computers & Security, vol. 130, Article ID 103262, 2023. doi: https://doi.org/10.1016/j.cose.2023.103262
R. Mia et al., “A comparative study on HIPAA technical safeguards assessment of android mHealth applications,” Smart Health, vol. 26, Article ID 100349, 2022. doi: https://doi.org/10.1016/j.smhl.2022.100349
D. Salomon, Data Privacy and Security: Encryption and Information Hiding. Springer-Verlag, Berlin, Heidelberg, 2003, 480 p.
H. Zhong, C. Gu, Q. Zhang, J. Cui, C. Gu, and D. He, “Conditional privacy-preserving message authentication scheme for cross-domain Industrial Internet of Things,” Ad Hoc Networks, vol. 144, Article ID 103137, 2023. doi: https://doi.org/10.1016/j.adhoc.2023.103137
W. Wang, H. Huang, Z. Yin, T. R. Gadekallu, M. Alazab, and C. Su, “Smart contract token-based privacy-preserving access control system for industrial Internet of Things,” Digital Communications and Networks, vol. 9, issue 2, pp. 337–346, 2023. doi: https://doi.org/10.1016/j.dcan.2022.10.005
N. Khalid, A. Qayyum, M. Bilal, A. Al-Fuqaha, and J. Qadir, “Privacy-preserving artificial intelligence in healthcare: Techniques and applications,” Computers in Biology and Medicine, vol. 158, Article ID 106848, 2023. doi: https://doi.org/10.1016/j.compbiomed.2023.106848
W.E. Yancey, W.E. Winkler, and R.H. Creecy, “Disclosure Risk Assessment in Perturbative Microdata Protection,” in J. Domingo-Ferrer (Ed.), Inference Control in Statistical Databases. Lecture Notes in Computer Science, vol. 2316. Springer, Berlin, Heidelberg, 2002. doi: https://doi.org/10.1007/3-540-47804-3_11
V. Torra, “Microaggregation for Categorical Variables: A Median Based Approach,” in J. Domingo-Ferrer and V. Torra (Eds.), Privacy in Statistical Databases. PSD 2004. Lecture Notes in Computer Science, vol. 3050. Springer, Berlin, Heidelberg, 2004. doi: https://doi.org/10.1007/978-3-540-25955-8_13
J. Domingo-Ferrer and V. Torra, “A Quantitative Comparison of Disclosure Control Methods for Microdata,” in P. Doyle, J.I. Lane, J.J.M. Theeuwes, and L.M. Zayatz (Eds.), Confidentiality, Disclosure, and Data Access: Theory and Practical Applications for Statistical Agencies. Elsevier, Amsterdam, 2001, pp. 111–133.
W. Wu, Q. Qi, and X. Yu, “Deep learning-based data privacy protection in software-defined industrial networking,” Computers and Electrical Engineering, vol. 106, Article ID 108578, 2023. doi: https://doi.org/10.1016/j.compeleceng.2023.108578
H.M. Ghadirli, A. Nodehi, and R. Enayatifar, “An overview of encryption algorithms in color images,” Signal Processing, vol. 164, pp. 163–185, 2019. doi: https://doi.org/10.1016/j.sigpro.2019.06.010
S. Yaremko, E. Kuzmina, N. Savina, D. Yaremko, V. Kuzmin, and O. Adler, “Development of a Smart Education System for Analysis and Prediction of Students’ Academic Performance,” in S. Babichev and V. Lytvynenko (Eds.), Lecture Notes in Computational Intelligence and Decision Making. ISDMCI 2021. Lecture Notes on Data Engineering and Communications Technologies, vol. 77. Springer, Cham, 2022. doi: https://doi.org/10.1007/978-3-030-82014-5_52
H. A. Yehoshyna, V. V. Romanuke, “Constraint-based Recommender system for commodity realization,” Journal of Communications Software and Systems, vol. 17, no. 4, pp. 314–320, 2021. doi: https://doi.org/10.24138/jcomss-2021-0102
U. Sopaoglu, O. Abul, “Classification utility aware data stream anonymization,” Applied Soft Computing, vol. 110, Article ID 107743, 2021. doi: https://doi.org/10.1016/j.asoc.2021.107743
G. Loukides, A. Gkoulalas-Divanis, “Utility-preserving transaction data anonymization with low information loss,” Expert Systems with Applications, vol. 39, issue 10, pp. 9764–9777, 2012. doi: https://doi.org/10.1016/j.eswa.2012.02.179
I. Parberry, “An efficient algorithm for the knight’s tour problem,” Discrete Applied Mathematics, vol. 73, issue 3, pp. 251–260, 1997. doi: https://doi.org/10.1016/S0166-218X(96)00010-8
M. Singh, A. Kakkar, and M. Singh, “Image encryption scheme based on knight’s tour problem,” Procedia Computer Science, vol. 70, pp. 245–250, 2015. doi: https://doi.org/10.1016/j.procs.2015.10.081
S.-S. Lin, C.-L. Wei, “Optimal algorithms for constructing knight’s tours on arbitrary chessboards,” Discrete Applied Mathematics, vol. 146, issue 3, pp. 219–232, 2005. doi: https://doi.org/10.1016/j.dam.2004.11.002
M. Valtorta, M. I. Zahid, “Warnsdorff’s tours of a knight,” Journal of Recreational Mathematics, vol. 25, no. 4, pp. 263–275, 1993.
J. Jeffers, J. Reinders, and A. Sodani, “Chapter 9 — Vectorization,” in J. Jeffers, J. Reinders, and A. Sodani (Eds.), Intel Xeon Phi Processor High Performance Programming (Second Edition). Morgan Kaufmann, 2016, pp. 173–212. doi: https://doi.org/10.1016/B978-0-12-809194-4.00009-0
V.V. Romanuke, “Finite uniform approximation of zero-sum games defined on a product of staircase-function continuous spaces,” Annals of the University of Craiova, Mathematics and Computer Science Series, vol. 49, issue 2, pp. 270–290, 2022. doi: https://doi.org/10.52846/ami.v49i2.1554
