Knight Pseudorandom Walk Manifold for Scrambling Multidimensional Data
DOI:
https://doi.org/10.31558/2786-9482.2024.1.1Keywords:
data scrambling, knight pseudorandom walk, break-in probability, similarity rateAbstract
The knight open tour problem is to build a sequence of knight moves covering a chessboard completely, without repetitions, where the starting position and ending position are always different. A solution of the knight open tour problem is similar to a sequence of pseudorandom numbers used to map data into non-readable yet usable information. The knight open tour problem has a manifold of solutions for a starting position of the knight depending on the chessboard size. Solutions of the knight open tour problem, which appear like a random series of knight positions, i. e. a pseudorandom walk, are used to further improve balance of the scrambling simplicity and productivity, where the main indicators are the break-in probability and similarity index. The break-in probability is dramatically decreased by taking into account a knight pseudorandom walk manifold for a starting position on a given chessboard. A pessimistic estimation of the break-in probability for an 8×8 chessboard is less than 10-16. A similarly expected estimation for an 8×8×8 chessboard is less than 10-26. A distinct knight pseudorandom walk (out of a manifold of pseudorandom walks) is built online by a given seed integer for a pseudorandom number generator. The scrambled data vector is built online as well in linear runtime complexity. Meanwhile, the similarity index is acceptable, rapidly dropping as the chessboard size is increased (for bigger multidimensional data arrays). A knight pseudorandom walk is determined by the chessboard size, the starting position, the way to vectorize the knight pseudorandom walk, and the pseudorandom number generator seed allowing to specifically move the knight onward through situations with multiple possible moves of the knight. The knight-open-tour scrambler has 1016 to 1021 times lower break-in probability compared to an ordinary pseudorandom number generator, depending on the chessboard size and the starting position of the knight.
References
Pandya, P. (2013). Advanced data encryption. In Cyber Security and IT Infrastructure Protection (pp. 325–345). Elsevier. https://doi.org/10.1016/B978-0-12-416681-3.00015-X
Pandya, P. (2013). Advanced data encryption. In Computer and Information Security Handbook (pp. 1127–1138). Elsevier Inc. https://doi.org/10.1016/B978-0-12-394397-2.00070-2
Li, N., Zhang, N., Das, S. K., & Thuraisingham, B. (2009). Privacy preservation in wireless sensor networks: A state-of-the-art survey. Ad Hoc Networks, 7(8), 1501–1514. https://doi.org/10.1016/j.adhoc.2009.04.009
De Capitani di Vimercati, S., Foresti, S., Livraga, G., & Samarati, P. (2022). Digital infrastructure policies for data security and privacy in smart cities. In Smart Cities Policies and Financing: Approaches and Solutions (pp. 249–261). Elsevier. https://doi.org/10.1016/B978-0-12-819130-9.00007-3
Waheed, A., Subhan, F., Suud, M. M., Alam, M. M., & Haider, S. (2023). Design and optimization of nonlinear component of block cipher: Applications to multimedia security. Ain Shams Engineering Journal, 102507. https://doi.org/10.1016/j.asej.2023.102507
Fair, T., Nordfelt, M., Ring, S., & Cole, E. (2005). Spying Basics. In Cyber Spying (pp. 45–86). Elsevier. https://doi.org/10.1016/b978-193183641-8/50005-8
Stapko, T. (2008). Choosing and optimizing cryptographic algorithms for resource-constrained systems. In Practical Embedded Security (p. 149–171). Elsevier. https://doi.org/10.1016/b978-075068215-2.50009-4
Sun, P. (2020). Security and privacy protection in cloud computing: Discussions and challenges. Journal of Network and Computer Applications, 160, 102642. https://doi.org/10.1016/j.jnca.2020.102642
Bakiri, M., Guyeux, C., Couchot, J.-F., & Oudjida, A. K. (2018). Survey on hardware implementation of random number generators on FPGA: Theory and experimental analyses. Computer Science Review, 27, 135–153. https://doi.org/10.1016/j.cosrev.2018.01.002
L’Ecuyer, P. (2006). Chapter 3. Uniform random number generation. In Handbooks in Operations Research and Management Science. Vol. 13 (p. 55–81). Elsevier. https://doi.org/10.1016/S0927-0507(06)13003-0
Plesser, H. E., & Jahnsen, A. G. (2010). Re-seeding invalidates tests of random number generators. Applied Mathematics and Computation, 217(1), 339–346. https://doi.org/10.1016/j.amc.2010.05.066
Dunn, W. L., & Shultis, J. K. (2012). Pseudorandom number generators. In Exploring Monte Carlo Methods (pp. 47–68). Elsevier. https://doi.org/10.1016/b978-0-444-51575-9.00003-8
Bowman, K. P. (2005). Statistics and pseudorandom numbers. In An Introduction to Programming with IDL (pp. 227–235). Elsevier. https://doi.org/10.1016/b978-012088559-6/50024-8
Ross, S. M. (2023). Random numbers. In Simulation (p. 39–45). Elsevier. https://doi.org/10.1016/b978-0-32-385738-3.00008-0
Parberry, I. (1997). An efficient algorithm for the Knight’s tour problem. Discrete Applied Mathematics, 73(3), 251–260. https://doi.org/10.1016/S0166-218X(96)00010-8
Lin, S.-S., & Wei, C.-L. (2005). Optimal algorithms for constructing knight’s tours on arbitrary chessboards. Discrete Applied Mathematics, 146(3), 219–232. https://doi.org/10.1016/j.dam.2004.11.002
Weisstein, E. W. Knight Graph. URL: https://mathworld.wolfram.com/KnightGraph.html
Bai, S., Yang, X.-F., Zhu, G.-B., Jiang, D.-L., & Huang, J. (2010). Generalized knight’s tour on 3D chessboards. Discrete Applied Mathematics, 158, 1727–1731. https://doi.org/10.1016/j.dam.2010.07.009
Kyek, O., Parberry, I., Wegener, I. (1997). Bounds on the number of knight’s tours. Discrete Applied Mathematics, 74(2), 171–181. https://doi.org/10.1016/S0166-218X(96)00031-5
Romanuke, V. V. (2022). Finite uniform approximation of two-person games defined on a product of staircase-function infinite spaces. International Journal of Approximate Reasoning, 145, 139–162. https://doi.org/10.1016/j.ijar.2022.03.005
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
