Sudoku Associated Two Dimensional Bijections for Image Scrambling

Yue Wu, Sos S. Agaian, Joseph P. NoonanarXiv 2012 · arXiv

Introduction

As digital imaging becomes increasingly integral to medical, satellite, and personal communications, the need for robust information protection has never been more critical. Image scrambling serves as a fundamental technique to disorder the spatial relationship between pixels, rendering an image unrecognizable to unauthorized parties. The primary challenge in this field is developing a "two-dimensional bijection"—a mathematical mapping that relocates every pixel to a unique new position while remaining perfectly reversible with the correct key.

Traditional methods based on chaos theory or cellular automata often suffer from residual patterns or "ghosts" of the original image. This paper introduces a novel approach that leverages the mathematical constraints of Sudoku puzzles to generate complex, parametric 2D bijective mappings that produce noise-like scrambled outputs.

The Sudoku-Associated Mapping

The core innovation of this research is the treatment of a Sudoku solution not as a game, but as a specialized coordinate system. In a standard $N \times N$ Sudoku grid, the "one-of-each" constraint (where every digit appears exactly once in every row, column, and block) provides a natural engine for generating permutations.

Conceptual bridge between a standard Sudoku puzzle (a) and the mathematical grid representation (b) used for pixel mapping.

By representing image pixels through Sudoku-associated pairs, the authors define six parametric representations:

  1. (row, digit)
  2. (digit, row)
  3. (column, digit)
  4. (digit, column)
  5. (block, digit)
  6. (digit, block)

Mapping a pixel from one of these representations back to the standard row-column grid creates a unique permutation. Given that there are 24 basic Sudoku-associated bijections and billions of possible Sudoku matrices, the resulting variety of scrambles is immense, providing a high degree of parametric diversity.

Scrambling Methodology and Scalability

The proposed scrambling scheme is driven by a 192-bit key that generates round-dependent parameters. Unlike simple position shuffling, this algorithm operates on individual bit-planes, which effectively changes the image histogram and enhances security. To accommodate images of varying resolutions, the algorithm utilizes blockwise processing with an overlapping technique at the edges to prevent "blocky" artifacts and increase shuffle complexity.

Scalability of the method using larger Sudoku matrices, such as $25 \times 25$ (a) and $36 \times 36$ (b), for high-resolution data scrambling.

Experimental Results

The authors evaluated the method across diverse datasets, including standard grayscale images (Lenna, Cameraman), natural images from the Berkeley dataset, medical MRI samples, and binary fax data.

Key performance metrics include:

  • Gray Degree of Scrambling (GDD): The proposed method achieved a GDD of 0.9672 on test image #239096, significantly outperforming earlier methods which reached only 0.4502.
  • Correlation: The Adjacent Pixel Autocorrelation (APCC) dropped from ~0.97 to near zero (-0.0020), indicating that spatial relationships were successfully destroyed.
  • Visual Quality: Head-to-head comparisons showed that the Sudoku method produced cleaner, more uniform noise than peer algorithms, which often left behind mesh-like artifacts.

While the MATLAB implementation reached speeds of approximately 150 KB/s, the authors suggest that the bit-plane and block-based logic is highly suitable for parallelization on GPUs or FPGAs for real-time applications.

Conclusion and Future Work

Sudoku-associated bijections provide a robust, deterministic, yet highly variable framework for image scrambling. While the system is resistant to brute-force attacks, the authors note a theoretical vulnerability to Chosen Plaintext Attacks (CPA) if keys are not rotated frequently. Future work may extend these bijections to secure audio and video data, or apply them in the fields of digital watermarking and data hiding.

Summary updated

BibTeX
@misc{wu2012sudoku,
  author = {Yue Wu and Sos S. Agaian and Joseph P. Noonan},
  title = {{Sudoku Associated Two Dimensional Bijections for Image Scrambling}},
  year = {2012},
  eprint = {1207.5856},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1207.5856},
}
Figure