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 8x8 chessboard is less than
10-16 . A similarly expected estimation for an 8x8x8 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-opentour 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-
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–
. Elsevier. https://doi.org/10.1016/b978-193183641-8/50005-8
Stapko, T. (2008). Choosing and optimizing cryptographic algorithms for resourceconstrained 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-
/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 n m 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
