# Fault-Tolerant Visual Secret Sharing Schemes without Pixel Expansion
## 1 Introduction  
In 1995, [PERSON] and [PERSON] proposed visual cryptography (VC) (also called visual secret sharing (VSS)), which is a way to encrypt one secret image, such that it can be decoded by human vision without any calculation [1]. The concept is to encrypt a secret image \(S\) into two meaningless random images \(G_{1}\) and \(G_{2}\), each called a share (also called sheet, shadow), of which one can be seen as a cipher text, and the other is a key to it. Stacking them is the only way to restore the hidden secret. Random grid-based VSS, invented by [PERSON] and [PERSON] [2], received more attention in recent years, such as [3; 4; 5; 6; 7; 8; 9]. This method takes each pixel as a grid on the image and applies the concept of random variables to encrypt images.  
For VSS, the secret image can be visually reconstructed with shares, printed on transparencies and stacked precisely on an overhead projector. A slight misalignment between the shares could increase the difficulty of identification in image reconstruction. The smaller the size of the shares, the more difficult it will be when you restore the secret image. Therefore, some literature studies this misalignment problem (also called fault-tolerance), such as [10; 11; 12; 13; 14; 8; 15]. [PERSON] and [PERSON] proposed an extended VSS scheme that can enhance the registration tolerance when stacked shares are not aligned perfectly in 2004 [14]. It transfers the secret image into black and white values with the half-tone technique and then encrypts into two random images. The difference from other methods is that one of the random images is larger than the other in a diamond pattern, leading to a certain level of fault tolerance when stacking the shares. In such a pixel expansion-based scheme, the size of the shares and the restored image in their scheme will be 49-times the original secret image. This increases the cost on data restoration and transmission and also makes its implementation inconvenient.  
A (\(k\), \(n\))-threshold scheme means that the dealer encrypts secret \(S\) into \(n\) shares and delivers each to one participant, such that any \(k\) (or more) participants can recover the secret by combining theirshares, while less than \(k\) participants cannot. A (\(k\), \(n\))-threshold VSS scheme is a visual version of the (\(k\), \(n\))-threshold scheme, _i.e._, stacking any \(k\) (or more) shares directly can reconstruct the secret image \(S\). In 2009, [PERSON] _et al._ considered the misalignment problem in the VSS scheme and designed a misalignment-tolerant VSS scheme based on the trade-off between the usage of big and small blocks to address this misalignment problem [15], called the MTVSS scheme. It is not necessary to align the transparencies precisely. Their scheme can solve the misalignment problem for the (\(k\), \(n\))-threshold VSS scheme. They also propose a useful parameter, CI (correctness index), to represent the quality of the restored image intuitively. However, that scheme also involves pixel expansion. Therefore, this paper is based on [PERSON] and [PERSON]'s idea to design the (2, 2)-threshold visual secret sharing scheme, such that the misalignment problem can be solved without pixel expansion. We shall use the same parameter CI to compare the performance of our schemes to the MTVSS scheme.  
The rest of this paper is organized as follows. Section 2 introduces the detailed techniques mentioned above. Section 3 discusses the major findings. In particular, we design four VSS schemes with analysis showing that they achieve better fault tolerance. Section 4 presents the fault tolerance result of various proposed schemes by simulations. Finally, our conclusions are given in Section 5.