A k out of n visual cryptographic scheme [(k, n)-VCS] encodes a secret image P into n transparencies (shares) in such a way that any k shares reveal P in a visual sense when they are superimposed (equivalent to the “OR” operation), while any k-1 or less cannot. A (k, n)-XVCS achieves the same goal with a better contrast on the reconstructed result of any k “XOR”ed shares. It has been proved that a (k, n)-VCS is also a (k, n)-XVCS. However, the monotonously increasing property (that any k+1,k+2,...,n shares also reveal P) in most conventional (k, n)-VCSs is not guaranteed when they are applied as (k, n)-XVCSs. This paper aims at developing efficient and flexible constructions for (k, n)-XVCSs with minimal pixel expansions, such that the monotonously increasing property, or even the flawless reconstruction of P when n shares are “XOR”ed, could be additionally fulfilled. Property analyses and comparisons against Tuyls et al.'s schemes are examined to demonstrate the applicability and superiority (in terms of the pixel expansion) of our schemes.

Given a secret image S, a set P of n participants and a strong access structure (ΓQual, Γ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 ΓQual can reveal S by superimposing their shares; whereas those of any forbidden set in Γ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 ≤ 4; but no more reliable for those of n ≥ 5.

This paper re-examines the problem of visual secret sharing for general access structures by using visual cryptograms of random grids (VCRG). Given a binary or color secret image shared by a set ofnparticipants with a strong access structure, we devise two effective algorithms to produce a set of VCRG so that the members in each qualified set can reconstruct the secret image by superimposing their shares, while those in any forbidden set cannot. Our algorithms do not require any extra pixel expansion, which is indispensable and grows exponentially asnincreases in conventional visual cryptographic schemes. The feasibility, light contrasts, flexibility, and limitations of our algorithms are explored from both theoretical and empirical points of view.

A conventional threshold (kout ofn) visual secret sharing scheme encodes one secret imagePintontransparencies (called shares) such that any group ofktransparencies revealsPwhen they are superimposed, while that of less thankones cannot. We define and develop general constructions for threshold multiple-secret visual cryptographic schemes (MVCSs) that are capable of encodingssecret imagesP1,P2,...,Psintonshares such that any group of less thankshares obtains none of the secrets, while 1) each group ofk,k+1,...,nshares revealsP1,P2, ...,Ps, respectively, when superimposed, referred to as (k,n,s)-MVCS wheres=n-k+1; or 2) each group ofushares reveals P(ru) whereru∈ {0,1,2,...,s} (ru=0 indicates no secret can be seen),k≤u≤nand 2 ≤s≤n-k+1, referred to as (k,n,s,R)-MVCS in whichR=(rk,rk+1, ...,rn) is called the revealing list. We adopt the skills of linear programming to model (k,n,s) - and (k,n,s,R) -MVCSs as integer linear programs which minimize the pixel expansions under all necessary constraints. The pixel expansions of different problem scales are explored, which have never been reported in the literature. Our constructions are novel and flexible. They can be easily customized to cope with various kinds of MVCSs.

With limited budget and inflation rate, the materials acquisition in multi-unit libraries has been a challenging issue all over the world. The materials acquisition for multi-unit libraries can be regarded as a generalized version of the knapsack problem, which was known to be NP-hard, with much more constraints. Thus, it can be computationally expensive to solve the problem. In this paper, the materials acquisition problem in multi-unit libraries is formulated as an integer programming model, and two different constraint-handling mechanisms applied in discrete particle swarm optimization algorithm for obtaining the near optimal solution are presented. It is evident from our computational results that one constraint-handling mechanism can solve the problem effectively and efficiently, while the other one takes more time.

A region incrementing visual cryptography scheme (RIVCS) deals with the sharing of an image consisting of multiple regions with different secrecy levels, which can be incrementally revealed as the number of shares increases. The encoding basis matrices of RIVCS for an image containing three to five regions have been reported in the literature, but no construction method has ever been studied. We develop a novel and efficient construction for RIVCS using linear programming in this paper. The proposed integer linear program aims at the minimization of the pixel expansion under the constraints for being a RIVCS. Experimental results demonstrate the feasibility, applicability, and flexibility of our construction. The pixel expansions and contrasts derived from our scheme are also better than the previous results.

The optimal pixel expansion of an (n,n) visual cryptographic scheme (VCS) was proven as 2n-1in 1995; and that of a (2,n)-VCS was proposed in 2002. Yet, most existing best pixel expansions of (k,n)-VCSs fork≥ 3 have not been improved since 1996. Whether they are already optimal, and if not how to find the optimums have never been explored. In this paper, we model the minimization of the pixel expansion in a (k,n)-VCS into an integer linear program to acquire the optimum solution. Computational results demonstrate that our integer linear program is simple, effective to obtain the optimum solution and flexible for coping with various types of (k,n)-VCSs.

We design innovative algorithms for visual multiple-secret sharing using circle or cylinder random grids in this paper. Formal validations, security analyses, and computer implementations are discussed to demonstrate the correctness and feasibility of our algorithms. As compared to the schemes developed in conventional visual cryptography, our design delivers three significant advantages: (1) it is capable of sharing multiple (instead of only one or two) secret images in two shares; (2) it does not result in any extra pixel expansion so that the sizes of the secret image and the encrypted shares are exactly the same; and (3) it is simple and easy to implement. These advantages broaden the potential applicability and flexibility of visual secret sharing schemes.

As the population of books and other materials increases explosively, an effective plan for material acquisitions becomes an emergent and significant need for most modern academic libraries. However, there are few researches on this topic in the past decades. We thereby propose a formal model for material acquisitions that resembles the practical situations of academic libraries. In the proposed model, we consider several features for each material (including the preference, price and its categories) as well as the budget for each category. The goal is to select materials to achieve a maximum total preference under the constraint that the acquisition for each category of materials is controlled by a predefined budget. With the computational complexity of the studied problem, we seek to produce approximate solution in a reasonable time. Three meta-heuristics, namely simulated annealing, genetic algorithm and tabu search, are developed to cope with this problem. Computational results reveal that tabu search is the most elegant approach among the three for the material acquisitions problem.

We extend the sharing scheme proposed by Mignotte in 1983 based upon Chinese remainder theorem (CRT) to devise a threshold secret sharing scheme for digital images. Given a secret image I and a set of n participants sharing I, our scheme encrypts I into n shadows in such a way that any group of r shadows can recover I while that of less than r shadows cannot where 2 ≤ r ≤ n. As compared to the similar work by Meher and Patra in 2006, which is not a threshold scheme, our design satisfies the threshold requirements so that it is more technically sound. Our work reveals a new research area of applying CRT in secret image sharing.

The ant colony optimization is a meta-heuristic inspired by knowledge sharing amongst ants using pheromone, which serves as a kind of collective memory. Since the past few years, there have been several successful applications of this new approach for finding approximate solutions for computationally difficult problems in reasonable times. In this paper, we study the generalized minimum spanning tree problem that involves the design of a minimum weight connected network spanning at least one node out of every disjoint subset of the nodes in a graph. This problem has a wealth of pertinence to a wide range of applications in different areas. As the problem is known as computationally challenging, we adopt the ant colony optimization strategy and present a new solution method, called Ant-Tree, to develop approximate solutions. As an initial attempt, our study aims to provide an investigation of the ant colony optimization approach for coping with tree optimization problems. Through computational experiments, we compare the performances of our approach and the method available in the literature. Numerical results indicate that the proposed method is effective in producing quality approximate solutions.