Don’t Escape The Matrix – A GPU-Parallelizable Matrix-Based Block Cipher with Two-DimensionalDiffusion

Dont Escape The Matrix – A GPU-Parallelizable Matrix-Based Block Cipher with Two-Dimensional Diffusion

A GPU-Parallelizable Matrix-Based Block Cipher with Two-Dimensional Diffusion

Prakhar S Mittal

University School Of Automation and Robotics Guru Gobind Singh Indraprastha University, New Delhi

Abstract – We propose a matrix-based symmetric block cipher designed explicitly for parallel execution on graphics processing units (GPUs). Unlike the classical Hill cipher, which applies a single linear transformation C = KP , our construction applies a two-sided matrix transformation ASB mod q within a substitution-permutation network (SPN), giving diffusion across both rows and columns of the state in a single step while remaining nonlinear overall. Because the cipher is operated in counter (CTR) mode, blocks are mutually independent and can be encrypted as a single batched matrix-multiplication call, mapping naturally onto GPU tensor/GEMM hardware. We present the formal construction, prove that the pure linear core is vulnerable to a known-plaintext attack (motivating the non- linear layer), describe a GPU-oriented batched implementation, and outline an experimental methodology for correctness, sta- tistical/cryptanalytic evaluation, and throughput benchmarking against AES-CTR on GPU.

Index Termsblock cipher, matrix cryptography, GPU cryp- tography, parallel encryption, Hill cipher, SPN

1. Introduction

   Block ciphers such as AES operate on small, xed-size blocks (128 bits) using round functions whose individual steps are inexpensive but whose parallelism is constrained by block size and mode of operation. Modern GPUs, in contrast, are optimized for large, regular linear-algebra workloads such as batched matrix multiplication. This mismatch motivates the question we address: can a block cipher be designed so that its core diffusion step is a matrix multiplication, and its mode of operation exposes block-level independence, so that encryption reduces to a batched GEMM (general matrix multiply) call that fully exploits GPU hardware?

   The classical Hill cipher [1] already uses matrix multipli- cation as its encryption primitive, but it is purely linear and is broken trivially by a known-plaintext attack using O(m) plaintext-ciphertext pairs [2]. Our contribution extends the Hill ciphers single-sided, one-dimensional matrix transform into a two-sided, two-dimensional diffusion step, embeds it inside a nonlinear SPN (in the spirit of AES/Rijndael), and evaluates its suitability for GPU execution specically, rather than treating the GPU port as an afterthought as is common in prior GPU- AES work [3][6].

   The contributions of this paper are:

   • A formal, two-sided matrix diffusion step (ASB mod q) generalizing the Hill cipher to two dimensions, with a proof of why nonlinearity is required.

   • A GPU-oriented key schedule producing round matrices with invertibility guaranteed by construction (as products of elementary matrices).

   • A CTR-mode construction exposing full inter-block par- allelism, implemented as a single batched matrix multiply on GPU.

   • An experimental methodology and preliminary results for correctness, statistical/differential evaluation, and throughput versus CPU and AES-CTR-GPU baselines.

2. Related Work

   1. Matrix-based classical cryptography

      The Hill cipher [1] encrypts an m-symbol block P as C = KP mod q for an invertible key matrix K. It achieves full diffusion across the m symbols of a single block but is a linear transformation of the plaintext, so an attacker holding m linearly independent known plaintext-ciphertext pairs can recover K directly via Gaussian elimination [2]. This known weakness is the starting point for our design: we retain matrix multiplication as the diffusion primitive but wrap it in a nonlinear substitution layer, following the general substitution- permutation network (SPN) strategy used by Rijndael/AES [7].

   2. GPU-accelerated block ciphers

   A substantial body of work accelerates AES on GPUs via CUDA, generally by mapping the existing AES round structure onto GPU threads with varying granularity (bytes per thread) and memory layout choices. Di Biagio et al. [3] imple- mented AES-CTR on CUDA and reported a 14× throughput improvement over CPU OpenSSL. Iwai et al. [4] studied the effect of memory allocation and parallelism granularity, achieving approximately 35 Gbps on an NVIDIA GTX 285. Li et al. [5] reported around 60 Gbps on a Tesla C2050 using shared-memory T-boxes. Abdelrahman et al. [6] studied multiple granularities across GPU generations, reporting up to 277 Gbps on a Pascal-generation GPU. In all of these works, AESs byte-oriented round structure (SubBytes, ShiftRows, MixColumns on 4 × 4 state) is mapped onto the GPU after the fact; none of them redesign the diffusion primitive itself to be a native GEMM operation. Our design instead makes the diffusion step itself a matrix multiplication from the outset, so that the mapping onto GPU batched-GEMM hardware (cuBLAS / tensor cores) is direct rather than an engineering accommodation.

3. Proposed Algorithm

   1. State representation

      A plaintext block is represented as a matrix S Zn×n. We

      1. SubBytes

         Each entry is passed through a xed bijective S-box :

         Zq Zq, applied element-wise:

         t

         discuss the choice of modulus q

   2. Round function

      q

      in Section III-F.

      Sij = (Sij). (4)

      We reuse the AES S-box [7] rather than designing a new one. The AES S-box has well-studied nonlinearity and differential- uniformity properties; reusing it lets us cite existing analysis

      Each round k = 1, …,r applies, in order:

      directly rather than re-deriving these properties for a novel S-

      box, and isolates our contribution to the matrix diffusion layer

      Rk(S) = Permute

      Ak (S Kk) Bk mod q

      (1)

      and the GPU-oriented construction.

      q

      where Kk is the round key, is a xed bijective S-box applied element-wise, Ak, Bk Zn×n are keyed invertible matrices, and Permute is a keyed row/column shufe.

   3. MixMatrix: two-dimensional diffusion

      The core diffusion step is

      St = AS B mod q. (2)

      ij

      Left-multiplication by A mixes each column of S (a linear combination of rows); right-multiplication by B mixes each row of S (a linear combination of columns). Applying both in a single step means every output cell St is a function of every entry of S:

      1. Choice of modulus q

         Two choices were considered:

         • q = 256: byte-aligned, but Z256 has zero divisors, so only matrices with determinant coprime to 2 (odd determinant) are invertible.

         • q prime (e.g. q = 251 or q = 257): Zq is a eld, so any matrix with nonzero determinant is invertible, which simplies both the key schedules invertibility guarantee and the correctness proofs.

           For the reference implementation and initial experiments we use a prime modulus to keep invertibility reasoning simple; a byte-aligned mod-256 variant is left as an implementation optimization once correctness is established (see Section VIII).

      2. Key schedule

         The master key Kmaster nd a per-message nonce are

         n n

         S

         ij

         t = L L Aip Spql Bqlj mod q. (3)

         p=1 ql=1

         This is the two-dimensional generalization of the Hill ciphers single left-multiplication C = KP , which mixes only one axis.

   4. Lemma: pure matrix mixing is linearly invertible

   Lemma 1. The map S 1 ASB mod q, with A, B xed, is linear in S. Consequently, given a sufcient number of known plaintext-ciphertext matrix pairs with linearly inde- pendent structure, A and B (or their combined action) can be recovered by solving a linear system, analogous to the classical known-plaintext attack on the Hill cipher [2].

   Proof sketch. For xed A, B, the map S 1 ASB is linear because A(S1 + S2)B = AS1B + AS2B and A(cS)B = c(ASB) for scalar c. An attacker holding plaintext-ciphertext pairs can therefore set up a linear system in the unknown entries of A and B (or, if only recovering the equivalent round action is required, in the unknown entries of the combined linear operator) and solve via Gaussian elimination, exactly as in the one-sided Hill cipher case.

   This lemma is the formal justication for including the nonlinear SubBytes layer (Section III-E): without it, Eq. 2 alone is cryptographically broken regardless of block size or choice of A, B.

   the only values supplied externally. All round material

   k=1

   {Kk, Ak, Bk}r is derived deterministically:

   seedk = HKDF(Kmaster, k) (5)

   using a standard key-derivation function (HKDF [8] or SHA- 256 in counter mode) rather than a novel PRF, so that the schedules security properties can be argued from an estab- lished primitive rather than asserted.

   Invertibility of Ak and Bk is guaranteed by construction rather than by rejection sampling: each matrix is built as a product of elementary matrices (row swap, row scaling by a unit, row addition of a multiple of another row) whose entries are derived from seedk. Since a product of invertible matrices is always invertible, this avoids the need to compute a determinant and retry, and gives a one-line correctness argument for the paper.

   1. Mode of operation: CTR

   Rather than chaining blocks (as in CBC), each blocks keystream is generated independently from the nonce and a counter:

   Si = Pi Rr(Rr1(··· R1(Nonce I/ i) ··· )) (6) Because block is computation does not depend on block

   i 1s output, all blocks in a message can be processed in parallel. This is the property that enables batched GPU execution (Section IV).

4. GPU Implementation

   1. Batched execution model

      TABLE I

      AVALANCHE AND DIFFERENTIAL TEST RESULTS, n = 4, 10 ROUNDS, AES S-BOX, q = 257 (200500 TRIALS; SEE CRYPTANALYSIS_TESTS.PY)

      Because CTR mode removes inter-block dependencies, N

      blocks can be stacked into a single batched tensor of shape

      Metric Ideal Measured

      (N, n, n) and the MixMatrix step (Eq. 2) becomes a single batched matrix multiplication:

      Plaintext avalanche (% bits changed) Key avalanche (% bits changed) Differential uniformity (max freq.)

      44.4% 45.0% (=4.3%)

      44.4% 45.6% (=4.1%)

      low, uniform 0.20% (500/500 unique)

      Batcht = A · Batch · B (7)

      Monobit frequency (% ones)

      44.4%

      44.0%

      executed via a library batched-GEMM call (e.g. cuBLAS batched_gemm, or the batched matrix multiply in Py-

      NIST STS pass rate threshold

      TABLE II

      TODO (run full suite)

      Torch/CuPy), rather than N sequential calls. SubBytes be- comes a single coalesced table-lookup (or, on GPU, an elemen- twise mapping) over the whole batch, and Permute becomes an index-remapping operation, both trivially parallel across the

      Throughput comparison (fill in after running

      GPU_BENCHMARK.PY)

      Implementation Throughput (GB/s) Latency (ms / batch)

      batch dimension.

      CPU reference (NumPy)

      GPU batched (this work)

      TODO TODO

      TODO TODO

   2. Why block size matters for GPU occupancy

   A larger block (e.g. n = 16, giving a 16 × 16 state versus AESs 4 × 4) increases the amount of independent arithmetic per block, which can improve GPU occupancy per batched-GEMM call, at the cost of a larger key schedule and larger per-block memory footprint. This trade-off is evaluated experimentally in Section VI.

5. Experimental Methodology

   This section describes the experiments to be run (Sec- tion VIII provides companion scripts); Section VI reports results once available.

   1. Correctness

      For a range of block sizes n and round counts r, we verify DK(EK(P )) = P for randomly sampled plaintexts and keys, conrming that the key schedules invertibility guarantee holds in practice.

   2. Statistical and cryptanalytic evaluation

      • Avalanche effect: ip one input bit, measure the fraction of output bits that change (target 50%).

      • Key sensitivity: x the plaintext, ip one key bit, measure output bit-change fraction.

      • Differential trails: for xed input difference P , mea- sure the distribution of output differences C across many keys/plaintexts, checking for non-uniform cluster- ing.

      • Ciphertext randomness: apply standard statistical ran- domness tests (e.g. frequency, runs, and serial tests from the NIST STS battery [9]) to ciphertext streams.

   3. Performance benchmarking

   Throughput (GB/s) and latency are measured as a function of batch size N and block size n, on both CPU (reference NumPy implementation) and GPU (batched PyTorch/CuPy implementation), and compared against AES-256-CTR (e.g. via a GPU AES library or OpenSSL as the CPU baseline), following the methodology of prior GPU-AES throughput studies [3], [4].

   AES-256-CTR (GPU baseline) TODO TODO

6. Results

   Results pending execution of the availability of High-End GPU clusters for computation of a throughoutput baseline across varied platforms; see Section VIII.

7. Discussion and Limitations

   This work proposes a construction and an evaluation methodology; it does not claim a formal security proof. Resistance to the tests in Section V is evidence against the specic attacks tested, not a guarantee against all attacks. In particular, side-channel behavior (timing and memory-access patterns) may differ materially on GPU versus CPU due to differing memory hierarchies, and is not evaluated in this version of the paper. We view formal security proof and side-channel analysis as important future work rather than omissions to be glossed over.

8. Conclusion and Future Work

We presented a matrix-based block cipher whose diffusion primitive is a two-sided matrix multiplication and whose mode of operation exposes block-level independence, both chosen specically to map onto GPU batched-GEMM exe- cution. We proved that the linear core alone is vulnerable to known-plaintext attack, motivating the SPN construction, and described a GPU-oriented key schedule with invertibility guaranteed by construction. Future work includes: formal dif- ferential/linear cryptanalysis bounds for the specic S-box and matrix family chosen; side-channel evaluation on GPU; a byte- aligned mod-256 variant for direct hardware alignment; and extension of the optional Indic-script codebook layer discussed in preliminary design work, which remains a cosmetic layer rather than a security component.

References

1. J. Overbey, W. Traves, and J. Wojdylo, On the keyspace of the Hill cipher, Cryptologia, vol. 29, no. 1, pp. 5972, 2005.

2. D. R. Stinson, Cryptography: Theory and Practice, 3rd ed. Chapman and Hall/CRC, 2005.

3. A. Di Biagio, A. Barenghi, G. Agosta, and G. Pelosi, Design of a parallel AES for graphics hardware using the CUDA framework, in 2009 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). IEEE, 2009, pp. 18.

4. K. Iwai, N. Nishikawa, and T. Kurokawa, Acceleration of AES en- cryption on CUDA GPU, International Journal of Networking and Computing, vol. 2, no. 1, pp. 131145, 2012.

5. Q. Li, C. Zhong, K. Zhao, X. Mei, and X. Chu, Implementation and analysis of AES encryption on GPU, in 2012 IEEE 14th International Conference on High Performance Computing and Communication. IEEE, 2012, pp. 843848.

6. A. A. Abdelrahman, M. M. Fouad, R. Orje´sek, and H. M. Dahshan, Anal- ysis on the AES implementation with various granularities on different GPU architectures, Advances in Electrical and Electronic Engineering, vol. 15, no. 3, pp. 526535, 2017.

7. National Institute of Standards and Technology, Advanced encryption standard (AES), FIPS PUB 197, 2001.

8. H. Krawczyk and P. Eronen, HMAC-based extract-and-expand key derivation function (HKDF), RFC 5869, 2010.

9. National Institute of Standards and Technology, A statistical test suite for random and pseudorandom number generators for cryptographic applications, NIST Special Publication 800-22, 2010.