Informatica

A secret sharing scheme is any method of distributing a secret amongst a number of participants in such a way that any authorized group of participants can recover the secret, while unauthorized sets of participants are unable to obtain any information about the secret using their shares. In a k-out-of-n secret sharing scheme, there are n participants and every collection of k or more participants is authorized to recover the secret, while fewer than k participants constitute an unauthorized set. The number k is referred to as the threshold and the scheme is usually referred to as a $(k,n)$-threshold secret sharing scheme, or a $(k,n)$-scheme for short. While there exist other approaches such as those where authorized sets of participants are specified by properties other than merely the size of the subset, in this work we focus on $(k,n)$-schemes.

The concept of secret sharing was introduced in 1979 independently by Shamir (1979) and Blakley et al. (1979). Shamir’s method is based on polynomial interpolation in the field ${\mathbb{F}_{p}}$ of integers modulo p, whereas Blakley’s method is based on hyperplane geometry. In the early eighties, Mignotte (1982) and Asmuth and Bloom (1983) proposed a threshold secret sharing approach based on the Chinese remainder theorem. Secret sharing schemes are important primitives in a number of cryptographic applications such as threshold signature (authentication) schemes (Desmedt and Frankel, 1991), access control (Naor and Wool, 1998), electronic voting (Schoenmakers, 1999), distributed storage systems (Wylie et al., 2000), etc.

Because of the widespread use of digital images, development of secret image sharing schemes (SIS) where the secret is a digital image have attracted the attention of researchers. In the context of an SIS, shares are often referred to as shadow images. We refer to a $(k,n)$-threshold secret image sharing scheme as a $(k,n)$-SIS for short. There are challenges specific to secret image sharing. For example, secret sharing was originally introduced for sharing cryptographic keys, thus sizes of shares were not much of a concern. On the other hand, since digital images are typically large, one is concerned with how large each shadow image is in comparison to the original secret. While Shamir’s scheme produces shares of the same size as the secret itself, Thien and Lin (2002) proposed a $(k,n)$-SIS inspired by Shamir’s scheme whose shadow images are of size $1/k$ the size of the secret. Lin and Tsai (2004) extended Shamir’s scheme in proposing a secret image sharing scheme with the capabilities of steganography and authentication. Chang et al. (2008) showed that this scheme suffers from weak authentication and low quality of stego-images. In Bai (2006), Bai proposed a $(k,n)$-SIS based on matrix projection in conjunction with Thien and Lin’s approach (Thien and Lin, 2002). del Rey (2008) proposed a $(2,n)$-SIS using binary matrices. Rey’s scheme is shown to suffer from some drawbacks if the matrices are not of low enough rank (Elsheh and Hamza, 2010). Many Shamir-based SIS use arithmetic in the fields ${\mathbb{F}_{251}}$ or ${\mathbb{F}_{257}}$ to accommodate 8-bit intensity values of digital images. This choice renders such schemes lossy since they involve truncation of some values. Hu et al. (2012) proposed a lossless $(k,n)$-SIS over the Galois field ${\mathbb{F}_{{2^{8}}}}$. In El-Latif et al. (2013), Abd El-Latif et al. proposed a secret image sharing scheme based on random grids and error diffusion and a chaotic cat map for the generation of meaningful shadow images. Wu (2013) proposed a variant of Thien–Lin’s scheme (Thien and Lin, 2002) which uses prime number 257 as a replacement for 251 in Thien–Lin’s approach. Wu’s scheme has a low distortion rate, and is more applicable for light images (Wu, 2013). However, due the overflow caused in the generation phase of this scheme, reconstruction of the secret image is more computationally intensive than in the case of Thien–Lin’s scheme. In Zarepour-Ahmadabadi et al. (2016), Zarepour-Ahmadabadi et al. proposed an SIS based on cellular automata. Deng et al. (2017) proposed a $(2,n)$-threshold SIS based on basic vector operations and coherence superposition. Kanso and Ghebleh (2017) proposed a variant of Thien and Lin’s scheme based on cyclic shifting to improve the quality of the reconstructed secret image. Kabirirad and Eslami (2018) proposed a multi secret SIS based on Boolean operations whose drawback is that each generated shadow image has the same size as the secret image. Ghebleh and Kanso (2018) proposed a $(k,n)$-SIS based on Shamir’s approach and arithmetic in a field ${\mathbb{F}_{p}}$ where p is a large prime, to facilitate the use of (concatenated) multiple intensity values of the secret image as a single coefficient. While still lossy, this method enhances the quality of the reconstructed secret. Ding et al. (2018) proposed a scheme based on matrix theory and Shamir’s construction. Recently, Kanso and Ghebleh (2018) proposed a $(k,n)$-threshold secret sharing scheme for medical images based on Shamir’s approach and the high redundancy in medical images. Some secret image sharing schemes such as Chang and Hwang (1998), Chang et al. (2006), Chen et al. (2009), Le et al. (2011) employ vector quantization (VQ) methods (Gray, 1984; Gersho and Gray, 2012; Simić et al., 2018) to compress the secret image, which results in further reduction in the sizes of the shadow images.

A majority of existing secret image sharing schemes in the literature are based on one of Shamir’s (1979), Blakley’s et al., (1979), Mignotte’s, (1982) and Asmuth and Bloom’s, (1983) approaches. Furthermore, many of the existing schemes are lossy and restore the secret image with some distortion which may not be acceptable in certain applications. Moreover, some existing SIS suffer from weak authentication and security issues. The aim of this research is to present a secret sharing scheme that has improved performance over existing work.

In this paper, we propose a lossless linear algebraic $(k,n)$-SIS. As illustrated later, the proposed scheme is a generalization of Shamir’s secret sharing scheme based on polynomial interpolation. The scheme associates a vector ${\mathbf{v}_{i}}$ to the ith participant in the k-dimensional vector space ${\mathbb{F}_{q}^{k}}$ over the Galois field ${\mathbb{F}_{q}}$, where q is a power of 2. The ith share is then computed as a linear combination of the vectors ${\mathbf{v}_{i}}$ with coefficients computed from the secret. For the threshold property of secret sharing, and for security of shares, some admissibility conditions (such as linear independence of certain sets) are enforced on the vectors ${\mathbf{v}_{i}}$. Empirical results presented in the paper illustrate the proposed scheme’s performance. These include security of shadow images and the recovery process. More specifically, it is shown that the produced shadow images satisfy randomness properties which in turn means that the shadow images do not reveal any meaningful information about the secret image. Moreover, shadow images have little or no correlation. It is also shown that any unauthorized collection of shadow images fails to produce any information about the secret image. The proposed scheme is lossless, which means that it can be used for sharing any type of digital data (as secret), including text and binary files such as compressed images generated via vector quantization.

The paper is organized as follows: In Section 2, we present the necessary background and notation. Section 3 provides a detailed description of the proposed scheme. Simulations are presented in Section 4 to showcase the efficiency of the scheme, the properties of the generated shadow images and security analysis. Section 5 presents a comparison of the scheme with existing work. Finally, we end the paper with some concluding remarks.

We propose a secret image sharing scheme based on Shamir’s approach (Shamir, 1979). In this section we lay out the necessary background and notation, as well as differences between the proposed scheme and Shamir’s scheme.

Shamir’s $(k,n)$-scheme is based on polynomial interpolation in the field ${\mathbb{F}_{p}}$ where p is a prime number. To share secret $D\in \{0,1,\dots ,p-1\}$, a polynomial is chosen at random with ${a_{0}}=D$. Then the values $f(i)$ where $i\in \{1,2,\dots ,n\}$ are computed and distributed to the participants as shares. With the obvious conditions that $k\leqslant n<p$, the polynomial interpolation theorem guarantees that every k shares suffice to recover $f(x)$, and in particular the secret D. Following the notation of Spiez et al. (2009), Schinzel et al. (2010), this can be generalized by fixing pairwise distinct nonzero values ${x_{1}},{x_{2}},\dots ,{x_{n}}\in {\mathbb{F}_{p}}$ and using ${y_{i}}=f({x_{i}})$ as the ith share. With this notation, computation of shares can be summarized as Let $\mathbf{a}=({a_{0}},{a_{1}},\dots ,{a_{k-1}})$, $\mathbf{y}=({y_{1}},{y_{2}},\dots ,{y_{n}})$, and X be the $n\times k$ matrix in the above equation. For convenience, we identify vectors such as a and y with their row or column matrix representation. Then the above equation can be written as Simple linear algebra gives the following: The track $\mathbf{x}=({x_{1}},{x_{2}},\dots ,{x_{n}})$ is said to be admissible if it satisfies the nonsingularity conditions discussed above. Admissible tracks are studied in Schinzel et al. (2010), Spież et al. (2012).

In this work, we consider a general matrix X for computation of the shares vector y. By destroying the algebraic relations between columns of X, this idea allows more “randomness” in the shares, thus potentially making the scheme more secure. On the other hand, the lack of algebraic relations in X renders the theoretical study admissibility impractical, and each X must be verified directly. We propose to choose X randomly from the set of all $n\times k$ matrices over the given field, then check its admissibility. If the field has large enough cardinality, this process has a high probability of success.

Thien and Lin (2002) proposed a secret image sharing scheme (SIS) where all coefficients of the polynomial $f(x)$, namely components of a, are chosen from the secret. As long as the secret image is properly shuffled to eliminate correlations between entries of a, this scheme works similarly to Shamir’s scheme with the following two advantages:

We follow the same approach in this work and pick all components of the vector a from the shuffled secret image. Since a digital image typically has a large size compared to the parameters k and n of the scheme, elements of the secret are processed k at a time. This can be utilized by allowing y and a to have more than one column. More specifically, we write the proposed SIS as where S is a $k\times m$ matrix obtained by padding, shuffling, and reshaping the secret image, X is an admissible $n\times k$ transformation matrix, and the $n\times m$ matrix Y is the matrix of shares, whose ith row constitutes the ith share.

The final difference between the proposed scheme, Shamir’s, and Thien and Lin’s schemes is the use of the field ${\mathbb{F}_{q}}$ where $q={2^{\alpha }}$ instead of ${\mathbb{F}_{p}}$ where p is a prime. Since digital media typically contain values from a domain $\{0,1,\dots ,{2^{\alpha }}-1\}$, the use of a field ${\mathbb{F}_{p}}$ involves truncation of some values which renders such secret sharing schemes lossy. Depending on the application, this might be acceptable or not. While computations in ${\mathbb{F}_{p}}$ are faster, the field ${\mathbb{F}_{q}}$ where $q={2^{\alpha }}$ is the natural choice for a lossless scheme. Since digital images typically consist of bytes of information, it is convenient for α to be a multiple of 8. If $\alpha =8\beta $, the entries ${s_{ij}}$ of the matrix S are each a concatenation of β entries of the secret image.

It should be noted that as mentioned above, for the random selection of the transformation matrix X to have a high probability of admissibility, the field ${\mathbb{F}_{q}}$ must have a large cardinality. In the empirical analysis presented in this work we choose $\alpha =16$ and carry all computations in the field ${\mathbb{F}_{q}}$ where $q={2^{16}}$.

Following the notation of the previous section, the proposed SIS is summarized as where X is an admissible transformation matrix, S is the secret image (subjected to concatenation of entries, shuffling, padding and reshaping), and Y is the shares matrix. All these matrices have entries from a field ${\mathbb{F}_{q}}$ where $q={2^{\alpha }}={2^{8\beta }}$ for some chosen parameter β. In this section, we present in more detail the generation of the matrices X and S, and the generation of shadow images using them. For added security, the secret image may be divided into several blocks, where each block is processed separately (with an independent transformation matrix X). In this case a parameter m specified by the user defines the number of columns of the matrix S corresponding to each block.

The parameters of the proposed scheme which are kept constant throughout this section are the number β of bytes in each entry of S, the number n of the participants, the threshold k, and the block size m. With fixed β, we also fix an ordering of the elements of the field ${\mathbb{F}_{q}}$ where $q={2^{8\beta }}$, say ${\mathbb{F}_{q}}=\{{f_{0}},{f_{1}},{f_{2}},\dots ,{f_{q-1}}\}$ where ${f_{0}}=0$. Throughout our discussions, we use the correspondence to move between the field ${\mathbb{F}_{q}}$ and the group ${\mathbb{Z}_{q}}$ of integers modulo q.

In this section, we demonstrate the efficiency of the proposed scheme and its robustness against a number of attacks. The simulation results are based on the following parameters: the number of bytes per value $\beta =2$, the number of participants $n=6$, the threshold (minimum number of participants in an authorized set) $k=4$, and $m=1024$. For the tests presented in this section, we use the cat matrix obtained using the parameters $({a_{x}},{a_{y}},{a_{z}};\hspace{0.1667em}{b_{x}},{b_{y}},{b_{z}})=(2,1,117;\hspace{0.1667em}31,2,3)$.

Recall that each block of the process involves $mk\beta =8192$ bytes of the secret, resulting in 4096 elements of the field ${\mathbb{F}_{q}}$ with $q={2^{16}}$. Consider the standard grayscale image Lena of size $512\times 512$ presented in Fig. 1 to be the secret image. Then each shadow image consists of 65536 bytes since the size of each share is $1/k$ the size of the secret. For presentation, each ${H_{i}}$ ($1\leqslant i\leqslant n$) is reshaped into a $256\times 256$ matrix also denoted by ${H_{i}}$. Figure 2 depicts the six shadow images corresponding to the test image Lena.

In this section we compare the performance of the proposed approach, referred to by Pr-SIS, with few existing $(k,n)$-SIS schemes: TL (Thien and Lin, 2002), Wu (2013), KG (Kanso and Ghebleh, 2017), KE (Kabirirad and Eslami, 2018) and GK (Ghebleh and Kanso, 2018). All comparisons are performed with $(k,n)=(2,4)$ with the secret image Pirate of size $512\times 512$ presented in Fig. 10. The sizes of the generated shadows images are presented in Table 8.

In Table 9, we present the correlation coefficients between $N=10000$ pairs of randomly selected adjacent pixels in the horizontal, vertical and diagonal directions of sample shadow images generated by TL (Thien and Lin, 2002), Wu (Wu, 2013), KG (Kanso and Ghebleh, 2017), KE (Kabirirad and Eslami, 2018), GK (Ghebleh and Kanso, 2018) and Pr-SIS. It is evident from this table that all schemes generate shadow images almost free of any correlation between adjacent pixels.

Table 10 presents the entropy measures of sample shadow images of the schemes under comparison.

Table 11 presents the mean absolute difference of the secret image Pirate and the reconstructed image by the schemes under comparison. This table also presents the Peak Signal to Noise Ratio (PSNR) and The Structural Similarity (SSIM) measures between the secret image and the reconstructed one (Wang et al., 2004).

On the basis of the above results it is evident that the proposed scheme is competitive with existing schemes. Many existing secret image sharing schemes use arithmetics in the finite files ${\mathbb{F}_{q}}$ where q is a suitable prime. This yields in the need for truncation of values and, in turn, in all these schemes being lossy, and hence incapable of applications where the secret is sensitive. The proposed scheme, on the other hand, is defined on the field ${\mathbb{F}_{q}}$ where q is a power of 2. This choice is more suitable for handling binary data since with a proper choice of q one can avoid truncations of values. As shown in Table 8, among the schemes in comparison, only KE is lossless, but it is at a clear disadvantage to the proposed scheme Pr-SIS since each shadow image produced by KE has the same size as the original secret image.

In this research, we propose a lossless linear algebraic $(k,n)$-SIS which associates a vector ${\mathbf{v}_{i}}$ to the ith participant in the vector space ${\mathbb{F}_{q}^{k}}$, where q is a power of 2. Admissibility conditions are imposed on the vectors ${\mathbf{v}_{i}}$ to satisfy the threshold property of secret sharing. The scheme is shown to possess a number of characteristics such as robustness against standard statistical attacks, high level of security including sensitivity to its secret key, resilience to errors in shadow images, and reduction in the size of shadow images with respect to the size of the secret image. Another feature of the scheme is being lossless, which enables applications to digital media other than raw images. For example, the proposed scheme can be used for sharing textual data, JPEG images, video, etc.

The proposed scheme is very fast provided the admissibility of the transformation matrix is verified beforehand. This step is independent of the secret image and does not present any security risks to the process of secret image sharing. On the other hand, checking admissibility is costly in general and could be considered as a disadvantage of the proposed scheme if it is not performed independently of the secret sharing itself. Processing time and shadow image size can be further reduced if the proposed scheme is used in conjunction with image compression algorithms such as those based on vector quantization.