8.1. Introduction

The concept of secret sharing was developed in the late 1970s by Blakley (1979). Shamir (1979) worked independently, to solve the problems associated with the classic encryption approaches described in Chapters 4, 6 and 7. A major drawback of these approaches is that they require a key, and that the secret is limited to a single container. The container may be lost, destroyed or tampered with during an attack, meaning that the secret can no longer be retrieved. The applications of secret sharing have evolved since the 1980s. Nowadays, secret sharing offers a response to new problems such as secure multi-party computation, solving the Byzantine agreement problem, access control or attribute-based encryption (Beimel 2011). Secret sharing is presented as a keyless encryption approach, whereby a secret may be distributed to multiple users and reconstructed when a subset of these users collaborate to do so. The user who initially shares the secret is known as the dealer.

As we see from Figure 8.1, during the sharing phase, the dealer generates shares of the secret S denoted as s_i. Each share is assigned to a user among n such that i ∈ The shares are not disjointed parts of the secret S, but information computed from the secret S allowing it to be reconstructed. Taken individually, these shares do not provide any information about the secret S. To reconstruct the secret, at least k shares among those held by n users are needed. Any group of users with fewer than k of n members will be unable to reconstruct the secret.

This first approach to secret sharing is called the (k, n)-threshold method. This definition was extended and generalized by Ito et al. (1989), who defined a secret sharing method involving a secret, a set of users and a general access structure, that is, a collection of subsets with the capacity to reconstruct the secret. Note that this definition removes the minimum threshold principle, enabling generalization for user sets of different sizes.

The construction and/or the organization of their access structure means that some secret sharing methods have particularly interesting properties (Simmons 1988; Brickell 1989; Brickell and Davenport 1991; Brickell and Stinson 1992; Tassa 2004; Belenkiy 2008; Beimel 2011), insofar as they can be considered to be perfect, ideal, verifiable or clearly hierarchical.

A secret sharing method is said to be perfect when only a subset of the users can reconstruct the secret S and no information, in the theoretical sense, about S is revealed to other users. Methods such as those defined by Shamir (1979); Brickell and Stinson (1992); Lin et al. (2009) can be considered as perfect, while Blakley’s method cannot (Blakley 1979).

Furthermore, a secret sharing method is said to be ideal when, for any secret S and any share generated from S, the shares are the same size (in bits) as the input secret (Brickell 1989). Shamir’s method is one example of an ideal approach. The search for ideal secret sharing methods is an important subject for research. In contrast, other methods have focused on trying to reduce share size in order to optimize storage and transmission time (Krawczyk 1993).

Some secret sharing methods incorporate fault detection mechanisms with the ability to detect the provision of wrong shares by malicious users, aiming to prevent the reconstruction of the secret (Chor et al. 1985; Benaloh 1986; Zhao et al. 2007; Harn and Lin 2009). These mechanisms can be used to correct faults (Benaloh 1986) and identify users with ill intent (Harn and Lin 2009).

Finally, several secret sharing methods have proposed a hierarchization of users by groups or levels (Simmons 1988; Tassa 2004; Belenkiy 2008; Farràs et al. 2012; Nojoumian and Stinson 2015). In this type of approach, users have a different level of access to the secret; in classical thresholded methods, all users are at the same level. These methods can then be used as a basis for attribute-based encryption approaches. Simmons (1988) considers a system where users are divided into different groups, and each group is assigned a threshold that must be reached to allow the reconstruction of the secret by that group. Simmons also described two types of hierarchies for hierarchical secret sharing methods: multilevel sharing methods (multilevel threshold secret sharing scheme) and compartmentalized sharing methods (compartmented threshold secret sharing scheme).

While secret sharing methods were first developed for use with textual data, the increasing volume of multimedia data transiting over networks means that an adaptation of these methods for images and 3D objects is increasingly relevant. In section 8.2, we provide a brief introduction to classic secret sharing methods, along with the hierarchical aspects of some approaches. In section 8.3, we describe the principle of secret image sharing and the associated state-of-the-art methods. In section 8.4, we present work on the subject of secret 3D object sharing. Finally, in section 8.5, we describe an application of secret image sharing to social networks.

8.2. Secret sharing

We shall begin by presenting Shamir and Blakley’s methods (Shamir 1979; Blakley 1979) in section 8.2.1. We then address the hierarchical property, introducing two hierarchical secret sharing methods based on Shamir’s method, developed by Tassa (2007) and Belenkiy (2008).

8.2.1. Classic methods

8.2.1.1. Shamir’s method

In Shamir’s method, the secret S is considered as an element in a finite body (Shamir 1979). In this approach, the secret is protected by using polynomials over a finite body such that as the cardinal of a finite body and p as a prime number, respecting the condition:

[8.1]

with k as the minimum number of users required to reconstruct the secret and n as the maximum number of share holders.

Using parameters (k, n), this method distributes a set of shares for each of the n users, and allows the secret to be reconstructed when at least k of the n users pool their shares to solve a polynomial interpolation problem. No information concerning the secret will be revealed when using a subset of only (k − 1) shares. During the sharing step, each user receives a unique identifier x_j, where A polynomial of degree (k − 1) is then constructed, such that (k − 1) integers are randomly selected to form the set with and

[8.2]

Thus, f(0), which is equal to a₀, corresponds to the value of the secret S. Each of the n users receives an information pair s_j = (x_j, y_j = f(x_j)).

As we can see from Figure 8.2, the secret S can be reconstructed using a polynomial interpolation with at least k shares. These shares may be interpreted as points belonging to the selected polynomial. In Figure 8.2, for example, points s₀ = (x₀, f(x₀)) and s₁ = (x₁, f(x₁)) may be used to interpolate the polynomial of degree 1 f(x) represented by the red line. The codecolorBlue curve in Figure 8.2 represents a polynomial of degree 2, which can reconstruct the secret S when at least three points are used to interpolate the polynomial. The green curve is a polynomial of degree 3, allowing the reconstruction of the secret S using four or more points. Interpolation is applied to determine the value of f(0) of the polynomial, corresponding to term a₀ and, by definition, to the secret S. To reconstruct the secret S, a group of at least k users can determine the coefficients used in the polynomial f(x) during the sharing step by means of Lagrange interpolation:

[8.3]

8.2.1.2. Blakley’s method

The very same year, Blakley proposed a secret sharing method using hyperplanar geometry (Blakley 1979). The secret S is defined as a point in a k-dimensional space such that Each user is supplied with a hyperplane of dimension k, such that point S is present in all of the distributed hyperplanes. In formal terms, a hyperplane of dimension k noted H is defined by equation [8.4]:

[8.4]

where a_i with is the ith coefficient of the hyperplane of dimension k defined by the set a = {a_i} and b is the coefficient.

Using hyperplanar geometry, the secret point is the point of intersection of any group of k or more hyperplanes. Figure 8.3 shows the intersection of hyperplanes at a single point for k = 2 (see Figure 8.3(a)) and for k = 3 (see Figure 8.3(b)), respectively. The distributed shares are thus hyperplanes of dimension k, and more precisely the coefficients of the equation representing the hyperplane

8.2.2. Hierarchical aspects

For some applications, it may be necessary to define a hierarchy of users to provide higher control over access to secret content. For example, in a bank with a safe, it is natural to expect that access to the safe will require the presence of bank employees, some of whom are members of management. Imagine a scenario where three employees, including one manager, or alternatively two managers, must be present in order to open the safe. This example illustrates the use of hierarchical approaches to build an access control structure that varies according to case-specific requirements. In this context, the definition of secret sharing must be extended, adjusting the secret reconstruction process according to the users present. This hierarchical aspect, which we touched on briefly in section 8.1, was first introduced by Simmons (1988).

A hierarchical secret sharing method is defined by several parameters noted (L, k, n), where L is the number of levels in the hierarchy, is the minimum number of users per level for reconstruction is the maximum number of possible users per level. This approach was developed in response to a need to limit secret access to an authorized set of users. Users belong to groups defined as a function of their position, role or level in the hierarchy:

[8.5]

where u is a user belonging to a group of authorized users U and the user group of level

In the literature, hierarchy defines how users and groups organize the secret access structure together. Hierarchical secret sharing methods correspond to the implementation of these hierarchies in the context of secret sharing approaches. Different types of hierarchies may be defined, based on their uses and objectives (Simmons 1988).

8.2.2.1. Compartmented hierarchical secret sharing

The first category, presented by Simmons (1988), corresponds to compartmented hierarchical secret sharing, or CHSS, schemes. This category corresponds to an access structure with several user groups, where a consensus must be reached within each user group in order to reconstruct the secret. In the case of compartmentalized hierarchical sharing methods, user groups are defined as follows:

[8.6]

Each user u belongs to a group The different groups of users are distinct from one another. In a compartmented hierarchy, each group must attain a certain threshold assigned to the group in order to reconstruct the secret. As the groups are distinct from one another, users in a group will not count toward the threshold of a group . For this reason, if one or more thresholds are not attained in a group , the secret will not be revealed. Figure 8.4 shows an example of a CHSS method with parameters L = 4, k = (k₀ = 2, k₁ = 3, k₂ = 2, k₃ = 4) and n = (n₀, n₁, n₂, n₃). These parameters indicate that four disjunct user groups must each reach a consensus in order to reconstruct the secret. In this particular case, the CHSS method requires two users from set U₀, three from set U₁, two from set U₂ and four from set U₃.

The most naive implementation of a CHSS method consists of applying a secret sharing method sequentially. First, the secret S is shared, using the parameters (k = L, n = L), in order to generate L shares (s₀, s₁, . . . , s_L−1). Next, each of these L shares is shared again between the members of the same group with parameters , as shown in Figure 8.5.

8.2.2.2. Multi-level hierarchical secret sharing

A second category is made up of multi-level hierarchical secret sharing methods, with an access structure in which users are grouped by access level. Following Simmons’ proposals (Simmons 1988), the level defines the position of users in the hierarchy and their capacity to reconstruct the secret with fewer users. Unlike compartmented hierarchical sharing methods, in which users are split into disjoint groups, multilevel hierarchical sharing methods use nested groups:

[8.7]

One specificity of multilevel hierarchical sharing methods is that different levels are arranged in an order, such that:

[8.8]

The highest level is labeled 0 and the lowest level is (L – 1). During reconstruction, the method must verify whether the threshold for level has been reached (beginning with l = 0) with the presence of at least users belonging to the group . If the number of users is sufficient at level , then the secret will be reconstructed directly based on this set of users. Otherwise, users from level will be considered as users at level ( + 1), and can thus count toward the threshold .

Figure 8.6 shows a multilevel hierarchy. Users at the highest level can reconstruct the secret more rapidly. For example, in group U₀, fewer users are needed to reconstruct the secret than for groups U₁, U₂ or U₃. However, this only works with users on the same level (or higher levels), that is, belonging to the same group. Thus, if the number of users in U₀ present at the point of reconstruction is below the threshold k₀, then the secret remains protected. Nevertheless, they can participate in reconstruction in association with users of a lower level.

8.2.2.3. Tassa’s method

The article by Tassa (2007) proposed a hierarchical secret sharing method that combines the two types of hierarchies presented in sections 8.2.2.1 and 8.2.2.2, using Shamir’s secret sharing method (Shamir 1979). The purpose of this new type of hierarchy is to allow reconstruction when enough users at all levels of the hierarchy participate, that is, with a minimum number of users per level. The particularity of this approach lies in the fact that higher level users participate in the consensus of the lower levels. Tassa’s proposed method is based on a polynomial of degree (k_L−1 − 1) (see equation [8.2]), and the secret S is hidden in coefficient a₀ of the selected polynomial (Tassa 2007). Tassa’s method then transmits the information pair to the ith user belonging to level where is the level of user and is the Tassa polynomial associated with level . The Tassa polynomial associated with level is the Shamir polynomial f derived times and noted :

[8.9]

with k₋₁ = 0.

For example, for three hierarchical levels with thresholds k = (k₀, k₁, k₂), reconstruction of the secret requires the presence of at least k₀ level 0 users, k₁ level 1 users and k₂ level 2 users. The polynomials used for each level of the hierarchy are given as:

[8.10]

Taking k = (2, 3, 4) for the thresholds k₀, k₁ and k₂ and replacing the variables by their values, we obtain the following polynomials:

[8.11]

The polynomial g₀ used for the highest level, level 0, is equal to the Shamir polynomial f of degree (k_L−1 − 1) without derivation, while the polynomial g₁ for users of level 1 is equal to f derived twice, following equation [8.9], since k₀ = 2. The polynomial used for level 2 users is equal to f derived three times, following equation [8.9], since k₁ = 3.

Figure 8.7 shows the list of groups with the ability to reconstruct the secret in Tassa’s method (Tassa 2007), with thresholds k = (k₀ = 2, k₁ = 3, k₂ = 4). In Tassa’s proposed hierarchy, users of level 0, 1 and 2 are required to reconstruct the secret. However, as we can see from Figure 8.7, users of level 0 can act as users of levels 1 or 2 for reconstruction purposes. The final group of users shown in Figure 8.7 represents the minimal configuration needed to reconstruct the secret, with two level 0 users, one level 1 user and one level 2 users. Although the hierarchy requires two level 0 users, three level 1 users and four level 2 users, this configuration is possible because the level 0 users also count toward the level 1 and level 2 groups. By adjusting the number of users per level, the presence of certain users may be made compulsory in order to reconstruct the secret. Reconstruction is carried out using a Hermite–Birkhoff interpolation (Schoenberg 1966). A Hermite–Birkhoff interpolation is a means of identifying the unique solution to a linear system formed by a reduced set of users, valid for reconstruction purposes. Formally, when a hierarchical secret sharing method is used in the way defined by Tassa (2007), a matrix relationship is obtained for each group of users authorized to reconstruct the secret, such that:

[8.12]

[8.13]

where as the number of users (across all groups) participating in secret sharing as two level 0 users, as a level 1 user and as a level 2 user. A is the polynomial coefficient vector, X is the matrix of polynomials calculated (without coefficients) and derived (or non-derived) for each user belonging to the reconstruction group, and b is the result of the polynomials for each user.

The user group is a group with the capacity to reconstruct the secret according to Tassa’s method (Tassa 2007).

By solving the linear system X × A^T = b, we can deduce the set of coefficients A used in the polynomials.

8.2.2.4. Belenkiy’s method

Belenkiy’s hierarchical secret sharing method builds on Tassa’s approach (Tassa 2007) to create a new, less restrictive multilevel hierarchy (Belenkiy 2008). In this hierarchy, the secret can be reconstructed when the number of users reaches the associated threshold value . To create this hierarchy, Belenkiy suggested hiding the secret in the final coefficient of the Shamir polynomial a_k−1 instead of in a₀ (see equation [8.2]) (Belenkiy 2008). Furthermore, since higher level users receive derivatives of the Shamir polynomial, they can begin reconstructing the secret once the threshold for their level has been reached. If the corresponding threshold is not reached, then users at level can participate in reconstruction for the next level ( + 1) with the corresponding threshold . Let be the Belenkiy polynomial used to distribute shares to users of level . Thus, taking the same example as before with parameters k = (k₀ = 2, k₁ = 3, k₂ = 4), a polynomial of degree 3 will be used (since k_L−1 = 4). The value of coefficient is assigned to that of the secret, and for each level , the polynomial is derived times:

[8.14]

In this case, a group of users, where is the level of the attained threshold, will be able to reconstruct the final coefficient containing the secret, as shown in Figure 8.8.

Figure 8.8 shows the set of user groups with the capacity to reconstruct the secret according to Belenkiy’s method for three hierarchical levels, and with thresholds k = (k₀ = 2, k₁ = 3, k₂ = 4) (Belenkiy 2008). Users in level U₀ can reconstruct the secret if at least two members are present, whereas a minimum of three users of level U₁, or four users of level U₂, will be required to reconstruct the secret according to Belenkiy’s hierarchy (Belenkiy 2008). As we can see from Figure 8.8, a user of level 0 will not be able to reconstruct the secret alone, but can join users of level 1 or 2 to participate in reconstruction at this level. The final group shown in Figure 8.8 represents the minimal configuration, with four level 2 users who have the ability to reconstruct the secret.

Using the multi-level approach, higher level users can reconstruct the secret faster, or at least help reconstruct the secret with lower level users. As in the case of Tassa’s method, Belenkiy’s method relies on a Hermite–Bikhoff interpolation to reconstruct the secret. Taking the same example as in Figure 8.8, the level 0 users can reconstruct the secret through their information pair , according to the following matrix relationship:

[8.15]

[8.16]

Solving the linear system X × A^T = b gives a single possible solution for coefficients a₂ and a₃, where a₃ contains the value of the secret.

8.3. Secret image sharing

As we saw in section 8.2, the concept of secret sharing was initially developed for the management of secret cryptographic keys (Blakley 1979; Shamir 1979). Naor and Shamir (1994) proposed an adaption of the concept of secret sharing for the domain of 2D imaging. The authors provided the first definition of visual secret sharing, where the secret is the content of an image. The secret image sharing principle is presented in section 8.3.1. Section 8.3.2 provides a description of visual cryptography, one of the earliest approaches to visual secret sharing. In section 8.3.3, we present secret image sharing methods based on polynomial approaches, ensuring that the reconstructed secret image will be of the best possible quality. Finally, in section 8.3.4, we present the main properties of secret image sharing methods.

8.3.1. Principle

Just like secret sharing methods, secret image sharing methods can be split into two parts: sharing and reconstruction. As we can see from Figure 8.9, the input for the method consists of a secret image and parameters k and n, where k is the minimum number of shares required to reconstruct the secret image and n is the number of shares to generate. The particularity of secret image sharing lies in the fact that the shares themselves are images; as Figure 8.9 shows, the output of the sharing step consists of four shares (s₁, s₂, s₃ and s₄) to be distributed to each of the users. The secret image I can then be reconstructed if at least three of these shares are present.

Essentially, the secret image I is split into several blocks that are then shared and reassembled to create output images s_i, with This block-based treatment is used to eliminate the spatial correlation between pixels. The reconstruction process takes these image shares as input, reconstructing the original image or its visual content.

Figure 8.10 shows the reconstruction of the secret image from Figure 8.9. The contents of the secret image can be constructed using any three of the four shares generated by the sharing process. As the authors of Visual Cryptography and Secret Image Sharing (Cimato and Yang 2011) indicate, there are two categories of visual sharing methods: visual cryptography, as proposed by Naor and Shamir (1994), and secret image sharing, proposed by Thien and Lin (2002).

8.3.2. Visual cryptography

The visual security approach proposed by Naor and Shamir (1994) consists of obtaining secret visual content by superimposing two shares. In this method, originally intended for binary (black and white) images, shares are constructed using random binary pixel repetitions, as shown in Figure 8.11.

Naor and Shamir’s method consists of creating two shares (Naor and Shamir 1994). The method preserves the black pixels in the secret image, while leaving the color of the blank pixels random. The secret is then reconstructed by performing the XOR operation between the two shares, and the content is uniquely recognizable by the human visual system (HVS). The low complexity of this approach makes it very helpful in cases where a short response time is required. The visual cryptography approach has been studied in considerable detail, notably in terms of varying the different thresholds k and n in order to solve the contrast problem presented by Naor and Shamir (1996). Cimato and Yang (2011) cite three different groups of visual cryptography approaches: XOR-based visual cryptography, random grid visual cryptography and probabilistic visual cryptography. XOR-based visual cryptography corresponds to the approach proposed by Naor and Shamir (1994, 1996). However, XOR-based visual cryptography approaches tend to have a significant drawback in terms of the increase in share size. In order to increase the minimum number of shares required or to generate, each pixel in the secret image will be represented by a block of pixels in each share of size m. Thus, the larger the number of shares to generate or the higher the reconstruction threshold, the larger the size of the shares. Random grids and probabilistic visual cryptography approaches aim to address the shares expansion problem. Kafri and Keren (1987) defined random grids in the form of pixel matrices. Each pixel is either transparent or opaque, and the choice between the two is determined randomly. This has the effect of eliminating the spatial correlation between the pixels. When two or more grids are superimposed, the secret areas appear according to the difference in light transmission of the secret image; thus, the visual secret is recognizable by the HVS. Recently, (Shyu 2013) proposed a generalization of random grid cryptosystem methods for visual secret sharing. Probabilistic visual cryptography addresses the share expansion problems present in the previous methods and provides security for the secret image (Yang et al. 2004; Cimato et al. 2006). Weir and Yan (2010) developed a comprehensive state of the art of the different visual cryptography techniques in 2010.

8.3.3. Secret image sharing (polynomial-based)

In the state of the art, a distinction can be made between visual cryptography methods, where the decoding step is almost instantaneous, and those where reconstruction is more complex. These methods are more costly in terms of time and resources, but provide a better quality reconstruction of the secret image. Furthermore, they are more regularly suitable for use with grayscale or color images than binary images. Thien and Lin (2002) proposed a direct application of Shamir’s method to blocks of pixels in a secret image. The method is defined on grayscale (or RGB) images where the pixel value of each color channel varies between 0 and 255. First, in order for the Shamir method to work, a finite field defined by the prime q is used, such that:

[8.17]

The secret image is then processed so that all of the pixel values fall into the interval between 0 and 250. The value of 251 is assigned to q, as this is the largest prime integer that can be represented by a single byte. Next, instead of using only the a₀ term of equation [8.2], all of the coefficients are used as coefficients of the polynomial to store pixel intensity values. Thus, more or less pixels are used by the polynomial depending on the value of k. The image is then divided into blocks of k pixels that provide the values of the coefficients of the polynomial. The values generated by the polynomials are distributed within each share as pixel values. Share size is therefore divided by with respect to the secret image. This size reduction reduces the storage requirement and enables faster transmission over networks.

8.3.4. Properties

Visual secret sharing methods possess a number of interesting properties, in terms of reconstruction quality (Thien and Lin 2002; Yang et al. 2007), reduction or expansion of share size (Thien and Lin 2002; Wang and Su 2006), the storage of multiple secret images (Tsai et al. 2002; Yan et al. 2015), hidden data insertion (Yang et al. 2007) or progressive secret reconstruction (Wang and Shyu 2007).

8.3.4.1. Lossless reconstruction

The cryptographic methods used in these approaches mean that finite bodies are sometimes required to ensure security. Most methods use a finite body (see equation [8.17]) for grayscale or RGB images. However, the possible values of the pixels in the secret image range between 0 and 255, meaning that information may be lost; the secret image is pre-processed so that the pixel values are between 0 and 250. Most methods involve lossy reconstruction of the secret image (Thien and Lin 2002, 2003; Lin and Tsai 2004; Lin et al. 2009; Tsai and Chen 2013). In response to this issue, Yang et al. (2007) proposed the use of Galois bodies to avoid truncating pixel values. Galois bodies redefine arithmetic operations so that calculations remain within the body. This notably means, in our context, that non-prime numbers can be used to define them, as long as the selected numbers can be decomposed into primes. Thus, a Galois body can be used for pixel values such that

[8.18]

This Galois body is widely used in cryptography and for error codes, as it allows bytes to be manipulated easily.

8.3.4.2. Reduction or expansion of share size

Thien and Lin (2002) were the first to propose reducing the size of shares by taking advantage of the form of the chosen polynomials. Using the remaining coefficients of the selected polynomial to generate the pixel value of the shares, pixels are then processed by blocks of k pixels in the secret image. Each block of pixels in the secret image corresponds to a pixel in the shares. The authors were thus able to reduce share size to only of the size of the secret image. More recently, Chen et al. (2016) presented findings on share size reduction for other general access structures.

8.3.4.3. Data hiding

Since the images shared with users look like white noise, it is easy for a controller to detect suspicious images in a network in the context of covert communication and block their transmission (Kahn 1996). In order to transfer shares over networks in a less suspicious manner, Thien and Lin (2003) took advantage of their share size reduction strategy to hide their shares in host images. These images are known as meaningful shadows, where the shadows are images, distributed to users, that look like any other image. Many other authors have worked on developing discreet share insertion methods (Lin and Tsai 2004; Yang et al. 2004, 2007). The secret image is processed so that all pixel values are between 0 and 250.

8.4. 3D object sharing

The upsurge in applications using 3D data, such as 3D scanning, creation and printing, over the last decade means that 3D objects have become important financial assets for their owners. The intellectual property of creators must be preserved, and the massive use of distributed storage solutions has accentuated the need to protect this content. The principle of secret 3D object sharing is described in section 8.4.1. In section 8.4.2, we present methods for secret 3D object sharing based on binary shares, while in section 8.4.3, we describe secret 3D object sharing methods in which the shares take the form of 3D objects.

8.4.2. Methods without format preservation

The first 3D object sharing methods focus on applying secret sharing methods directly to 3D data, for both geometry and connectivity information (Elsheh and Hamza 2010, 2011; Anbarasi and Mala 2015).

8.4.2.1. Elsheh and Hamza’s first method

Elsheh and Hamza (2010) proposed a first approach to protecting the position of vertices and their connectivity based on Blakley’s method (Blakley 1979). The authors proposed a partition with a threshold k equal to 3. The coordinates are directly interpreted as elements of a finite field determined by a prime number q large enough to represent the coordinates. For each vertex, two coefficients a_i and b_i are then randomly generated, where is the number of shares to generate. The coefficient c_i is determined using the equation:

[8.19]

such that x, y, z are the coordinates of the vertex being shared.

The same process can be carried out for connectivity, with each triangular facet of the 3D mesh being represented by a triplet of vertex indices (v_u, v_w, v_t) such that where V is the number of vertices.

8.4.2.2. Elsheh and Hamza’s second method

Elsheh and Hamza then proposed a second approach based on Shamir’s method (Shamir 1979), using the same approach that Thien and Lin (2002) applied to 3D images: the method produces shares which are smaller than the secret image (Elsheh and Hamza 2011). As in their first method (Elsheh and Hamza 2010), the authors proposed applying the secret sharing method, with k = 3, to the data directly, modifying the finite body using a prime number greater than the number of vertices. The drawback to this method is that the number of vertices in the 3D object is increased to ensure that the vertex indices are valid. Furthermore, as in Thien and Lin’s approach (Thien and Lin 2002), the method does not select a block of k pixels, but rather k coordinates or indices. The size of the shares is thus reduced to that of the secret 3D object. Finally, Elsheh and Hamza showed that an additional compression step could be applied to the generated shares, using the entropic compression method introduced by Huffman (1952) or that included in the ZLIB program (Deutsch and Gailly 1996).

8.4.3. Methods with format preservation

Tsai (2016) and Lee et al. (2017) recently proposed the use of hidden data to replicate the approach proposed by Thien and Lin (2003) by hiding the shares in host images. Contrary to previous methods, the minimum threshold for reconstructing a secret 3D object k is no longer fixed at 3. In order to insert shares into host 3D objects via data hiding techniques, the data to insert must be compressed, and the host objects must be dense enough to offer sufficient capacity. Resampling and surface subdivision methods are used to increase the natural share storage capacity of the host 3D object.

8.4.3.1. Tsai’s method

In Tsai’s method, only the geometry of the secret 3D object is retained; the object is pre-compressed using space division and quantization methods (Tsai 2016). The compressed data are then shared using Shamir’s method (Shamir 1979) and inserted into 3D objects using a data hiding technique, which is sufficiently robust to modifications.

8.4.3.2. Lee et al.’s method

The method developed by Lee et al. (2017) does not aim to ensure the security of 3D objects, but to enable more cost-effective transmission in order to display a set of n 3D objects in a 3D streaming context. Their method consists of sharing several 3D objects of low quality, with the aim of displaying the n 3D objects as soon as k shares are downloaded in high quality. Thus, the shares are inserted into the high-quality 3D objects, specifically in the Reed-Solomon (Reed and Solomon 1960) codes, making it possible to reconstruct the whole set of n 3D objects in low quality. The original 3D objects are decimated to a certain level and then compressed using ZLIB (Deutsch and Gailly 1996). The compressed data is then processed and transformed into Reed-Solomon codes (Reed and Solomon 1960), which can be assimilated to shares according to Shamir’s method (Shamir 1979).

8.4.3.3. Beugnon et al.’s method

In 2019, Beugnon et al. (2019b) proposed the first selective sharing approach for secret 3D objects which preserves the 3D format. Drawing on their earlier work on selective 3D encryption (Beugnon et al. 2018), the authors developed a method that selects a portion of the bits of the floating point representation used to represent the coordinates of vertices according to a degradation level. The latter deduces a sequence of bits to be selected and shared in order to build new 3D objects, called shared 3D objects, which are distributed to each user. These shared 3D objects may be assimilated to low-quality versions of the secret 3D object. This approach preserves the size of the original 3D object within the shared 3D objects, enabling independent reconstruction of the vertices. The authors used both Blakley and Shamir’s secret sharing methods (Blakley (1979) and Shamir (1979)), described in their article (Beugnon et al. 2019a), in presenting their secret sharing approach. The bits representing the coordinates within the shared 3D objects, which form the output for the method, contain the result of sharing by replacing selected bits with bits extracted from shares generated using sharing methods. The bits selected by the degradation level have an effect on the visual security level of the shared 3D objects, which may be totally confidential or recognizable, but protected against illegal use. Once k shared 3D objects are combined, a high quality, lossless version of the original 3D object can be reconstructed.

Figure 8.12 shows an application of Beugnon et al.’s approach (Beugnon et al. 2019b) using Shamir’s method (Shamir 1979) to a 3D object noted , representing a shoe (mesh provided by the Stratégies company¹), with parameters (k, n) = (3, 4) (see Figure 8.12(a)). The 3D objects shown in Figure 8.12(b-e) are the four shared images generated by the sharing process. These 3D objects have the same number of vertices as the original 3D object; their geometry is degraded, but they remain usable within a 3D environment. Figures 8.12(f) and (g) show that identical versions of the original, secret 3D object can be reconstructed from any group of three or more shared 3D objects. Figure 8.12(h) shows a reconstruction created using only two shared 3D objects, rather than three; in this case, the reconstruction is no less degraded than the shared 3D objects.

8.5. Applications for social media

Social networks are immensely popular, with over two billion active users worldwide. The rapid development of these networks has raised many questions regarding image protection. Notably, multi-party privacy conflicts can arise when a photo is published by its owner. This is because the privacy settings applied to an image are those specified by the owner, and the people in the picture are not involved in the process. For example, say a person, Alice, takes a photo with her group of friends and posts it on her personal page. Her entire network has access to this photo, according to the privacy settings that Alice has defined. Her friends who are present in the photo are not involved in the publication process: they are not consulted and their agreement is not required in order to publish the photo, despite the fact that it contains their personal information. This is a major problem, and effective solutions are needed to manage these multi-party privacy conflicts. In this section, we aim to address this problem by describing a hybrid photo sharing method for social networks (Beugnon et al. 2019c).

Consider an image showing a group of n users. First, the regions of interest (ROI) R_j, with corresponding to each participant are identified using a face detection algorithm. The coordinates of these regions are then used to determine the parts of the image to protect using secret image sharing techniques. Note that the rest of the image, considered as the background, remains in the clear (public content).

Belenkiy’s hierarchical secret sharing method, applied to images, is used to protect the n RIs. This approach, based on Tassa’s hierarchy (Tassa 2007), is disjunctive and multilevel, as described in section 8.2.2.4. To avoid data loss, secret sharing is carried out in the Galois field GF (2⁸), as proposed by Yang et al. (2015). An identifier x_j, with is assigned to the j-th participant, and the value x₀ is assigned to the public server:

[8.20]

The n participants define a confidence level within their group, selecting a threshold k such that indicating the minimum number of users needed to reconstruct all of the RIs, that is, the entire image in the clear domain. Figure 8.13 gives an overview of the encoding phase.

Each RI R_j is shared using n + 1 protected RIs Each share is the same size as the original image; S₀ is the public share, consisting of all of the shared pixels (level 2) in the along with the pixels in the original image which lie outside of the RI. The other shares contain the shared pixels (level 2) in the corresponding to the user ID x_j, the shared pixels (level k + 1) in the other and the background pixels from the original image.

Shares are obtained by treating each RGB component of each RI R_j, with in isolation. For each component, the pixels coded on 8 bits, read sequentially, are considered as secret values s to share (s ∈ GF(2⁸)). To share each secret value s, a sequence of random values a₀, a₁, · , a_k−1 is generated and a_k takes the value s. These values are then used to define a polynomial of order k:

[8.21]

The shared value corresponding to s in R_j is then calculated in the following way, as a function of the polynomial:

• – the hierarchical level for the public share S₀ is assigned a threshold of 2, so that R_j can be reconstructed if the user with ID x_j gives their consent. The shared value is equal to is the derivative of order (k − 1) of f shares; note that this shared value is also used in the reconstruction of R_j even if the user with ID x_j does not give their consent, as long as at least k users are involved in reconstruction;
• – the hierarchical level for a user with ID x_j is also assigned a threshold of 2. Users must be able to reconstruct their own RI easily, using only the public share S₀. The shared value is equal to is the derivative of order (k − 1) of f(.);
• – the hierarchical level for users with ID is assigned a threshold of k + 1. Thus, each shared value is equal to In this case, k participants must give their consent to permit a full reconstruction of the secret image, using the public share and their own shares.

There are two possible scenarios for the decoding phase, as shown in Figure 8.14. If the number of users k′ is below the confidence level determined by the group k, then the k′ shares and the pubic share S₀ are used to reconstruct k′ RIs {R_j}, corresponding to the k′ participants in the clear domain. Each secret value s of each R_j can be reconstructed using the Lagrange interpolation method. The user with ID x_j and the public server (ID x₀) have an equation with two unknown coefficients a_k−1 and a_k = s. The value of s can be obtained by solving the linear system formed by these two equations. Note that the n − k′ RIs of users not participating in the reconstruction process remain protected.

If the number of participants k′ is equal to (or greater than) the confidence level k, then the n − k′ RIs corresponding to users not involved in the reconstruction are also reconstructed. Each of the k′ ≥ k participants has an equation with k + 1 unknown coefficients a₀, . . . , a_k, where a_k = s, enabling them to reconstruct the secret value s. Furthermore, the public server has an equation with two unknown coefficients a_k−1 and a_k = s. This means that the number of equations is sufficient to solve the system, and the value of can be found. The image obtained after reconstructing the n RIs is exactly the same as the original, since enough users have accepted its publication (according to the level of confidence defined by the group).

A full example of the hierarchical secret image sharing method applied to a social network context is shown in Figure 8.15. The chosen parameters are k = 5 and n = 8. In this case, the RI detection process identified eight users (n = 8), and the original image can be reconstructed with the consent of at least five of these users (k = 5). Figure 8.15a shows the RIs identified using a face detection algorithm. Following the approach described above, a public share, S₀ share, is published on the social network, as shown in Figure 8.15b. Each user of ID x_j, with receives their own personal share S_j in which all RIs are protected. Note that by using this share alongside the public share S₀, each user is able to reconstruct their own RI R_j, as shown in Figure 8.15c. This shows the partial reconstruction obtained by combining share S₂, corresponding to the user ID x₂, with the public share S₀. The RI R₂ is thus reconstructed in the clear, while all other RIs remain protected. As long as the number of users involved in the reconstruction k′ is below the confidence level k defined by the user group, full reconstruction of the original image is impossible. In Figure 8.15d, k′ = 3 shares S₁, S₂ and S₄ (corresponding to x₁, x₂ and x₄) are combined, together with the public share S₀. In this case, only the background of the image and RIs R₁, R₂ and R₄, corresponding to the users involved, are clearly visible. The privacy of users who are not involved in this reconstruction is protected, and their faces are not visible. On the other hand, when k′ ≥ k or more shares are combined, for example when k′ = 5, as shown in Figure 8.15e, then the original image can be reconstructed in full. The k′ shares S₁, S₃, S₅, S₇ and S₈, corresponding to participant IDs x₁, x₃, x₅, x₇ and x₈, are recombined, one by one, with the public share S₀ to reveal the contents of RIs R₁, R₃, R₅, R₇ and R₈. Additionally, the n − k′ = 3 remaining RIs R₂, R₄ and R₆ are reconstructed using the k′ shares and the public share to decode the image, using the hierarchical secret image sharing process. This results in a full and perfect reconstruction of the original image.

Table 8.1 shows the average results obtained for the PSNR, Shannon entropy and SSIM statistical measures, based on the generated shares , for each protected RI . We see that the PSNR value is less than 10 dB, the SSIM is close to 0, and the entropy is very close to the maximum value of 8 bits/pixel. These results indicate that the content of the RIs is protected in each share.

COMMENT ON FIGURE 8.15.– (a) original image after detection of the RIs corresponding to the eight users (faces, in red); (b) public share S₀ published on social networks; (c) partial reconstruction of the image using share S₂ corresopnding to user ID x₂ and the public share S₀, (d) partial reconstruction of the image obtained by combining the shares of k′ = 3 users (S₁, S₂ and S₄, corresponding to x₁, x₂ and x₄) and the public share S₀; (e) perfect reconstruction of the original image, obtained by combining the shares of at least k′ = 5 users (S₁, S₃, S₅, S₇ and S₈, corresponding to x₁, x₃, x₅, x₇ and x₈) and the public share S₀.

Figure 8.16 shows the histograms of the pixels in RI R₁ in the original image I and in its protected form within share S₀. The distribution of pixels in the protected RI is almost uniform, indicating that the hierarchical secret image sharing method preserves the visual confidentiality of pixel values in each generated share.

The results presented here demonstrate the effectiveness of the hierarchical secret image sharing method in real-life situations and security contexts. This approach can also be extended to more traditional multi-party privacy cases, where all users must give their consent for partial reconstruction. In this case, the confidence level is simply set at k = n during the sharing phase.

8.6. Conclusion

In this chapter, we presented and discussed the notion of secret sharing. The concept, developed in the late 1970s by Blakley (1979) and Shamir (1979), has its origins in methods designed for secret cryptographic key management; its scope was extended to new areas of security in the 1990s. In light of developments in encryption techniques, secret sharing methods began to be adapted for multimedia data, notably 2D images, from 1994 (Naor and Shamir 1994). The authors of this paper established a definition of visual secret sharing, considering the secret to be the contents of an image. A new wave of work on protecting and sharing secret images was launched in 2002, with the adaptation of Shamir’s method (Shamir 1979) to enable image format preservation (Thien and Lin 2002). Finally, secret sharing began to be adapted for 3D objects in the 2010s (Elsheh and Hamza 2010) to meet the growing security needs resulting from the massive use of distributed storage solutions.

In the approach described in section 8.5, we showed how secret image sharing techniques can be used to manage multi-party privacy conflicts (Beugnon et al. 2019c). Using a hierarchical method for sharing secret regions of interest within an image, a photograph representing several people may be disseminated, but without the subjects’ identity being revealed without their consent. Individuals are identified using a face detection and recognition algorithm, and users define a trust threshold k, determining the minimum number of users who must provide consent in order for the image to be displayed in full on the social network. If this threshold is not crossed, then only consenting subjects will be shown. Following the detection phase, the method determines specific regions of interest for each identified person; these are then shared using Belenkiy’s method, protecting the pixels in question (Belenkiy 2008). Each user receives a share which may be used to reconstruct the region of interest corresponding to their face. Our experimental results highlight the feasibility of this method and its potential for application within a social network context as a tool for managing multi-party privacy conflicts. Note that the regions of interest correspond to a box around the area corresponding to a face. Future developments may focus on only selecting the pixels corresponding to the face of the detected person, or on improving rendering by applying selective encryption at the pixel level in the regions of interest, rather than creating a noise-type effect. Different levels of confidentiality (transparent or sufficient) may thus be applied to different regions of interest, depending on users’ needs. Another promising area of investigation is the development of secret image sharing methods that are robust to lossy compression, notably in relation to the JPEG standard (Wallace 1992): most image sharing platforms and social networks now apply JPEG compression to transmitted images.

As we saw in section 8.4, Beugnon et al. (2019b) have proposed a selective secret 3D object sharing method, in which each user receives a shared 3D object representing a low-quality version of the secret 3D object, corresponding to a chosen degradation level. This method preserves the input format by using shares which are, themselves, 3D objects, and allows the degradation level to be controlled. A secret sharing method, based on either Blakley (1979) or Shamir (1979), is applied to a sequence of selected bits within the coordinates of the vertices of the secret 3D object. The shared 3D objects generated in this way are then distributed to users. These objects are low-quality versions of the original, created as a function of the desired level of degradation. A high-quality, lossless version of the secret 3D object can be reconstructed when a subset of k out of n users combine their shares. To date, this is the only method that has been developed for selective sharing of secret 3D objects. Further work in this area may concern new functionalities, such as progressive reconstruction, whereby the quality of the reconstruction varies according to the number of contributing users. It may also be interesting to include hierarchical functionalities, establishing different access rights for the 3D objects, so that reconstruction may be carried out more quickly by users with the highest authorization level. In this case, each user would receive a shared 3D object with a particular level in the hierarchy and according to a chosen degradation level. Higher level users could thus reconstruct a better-quality version of the secret 3D object than their counterparts.