Abstract
Traditional randomness tests, such as the NIST 800-22 suite, are primarily designed for one-dimensional bitstreams and often fail to capture the two-dimensional spatial correlations inherent in images. This paper introduces a specialized evaluation method (EM) for image shuffling (IS) and image encryption (IE) based on the statistical distribution of pixel differences. By modeling a "perfectly shuffled image" as a set of independent and identically distributed (i.i.d.) pixels, we derive theoretical distributions for pixel differences and employ a Z-test for hypothesis testing. Experimental results on the USC-SIPI dataset demonstrate the method's efficacy in identifying weaknesses in common shuffling and encryption algorithms that 1D tests might overlook.
Introduction
Securing digital images typically involves Image Shuffling (IS), which permutes pixel positions, or Image Encryption (IE), which modifies both positions and values. A critical challenge in cryptography is objectively measuring the effectiveness of these processes. Standard 1D tests require flattening 2D images, which can obscure spatial artifacts. Furthermore, IS preserves the image histogram, making standard entropy measures insufficient. This research proposes a 2D-aware randomness yardstick that utilizes pixel difference distributions to evaluate the quality of image protection schemes.
Methodology
The core of the proposed method lies in the "Perfectly Shuffled Image" model. In this model, every pixel is treated as an i.i.d. random variable. The researchers focus on the distribution of differences between pairs of pixels rather than raw intensity values.
Theoretical Modeling
For a perfectly shuffled image, the probability distribution of pixel differences is derived from the image's original histogram. For the specific case of perfectly encrypted images (where the distribution is uniform), this simplifies to a predictable triangular distribution.
As shown in Figure 1, the theoretical mean $\mu_e$ and standard deviation $\sigma_e$ scale with the number of intensity levels $L$. For a standard 8-bit image ($L=256$), the expected mean difference is approximately 85.332.
The Z-Test and Randomized Sampling
Using the Central Limit Theorem, the average pixel difference of a sufficiently large sample ($m$) follows a Normal distribution. A Z-test is then applied to determine if the observed sample mean $\mu$ significantly deviates from the theoretical expectation $\mu_e$. To ensure the test is not biased by specific areas of the image, a randomized algorithm pulls pixel pairs from random configurations across the entire image. The authors also introduce a loss function to optimize the sample size $m$, balancing statistical accuracy with local spatial sensitivity.
Experimental Results
The method was validated using the USC-SIPI miscellaneous dataset, comprising 8-bit grayscale images ($L=256$) of various sizes and structures.
Figure 2 summarizes the statistical performance across the dataset. The parameters $m^*$ and $m_e^*$ represent the optimized sample sizes for IS and IE, respectively. The results indicate that:
- High-Performance Algorithms: The Random Permutation Method (RPM) and AES in CBC mode consistently passed the Z-test, showing no statistically significant difference from perfect randomness.
- Structural Failures: The Arnold Transform Method (ATM) and Row-Column Shuffling (RCS) failed the test due to residual periodic patterns like "mesh-like" or "slant" artifacts.
- Context Sensitivity: AES in ECB mode, while effective for natural images, failed on highly structured images like "ruler.512," confirming its known vulnerability to pattern leakage.
Conclusion
The proposed pixel-difference evaluation method provides a robust, computationally efficient ($O(NTm)$) tool for assessing image randomness. While passing this test is a necessary prerequisite for security, it does not replace comprehensive cryptanalysis. Future research will explore extending this framework to multi-channel color images and video data to provide a more holistic security assessment for visual media.
Summary updated