Minimizing Pixel Expansion in Visual Cryptographic Scheme for General Access Structures.

Given a secret image S , a set \mathscr {P} of n participants and a strong access structure ( \Gamma \mathrm {\mathbf {Qual}} , \Gamma \mathrm {\mathbf {Forb}}) , a visual cryptographic scheme (VCS) for general access structures (GVCS) encodes S into n shares of transparencies such that the participants of each qualified set in \Gamma \mathrm {\mathbf {Qual}} can reveal S by superimposing their shares; whereas those of any forbidden set in \Gamma \mathrm {\mathbf {Forb}} obtain nothing about $S$ . Elegant GVCS constructions have been designed with smaller pixel expansions. Yet, whether the pixel expansion derived is minimized is still unknown. In this research, we generalize and extend our recent study, in which the modeling of minimizing the pixel expansion for a ( $k$ , $n$ )-VCS into an integer linear program (ILP) was proposed, to ensure that the constraints for GVCS can be satisfied. The pixel expansion of a GVCS can thus be minimized by solving the corresponding ILP. This is the first result in the literature for acquiring the optimal solution to a GVCS. The computational study demonstrates the effectiveness of our ILP and also verifies that the best solution from previous GVCS approaches is optimal for all strong access structures of $n \le 4$ ; but no more reliable for those of $n\ge 5$ . [ABSTRACT FROM PUBLISHER]