A Maze Matrix-Based Secret Image Sharing Scheme with Cheater Detection

Ching-Chun Chang, Ji-Hwei Horng, Chia-Shou Shih, Chin-Chen Chang

TL;DR

This paper introduces a novel secret image sharing scheme for massive IoT applications that uses a "maze matrix" to embed secret data into two shadow images. It features a two-layered cheat detection system that can identify tampered shadows even without information from other participants, and uses Lagrange polynomials to significantly speed up the image creation process.

What Problem Does This Paper Address?

The proliferation of the Internet of Things (IoT) means a massive increase in connected devices and the data they handle. Ensuring the privacy and security of this data, especially sensitive images, is a significant challenge. Traditional methods for sharing secrets often rely on pre-shared keys or complex systems, which can be cumbersome in a distributed IoT environment. This paper addresses the need for a secure, efficient, and robust secret image sharing method that can operate without pre-shared secrets and actively detect and identify malicious participants (cheaters) who might tamper with the shared data.

Methods

The core of the proposed scheme is a novel "maze matrix." This matrix, constructed through a specific mirroring process, guides the embedding of secret data into two distinct cover images, creating two "shadow" images. The maze matrix has unique properties, including "forbidden zones" (marked with 'x'), which are crucial for detecting tampering.

The scheme employs a two-layered cheat detection mechanism:

  1. Joint Cheat Detection: This layer checks if a pair of shadow pixels maps to a forbidden zone in the maze matrix. If it does, a potential cheat event is flagged.
  2. Blind Cheater Identification: This layer, a key innovation, can identify a tampered shadow without relying on information from the other shadow. It leverages specific "gap" locations within the maze matrix to pinpoint which shadow is likely compromised.

To improve efficiency, the authors derived Lagrange polynomials. Instead of computationally expensive searching for embedding locations, these polynomials directly calculate the exact pixel values for the shadow images, significantly reducing processing time.

Datasets

The paper uses publicly available grayscale images for cover images and a secret image. Specifically, six pairs of 512x512 grayscale cover images (e.g., Lena, Baboon, Tiffany, Barbara) and a 362x362 grayscale secret image named "office" were used for experimental evaluation. No new datasets were introduced.

Key Insights and Ideas

  • Maze Matrix for Security: The maze matrix isn't just a lookup table; its structured "gaps" and "forbidden zones" are ingeniously designed to enable both data hiding and robust cheat detection.
  • Two-Layered Cheat Detection: The combination of a joint detection (requiring both shadows) and a blind detection (working with a single shadow) offers a powerful and flexible security framework.
  • Blind Cheater Identification is Game-Changing: The ability to identify a cheater without needing the other shadow is a significant advancement, especially in distributed systems where participants might not always cooperate.
  • Lagrange Polynomials for Speed: Using mathematical polynomials to directly compute pixel values instead of iterative searching is a clever optimization that drastically improves performance.
  • IoT Applicability: The scheme's reliance on low-cost computations and lack of pre-shared keys makes it well-suited for resource-constrained IoT environments.

Key Results

  • Visual Quality: Shadow images exhibit high Peak Signal-to-Noise Ratios (PSNR) around 39.86-39.90 dB, indicating that the visual degradation is imperceptible to human eyes.
  • Embedding Capacity: The scheme can embed a substantial amount of data, with a capacity of 1,048,576 bits per cover image pair, sufficient to embed the entire secret image.
  • Joint Cheat Detection Ratio (DRJ): Achieved around 0.42 for single tampered shadows and increased to 0.72 for combinatorial tampering (both shadows tampered).
  • Blind Cheater Detection Ratio (DRB1): Detected approximately 0.20 of tampered pixels in a single shadow, demonstrating its effectiveness.
  • Time Efficiency: The Lagrange polynomial approach reduced share construction time by up to 39% compared to conventional searching methods.

Limitations and Future Work

  • Detection Ratios: While effective, the detection ratios for single tampering (DRJ ~0.42) and blind detection (DRB1 ~0.20) could potentially be improved. The paper notes that the blind detection ratio is lower in single tampering cases compared to combinatorial tampering.
  • Combinatorial Tampering: The paper explores combinatorial tampering (both shadows tampered) and shows higher detection rates (DR102 ~0.72), but the detection ratio for the union of tampered regions (DR102) is dependent on the overlap percentage.
  • Future Work: The authors envision integrating this scheme into massive IoT systems as a data security module. They also suggest its application in scenarios where image shadows are transmitted via different routes to devices (e.g., smartphones) and secret extraction is performed via apps, enabling secure communication without pre-shared keys.

Summary updated

Abstract

Secret image sharing is a technique for sharing a secret message in such a fashion that stego image shadows are generated and distributed to individual participants. Without the complete set of shadows shared among all participants, the secret could not be deciphered. This technique may serve as a crucial means for protecting private data in massive Internet of things applications. This can be realized by distributing the stego image shadows to different devices on the Internet so that only the ones who are authorized to access these devices can extract the secret message. In this paper, we proposed a secret image sharing scheme based on a novel maze matrix. A pair of image shadows were produced by hiding secret data into two distinct cover images under the guidance of the maze matrix. A two-layered cheat detection mechanism was devised based on the special characteristics of the proposed maze matrix. In addition to the conventional joint cheating detection, the proposed scheme was able to identify the tampered shadow presented by a cheater without the information from other shadows. Furthermore, in order to improve time efficiency, we derived a pair of Lagrange polynomials to compute the exact pixel values of the shadow images instead of resorting to time-consuming and computationally expensive conventional searching strategies. Experimental results demonstrated the effectiveness and efficiency of the proposed secret sharing scheme and cheat detection mechanism.
BibTeX
@inproceedings{chang2020maze,
  author = {Ching-Chun Chang and Ji-Hwei Horng and Chia-Shou Shih and Chin-Chen Chang},
  title = {{A Maze Matrix-Based Secret Image Sharing Scheme with Cheater Detection}},
  booktitle = {Sensors},
  year = {2020},
  url = {https://openreview.net/forum?id=kolVDdc0rd},
}
Figure