ایجاد طرح رمزنگاری بصری با تجزیه هیپرگرافی Constructing visual cryptography scheme by hypergraph decomposition

1. Introduction Naor and Shamir proposed the notion of k out of n visual cryptography scheme in [1], denoted as (k, n)-VCS for short, where a secret image is encrypted into n share images so that the physical stacking of any k share images can decrypt the secret content while any less than k share images will leak no information of the secret content. In most cases, VCSs need to encrypt binary images, which only have white and black pixels, denoted as □ and ■ respectively. In a (2, 2)-VCS, every white pixel is encrypted into two patterns ((□■, □■) and (■□, ■□) respectively) each with probability one half while every black pixel is encrypted into two patterns ((□■, ■□) and (■□, □■) respectively) each with probability one half. From any single share pattern, we have □■ and ■□ each with probability one half, regardless of the content of the secret pixel. Hence we will gain no information of the secret content from any single share. If we denote □ by 0 and denote ■ by 1, the pixel stacking model can be characterized by the Boolean OR operation on {0, 1}. Therefore, the decrypted white pixel can be □■ and ■□ each with probability one half while the decrypted black pixel will be ■■ for sure. We can still see the secret content from the decrypted image with 50% loss of contrast. As we can see, each secret pixel is encrypted into two pixels for each share image, which is defined as the pixel expansion and denoted as m usually. The pixel expansion of the previous (2, 2)-VCS is two. Ateniese et al. proposed the notion of general access structure VCS in [2]. In this paper, we denote the participant set by , and a general access structure consists of two specifications that are the set of qualified sets and the set of forbidden sets respectively. For any set , the secret content can be decrypted by physically stacking their share images, but any set gains no information of the secret content. From the above definition, we have . In k out of n access structure, it is easy to verify that we have and . There are two lines of work to construct VCSs, where one line uses combinatorial techniques [1,2,3,4], and the other line uses optimization search techniques [5,6,7]. Our constructions will follow the first line of work. The following contents can be divided into three parts. In Section 2, access structure notations and previous results are introduced. In Section 3, our constructions and relevant theoretical analysis are presented in detail. Section 4 gives a brief summary of our work.