Optimal Access Structure Partition Methods for Image Secret Sharing

Abstract

Visual cryptography scheme (VCS) and polynomial-based secret image sharing (PSIS) are two primary types of secret sharing for protecting images. VCS and PSIS have their respective pros and cons. For VCS, the benefits of perfect security and easy decoding are provided. But it suffers from the limitations of lossy secret recovery and binary image-oriented. PSIS can deal with grayscale/color images and offers lossless secret reconstruction. Whereas, the secret decoding is computationally intensive (i.e., O(klog²k) for (k,n) threshold) and the residual-image problem in PSIS compromises the security. In this paper, we are motivated to investigate a sharing technique that can preserve the advantages of both VCS and PSIS. Differing from existing VCS and PSIS, the proposed sharing method is accomplished based on the access structure partition (ASP) result. Essentially, an ASP guided image secret sharing approach is developed and three optimal ASP algorithms are designed. When compared with existing partition method, significant improvement is offered by our partition techniques especially for the (k,n) threshold with a larger n . Take the (2,15) , (2,18) , and (4,12) thresholds for example, the numbers of involved sub-access structures by our method are 4, 5, and 19, while the quantities by existing approach are 8, 10, and 45. The percentages of improvement are 100%, 100%, and 137%. Further, based on the partition result from ASP algorithms, we can employ (k,k) probabilistic VCS (PVCS) to constitute a (k,n) sharing method for encoding gray-level/color images. Experiments are demonstrated to confirm the effectiveness of the sharing method and ASP algorithms. Meanwhile, comparisons are included to show that the merits of perfect security, low decoding complexity (i.e., O(d) ), lossless secret recovery (i.e., PSNR =∞ , SSIM= 1), and grayscale/color image-oriented are provided by our sharing method.