# Reversible Data Hiding for Encrypted 3D Model Based on Prediction Error Expansion

Authors: Li Li; Shengxian Wang; Ting Luo; Ching-Chun Chang; Qili Zhou; Hui Li
Journal: Journal of Sensors
 (2020)

---

## Abstract

Since 3D models can intuitively display real-world information, there are potential scenarios in many application fields, such as architectural models and medical organ models. However, a 3D model shared through the internet can be easily obtained by an unauthorized user. In order to solve the security problem of 3D model in the cloud, a reversible data hiding method for encrypted 3D model based on prediction error expansion is proposed. In this method, the original 3D model is preprocessed, and the vertex of 3D model is encrypted by using the Paillier cryptosystem. In the cloud, in order to improve accuracy of data extraction, the dyeing method is designed to classify all vertices into the embedded set and the referenced set. After that, secret data is embedded by expanding direction of prediction error with direction vector. The prediction error of the vertex in the embedded set is computed by using the referenced set, and the direction vector is obtained according to the mapping table, which is designed to map several bits to a direction vector. Secret data can be extracted by comparing the angle between the direction of prediction error and direction vector, and the original model can be restored using the referenced set. Experiment results show that compared with the existing data hiding method for encrypted 3D model, the proposed method has higher data hiding capacity, and the accuracy of data extraction have improved. Moreover, the directly decrypted model has less distortion.


---

## Body

## 1. Introduction

With the rapid advancement of multimedia processing technologies on the internet, data hiding methods have been developed for the security of three-dimensional (3D) models [1–3]. Data hiding methods achieve integrity authentication and copyright protection by embedded secret data into the content of the original carrier [4, 5]. However, for the occasions with high data security requirement, such as medical images and judicial certification, no modification is allowed on the original carrier. Therefore, reversible data hiding (RDH) has attracted more researchers for potential applications [6–8].Traditional RDH methods can be divided into three categories: difference expansion (DE), histogram shifting (HS), and lossless compression (LC). DE-based RDH methods embed secret data into carrier image by expanding the difference among adjacent pixels [9, 10]. Prediction error expansion (PEE), which belongs to difference expansion, embeds secret data by expanding the difference between the actual value and the prediction value of pixels [11–14]. HS-based RDH methods generate the feature histogram of original image and embed secret data into the smallest point of the histogram [15, 16]. LS-based RDH methods compress the specified area of the carrier image and embed secret data into the compressed area [17].With the development of outsourced storage in the cloud, reversible data hiding in encrypted domain (RDH-ED) has been studied for security of multimedia files in the cloud. The existing RDH-ED methods are mainly classified into reserving room before encryption (RRBE) and vacating room after encryption (VRAE). The RRBE method reserves embedding room before encrypting the original image. For example, Ma et al. proposed a reversible data hiding method, in which the room is reversed by self-embedding before encryption. Zhang [19] constructed the histogram of prediction error and reserved room by HS, which is the most popular method for reversible data hiding. Cao et al. improved the method of [18, 19] by generating prediction error with a small entropy so that the reserved room can be increased, and the data hiding capacity can be improved [20].The VRAE method directly implements data embedding by modifying the encrypted image [21, 22]. For example, Zhang embedded secret data by flipping the three least significant bits of a pixel [19]. With the help of the spatial correlation of natural images, the receiver extracted the secret data through the evaluation function of texture complexity. Based on the method of [19], Hong et al. increased data hiding capacity by improving the evaluation function [23]. Zhang [19] emptied out space for data embedding by using the typical manner of cipher-text compression.However, the above RDH methods are for images and cannot be directly used to 3D models because the data structure of the 3D model is different from that of the image. Therefore, Wu and Cheung proposed a RDH method for 3D models based on DE, which embeds secret data by modifying the difference among adjacent vertices [24]. Jhou et al. constructed the histogram of the distance between all vertices and the center of 3D model and embedded secret data by histogram shifting. However, these methods cannot be implemented in the encrypted domain [25]. Jiang et al. proposed a RDH-ED method for 3D models based on stream cipher encryption [26]. By flipping several least significant bits of vertex coordinates, one bit was embedded. The receiver extracted secret data by using the spatial correlation of the original 3D model. Shah and Zhang proposed a watermarking method based on the Paillier cryptosystem, which used VRAE framework to vacate space before encryption [27]. Wang et al. embedded secret data in the encrypted domain by constructing direction histogram and histogram shifting [28].Combining homomorphic encryption and prediction error expansion, a RDH method for encrypted 3D model is proposed in this paper. In this method, the original 3D model is preprocessed, and the vertex of 3D model is encrypted by using Paillier cryptosystem. In the cloud, in order to improve the accuracy of data extraction, the dyeing method is designed to classify all vertices into the embedded set and the referenced set. After that, the secret data is embedded by expanding direction of prediction error with direction vector. The prediction error of the vertex is computed by using the referenced set, and the direction vector is obtained according to the mapping table. Moreover, the mapping table is constructed to map several bits to a direction vector. Secret data can be extracted by comparing the angle between the direction of prediction error and direction vector, and the original model can be restored using the referenced set. The contributions of the paper are organized as follows.(1)
By designing the dyeing method to classify all vertices into the embedded set and the referenced set, the error rate of data extraction can be reduced(2)
The mapping table is constructed to map several bits to a direction vector, so that several bits can be embedded into a vertex, which improves data hiding capacity(3)
Compared the existing RDH-ED methods, the proposed method has higher capacity, lower bit error rate, and the directly decrypted 3D model has less distortionThe rest of this paper is organized as follows. The Paillier cryptosystem is briefly introduced in Section2. The related reversible data hiding method is proposed in Section 3. The experimental results are shown in Section 4. The conclusions are discussed in Section 5.


## 2. Related Algorithm

The Paillier cryptosystem [29], which has been widely used in encrypted signal processing, has homomorphism and probability. Homomorphism means that the product of two ciphertexts is consistent with the sum of two corresponding plaintexts. Probability means that different ciphertexts, which are obtained by encrypting the same plaintext with different parameters, can be decrypted to the same plaintext. The following describes the process of key generation, encryption, decryption, two characteristics, and subtraction homomorphism expansion.


### 2.1. Key Generation

Randomly pick up two large prime numbersp and q. Calculate N=pq and λ=lcmp−1,q−1, where lcm⋅ stands for the lowest common multiple. Afterwards, select g∈ZN2∗ randomly, which satisfies
(1)gcdLgλmodN2,N=1,where Lu=u−1/N, and gcd⋅ means the greatest common divisor of two inputs. ZN2=0,1,2,⋯,N2−1 and ZN2∗ are the numbers in ZN2 which prime with N2. Finally, we get the public key N,g and corresponding private key λ.


### 2.2. Encryption

Select a parameterr∈ZN2∗ randomly. The plaintext m∈ZN can be encrypted to the corresponding ciphertext c by
(2)c=Em,r=gm⋅rNmodN2,where E⋅ denotes the encryption function.


### 2.3. Decryption

The original plaintextm can be obtained by
(3)m=Dc=LcλmodN2LgλmodN2modN.Moreover, two important characteristics are described as follows (which has been applied in the proposed method).


### 2.4. Lemma One

For two plaintextsm1,m2∈ZN, compute corresponding ciphertexts c1,c2 with r1,r2 according to Equation (1), respectively. The equation c1=c2 holds if and only if m1=m2 and r1=r2.


### 2.5. Homomorphic Multiplication

For∀r1,r2∈ZN∗, two plaintexts m1,m2∈ZN and corresponding ciphertexts Em1,r1,Em2,r2∈ZN2∗ satisfy
(4)c1⋅c2=Em1,r1⋅Em2,r2=gm1+m2⋅r1⋅r2NmodN2,Dc1⋅c2=DEm1,r1⋅Em2,r2modN2=m1+m2modN.The original Paillier encryption system only has addition homomorphism and multiplication homomorphism. The subtraction homomorphism of the Paillier encryption system can be realized as follows.


### 2.6. Subtraction Homomorphic Expansion

In order to calculate the subtractionm1−m2 of two numbers m1,m2 in the encrypted domain, the negative number −m2 should be expressed by a positive number N−m2. Suppose that Em2−1 denotes the ciphertext of N−m2, the ciphertext Em2−1 can be calculated by Euclidean algorithm [30] and Modular Multiplication Inverse. Hence, the corresponding result of m1−m2 in the encrypted domain can be obtained with Em1⋅Em2−1modN2.


## 2.1. Key Generation

Randomly pick up two large prime numbersp and q. Calculate N=pq and λ=lcmp−1,q−1, where lcm⋅ stands for the lowest common multiple. Afterwards, select g∈ZN2∗ randomly, which satisfies
(1)gcdLgλmodN2,N=1,where Lu=u−1/N, and gcd⋅ means the greatest common divisor of two inputs. ZN2=0,1,2,⋯,N2−1 and ZN2∗ are the numbers in ZN2 which prime with N2. Finally, we get the public key N,g and corresponding private key λ.


## 2.2. Encryption

Select a parameterr∈ZN2∗ randomly. The plaintext m∈ZN can be encrypted to the corresponding ciphertext c by
(2)c=Em,r=gm⋅rNmodN2,where E⋅ denotes the encryption function.


## 2.3. Decryption

The original plaintextm can be obtained by
(3)m=Dc=LcλmodN2LgλmodN2modN.Moreover, two important characteristics are described as follows (which has been applied in the proposed method).


## 2.4. Lemma One

For two plaintextsm1,m2∈ZN, compute corresponding ciphertexts c1,c2 with r1,r2 according to Equation (1), respectively. The equation c1=c2 holds if and only if m1=m2 and r1=r2.


## 2.5. Homomorphic Multiplication

For∀r1,r2∈ZN∗, two plaintexts m1,m2∈ZN and corresponding ciphertexts Em1,r1,Em2,r2∈ZN2∗ satisfy
(4)c1⋅c2=Em1,r1⋅Em2,r2=gm1+m2⋅r1⋅r2NmodN2,Dc1⋅c2=DEm1,r1⋅Em2,r2modN2=m1+m2modN.The original Paillier encryption system only has addition homomorphism and multiplication homomorphism. The subtraction homomorphism of the Paillier encryption system can be realized as follows.


## 2.6. Subtraction Homomorphic Expansion

In order to calculate the subtractionm1−m2 of two numbers m1,m2 in the encrypted domain, the negative number −m2 should be expressed by a positive number N−m2. Suppose that Em2−1 denotes the ciphertext of N−m2, the ciphertext Em2−1 can be calculated by Euclidean algorithm [30] and Modular Multiplication Inverse. Hence, the corresponding result of m1−m2 in the encrypted domain can be obtained with Em1⋅Em2−1modN2.


## 3. The Proposed Reversible Data Hiding Method

In order to protect 3D model in the cloud, a reversible data hiding (RDH) method for encrypted 3D model is proposed. Figure1 shows the flowchart of the proposed method. An original 3D model is preprocessed, and the vertex of 3D model is encrypted by using the Paillier cryptosystem. In the cloud, all vertices are classified into the embedded set and the referenced set. Then, the secret data is embedded by expanding direction of prediction error with direction vector. The prediction error of the vertex is computed by using the referenced set, and the direction vector is obtained according to the mapping table. Receiver can extract secret data by comparing the angle between prediction error and the direction vector, and the original model can be restored using the referenced set.Figure 1
Flowchart of the proposed RDH-ED method.


### 3.1. Preprocessing

Because the input of the Paillier cryptosystem should be a positive integer, the vertex coordinates firstly are converted from decimal to positive integer.3D models are consisted of vertex data and connectivity data. The vertex data includes the coordinates of each vertex in the spatial domain. The connectivity data reflects the connection relationship between vertices. A 3D model Fairy and its local region are illustrated in Figure2, and the corresponding format file is shown in Table 1. Each vertex and each face of the 3D model have a corresponding index, respectively. For a 3D model M, let vii=0NV represent the sequence of vertices, where vi=vi,x,vi,y,vi,z, and NV is the number of vertices. Note that each coordinate ∣vi,j∣<1,j∈x,y,z, and the significant digit of each coordinate is 6.Figure 2
Illustration of a 3D model Fairy and its local region.Table 1
File format of Figure2.
Vertex listFace informationIndex of vertexX-axisY-axisZ-axisIndex of faceElements in each face1v1,xv1,yv1,z1(2,3,1)2v2,xv2,yv2,z2(5,1,4)3v3,xv3,yv3,z3(3,6,7)4v4,xv4,yv4,x4(5,2,1)5v5,xv5,yv5,z5(3,10,7)Normally, uncompressed vertices are 32-bit floating point numbers with a precision of 6 digits. Therefore, the vertex coordinates are converted into an integer withk significant digits by using.
(5)vi,j′=vi,j⋅10k,j∈x,y,z.Moreover, all vertex coordinates should be converted to positive integers for encryption by using.(6)vi,j′=vi,j′+10k,j∈x,y,z.Ifk is greater than 6, the model can be restored losslessly; however, the time cost of encryption and decryption is large. If k is less than 6, the time cost is small, while the model cannot be restored losslessly. In order to balance the time cost and distortion of 3D model, the best k will be selected through the experiment.


### 3.2. Encryption

Referring to Equation (2), an integer r can be randomly selected to encrypt the vertex coordinates vi′=vi,x′,vi,y′,vi,z′ with the public key N,g.
(7)ci,j=Evi,j′,ri,j=gvi,j′ri,jNmodN2,j∈x,y,z,where ci,j is the ciphertext from the plaintext vi,j′.


### 3.3. Data Embedding

Firstly, the dyeing method is designed to classify all vertices into the embedded set and the referenced set. Secondly, the prediction error of the vertex in the embedded set is computed using the referenced set. Thirdly, a one-to-one mapping is constructed to map several bits to a direction vector. Finally, for embedding secret data, the direction vector and the embedded key are used to expand the direction of the prediction error. In addition, the embedded key is calculated to reduce the accuracy of data extraction.


#### 3.3.1. Classifying the Vertices

For the vertex of 3D model, 1-ring neighborhood of the vertex refers to these vertices that are directly adjacent to the vertex. As shown in Figure3, the vertex vj′ is adjacent of the vertex vi′. If a vertex is modified to embed secret data, its 1-ring neighborhood cannot be modified, and it is mainly because the 1-ring neighborhood is required to calculate the prediction value of the vertex. Therefore, the dyeing algorithm is designed to classify all vertices into the embedded set and the referenced set because the color of adjacent vertices cannot be same. The vertices in the referenced set can be used to calculate the prediction value of the vertices in the embedded set because the referenced set consists of 1-ring neighborhood of all vertices in the embedded set, while the vertices in embedded set are modified to embed secret data.Figure 3
The actual value and the prediction value of the vertex.Suppose thatSe denotes the embedded set, and Sr denotes the referenced set. In order to obtain large data hiding capacity, the number of the vertices in the embedded set should be increased. The embedded set is the nonadjacent vertex set. According to graph theory, the existing polynomial algorithms can find the largest nonadjacent vertex set if the graph is a bipartite graph. However, the connectivity data of a 3D model cannot be represented by a bipartite graph since all loops of 3D model are 3. Hence, finding the largest embedded set in a 3D model is NP-hard problem. In order to increase data hiding capacity, the dyeing algorithm is designed to increase the number of the vertices in the embedded set.Referring to the four-color theorem, different colors are required for any two adjacent vertices. For 3D models, at least seven colors are needed to dye the vertices to ensure that the colors of the adjacent vertices are different. After completing the process of dyeing, the color with most vertices is selected, and all vertices of this color are regarded as the embedded set, and the remaining vertices are regarded as the referenced set. Suppose thatC denotes the color set of dyeing all vertices, Zi denotes the color set of 1-ring neighborhood of the vertex, and ci denotes the color of the ith vertex. The steps for the vertex classification using the dyeing algorithm are listed as follows.Step 1.
Suppose that the color of all vertices is black, and traverse all vertices in order of the vertex index.Step 2.
For an unclassified vertexvi, statistic the color set of its 1-ring neighborhood.Step 3.
Dye the vertexvi using the first color in C but not in Zi.Step 4.
Determine whether the next vertexvi+1 is black. If vi+1 is black, the classification ends. If vi+1 is not black, loop from Step 2 until no vertex is black.Step 5.
Select the most frequently used color, add all vertices of this color to the embedded set, and the remaining vertices are added to the referenced set.Since all vertices are traversed only once, the time complexity of the dyeing algorithm isOn. For example, as illustrated in Figure 4, let C=red,green,yellow,blue. Traverse the vertex v1, and let c1=red since Z1=black. Traverse the vertex v2, and let c2=green since Z1=black,red. Traverse the vertex v2, and let c2=yellow since Z1=black,red,green. After traversing all vertices, the most frequently used color green is selected. The vertex set {2,6,7,11} of color green is regarded as the embedded set, while the remaining vertices as the referenced set.Figure 4
The process of classifying the vertices using the dyeing method.


#### 3.3.2. Computing of Prediction Error

The accuracy of prediction error directly affects the performance of data hiding. As shown in Figure3, the vertex vj′ is adjacent to the vertex vi′, and the vertex v¯i is the prediction value of vertex vi′. According to the correlation of adjacent vertices, prediction value v¯i can be calculated by using
(8)v¯i=1Ni∑j=1Nivj′,j∈1,Ni,where Ni denotes the number of the adjacent vertices of the vertex vi′.The prediction error of the vertexvi′ can be calculated by using
(9)Δvi=vi′−v¯i,where Δvi denotes the prediction error of the vertex vi′. Δvi is a three-dimensional vector with random direction. Due to the spatial correlation, the modulus length Δvi is usually small, and experiment results show that the modulus length Δvi has the maximum D. Hence, the range of Δvi is as follows.
(10)Δvi∈0,D.


#### 3.3.3. Constructing the Mapping Table

In order to embed several bits into a vertex in the embedded set, several bits should be mapped to a direction vector.Data embedder converts secret data into several groups withn bits, and n is a shared parameter. Let a group with n bits denote as ww0,w1,⋯,wn−1. Suppose that sw denotes weighted sum of w, and sw is calculated as
(11)sw=∑i=0n−1wi⋅2i,sw∈0,2n−1.In order to embedsw into a vertex, the corresponding direction vector of swshould be constructed. Suppose that b→sw denotes the direction vector of sw, and sw is embedded by expanding the direction of prediction error with direction vector b→sw. The one-to-one mapping between weighted sum and direction vector is constructed as shown in Table 2. Let bk,j∈−1,1,k∈0,7, and if n≤3, eight direction vectors can be constructed. The mapping between direction vector and weighted sum is shown at the top three rows in Table 2. Let bk,j∈−1,0,1,k∈0,26, and if n=4, twenty-six direction vectors are constructed as shown at the fifth row in Table 2. Let bk,j∈−2,−1,0,1,2,k∈0,110, and if n=5 or n=6, 110 direction vectors are constructed. Let Wbk denote the direction weight of direction vector. As shown in Table 2, the direction vector b→k is sorted according to the value Wbk, and the direction weight Wbk of the direction vector is calculated as follows.
(12)Wbk=9bk,1+3bk,2+bk,3.Table 2
The one-to-one mapping table between weighted sum and direction vector.
Embed one bit into a vertex, which meansn=1, and sw∈0,1. On this condition, let bk,j∈−1,1.sw∈0,10(-1,-1,-1)1(-1,-1,1)Embed two bits into a vertex, which meansn=2, and sw∈0,3. On this condition, let bk,j∈−1,1.sw∈0,30(-1,-1,-1)1(-1,-1,1)2(-1,1,-1)3(-1,1,1)Embed three bits into a vertex, which meansn=3, and sw∈0,7. On this condition, let bk,j∈−1,1.sw∈0,70(-1,-1,-1)1(-1,-1,1)2(-1,1,-1)3(-1,1,1)4(1,-1,-1)5(1,-1,1)6(1,1,-1)7(1,1,1)Embed four bits into a vertex, which meansn=3, and sw∈0,15. On this condition, letbk,j∈−1,0,1.sw∈0,150(-1,-1,-1)1(-1,-1,0)2(-1,-1,1)3(-1,0,-1)4(-1,0,0)5(-1,0,1)6(-1,1,-1)7(-1,1,0)8(-1,1,1)9(0,-1,-1)10(0,-1,0)11(0,-1,1)12(0,0,-1)13(0,0,1)14(0,1,-1)15(0,1,0)Hence, if the shared parametern is obtained, the mapping table between weighted sum and direction vector can be constructed. For different sw, the corresponding direction vector b→sw can be found through the mapping table.For example, ifn=2, four direction vectors b→sw should be constructed to represent four weighted sum sw, respectively. Let bk,j∈−1,1, eight direction vectors can be constructed, and the first four direction vectors are selected according to the direction weight Wbk. As a result, the four direction vectors (-1,-1,-1), (-1,-1,1), (-1,1,-1), and (-1,1,1) are constructed to represent sw∈0,3, respectively.


#### 3.3.4. Data Embedding

In order to embed secret data into the vertex, the vertex coordinates are required to be modified by using the direction vector and the embedding key. The weighted sumsw of ww0,w1,⋯,wn−1 is embedded in the vertex vi′ by using Equation (13).
(13)vi″=vi′+φb→sw,where vi″ is the modified vertex coordinate of vi′, parameter φ is the embedding key, and b→sw=bsw,x,bsw,y,bsw,z is the corresponding direction vector of sw.Referring to Equation (13), data embedding in the encrypted domain is performed as
(14)ci,j′=ci,j⋅csw=Evi,j,ri,j⋅E−φ⋅bsw,j,rsw−1modN2,ifφ⋅bsw,j<0,j∈1,2,3,ci,j′=ci,j⋅csw=Evi,j,ri,j⋅Eφ⋅bsw,j,rswmodN2,ifφ⋅bsw,j>0,j∈1,2,3,ci,j′=ci,j,ifφ⋅bsw,j=0,j∈1,2,3,where ci,j′ is the ciphertext of vi,j″, and csw is the ciphertext of φ⋅bsw,j. Moreover, if φ⋅bsw,j>0, addition homomorphism of Paillier cryptosystem is utilized to embed secret data. If φ⋅bsw,j<0, subtraction homomorphism expansion of Paillier cryptosystem is utilized to embed secret data.After data embedding, the corresponding change of the prediction error in the plaintext is as follows.(15)Δvi′=Δvi+φ⋅b→sw.AfterΔvi being changed, the angle between the direction of prediction error and direction vector will be small.In order to improve accuracy of data extraction, two inferences about vector are provided to calculate the embedded key.Inference 1.
Suppose thatm→1 and m→2 are two three-dimensional vectors. If the directions of m→1 and m→2 are the same, the modulus length m→1+m→2 has the maximum. If the directions of m→1 and m→2 are the opposite, the modulus length m→1+m→2 has the minimum. The proof is listed as follows.
(16)m→1+m→22=m→12+m→22+2m→1⋅m→1⋅cosθm→1,m→2,where θm→1,m→2 is the angle between m→1 and m→2. According to Equation (16), since m→1+m→2 is related to the angle, the above inference holds.Inference 2.
For two unit vectorsn→1 and n→2, let θn→1,n→2 denote the angle between two vectors, and let θn→1,n→1−n→2 denote the angle between n→1 and n→1−n→2. θn→1,n→1−n→2 and θn→1,n→2 are positively related. The smaller θn→1,n→2, the smaller θn→1,n→1−n→2. In addition, θn→1,n→1−n→2∈0,π/2. The proof is listed as follows.
(17)cosθn→1,n→1−n→2=n→1×n→1−n→2n→1⋅n→1−n→2=n→12−n→1⋅n→2cosθn→1,n→2n→1⋅n→1−n→2,where × denotes cross product. Since n→1 and n→2 are unit vector, Equation (18) can be obtained according to Equation (17).
(18)cosθn→1,n→1−n→2=1−cosθn→1,n→2/2.
According to Equation (18), cosθn→1,n→1−n→2>0, and θn→1,n→1−n→2∈0,π/2. The above inference holds.


#### 3.3.5. Embedding Key Calculation

The embedding key influences the accuracy of data extraction. If the embedding key satisfies a certain condition, secret data can be extracted correctly.Figure5 shows the angle between prediction error and three direction vectors. Suppose that θsw denotes the angle between prediction error Δvi and direction vector b→sw corresponding to the secret data sw, and θk denotes the angle between prediction error Δvi and other direction vector b→kk∈0,2n−1,k≠sw. θsw is computed as
(19)cosθsw=Δvi′×b→swΔvi′b→sw.Figure 5
The angle between the prediction error and three direction vectors.Since the secret data is extracted by using the smallest angle between the prediction error and the direction vector, in order to improve the accuracy of data extraction,θsw should be smaller than θkk∈0,2n−1,k≠sw. After data embedding, Equation (20) should be satisfied.
(20)∀k∈0,2n−1,k≠sw,cosθsw>cosθk.The following equation can be derived by using Cosine Theorem.(21)∀k∈0,2n−1,k≠sw,Δvi′×b→swΔvi′b→sw>Δvi′×b→kΔvi′b→k.It can be derived to the following equation.(22)Δvi+φb→sw×b→swb→sw−b→kb→k>0.Suppose that the vectorM→=b→sw/b→sw−b→k/b→k, and Equation (22) can be simplified as
(23)Δvi+φb→sw×M→>0.According to Inference2, the angle between b→sw and M→ is smaller than π/2, so b→sw×M→>0. Equation (24) can be derived.
(24)φ>Δv×−M→b→sw×M→.Since the modulus lengthΔv∈0,D, Equation (25) can be derived according to Inference 1.
(25)Δv=D−M→⋅−M→,φ>Δv×−M→b→sw×M→max=D⋅M→b→sw×M→.It can be derived to the following equation by using Cosine Theorem.(26)φ>D⋅M→b→sw⋅M→⋅cosθb→sw,M→⇔φ>Db→sw⋅cosθb→sw,M→.Suppose thatθb→sw,M→ denotes the angle between M→ and b→sw, in order to ensure that θsw is smaller than θk, θsw should satisfy the following equation.
(27)φ=Db→sw⋅cosθb→sw,M→.Ifφ satisfies Equation (27), secret data can be extracted correctly. According to Inference 2 and Equation (27), φ has the maximum if the angle between b→sw and b→k is smallest.Since direction vector is related to the shared parametersn, the shared parameters influence the value of φ. According to Equation (27), the relationship between φ and n is obtained as follows.
(28)φ=D,ifn=1,2,3,φ=3D,ifn=4,For example, for a clear description, letn=3. In this condition, the angle between b→0=−1,−1,−1 and direction vector b→1=−1,−1,1 is the smallest. The embedding key can be calculated by the following equation.
(29)M→=b→0b→0−b→1b→1=13−1,−1,2,cosb→0,M→=13,φ=Db→0cosb→0,M→=D.In order to explain the whole processes, the data embedding example is given as follows. For convenience, suppose thatn=2, the ith vertex vi′=1410,2120,790, the prediction value v¯i=1430,2280,750, and the secrete data w′=1,0. Since n=2, the weighted sum sw∈0,3 according to Equation (11), and four direction vectors can be obtained according to the mapping table. Four direction vectors b→0=−1,−1,−1, b→1=−1,−1,1, b→2=−1,1,−1, and b→3=−1,1,1 correspond to sw=0, sw=1, sw=2, and sw=3, respectively. Since w′=1,0, then sw′=2 can be computed, and sw′=2 corresponds to b→2=−1,1,−1. In addition, φ=250 can be obtained by Equation (28). The prediction error can be computed, and Δvi=−20,−160,40 according to Equation (9). Initially, the angle between Δvi and b→0,b→1,b→2,b→3 can be computed, and θ0=60.88°, θ1=40.12°, θ2=128.7°, and θ3=110.3°. After data hiding, θ2 between Δvi and b→2 should be the smallest angle. During data hiding, vi″=vi′+φb→2 and Δvi′=Δvi+φb→2. Hence, vi″=1160,2370,540 and Δvi′=−270,90,−210. Then, θ0=50.49°, θ1=91.87°, θ2=21.58°, and θ3=75.83° can be computed. The result shows that θ2 between Δvi′ and b→2 will be smallest after data hiding, and the secret data can be extracted by finding the smallest angle.Figure6 shows the changes of angles θsw between prediction error Δvi′ of 100 vertices and direction vector b→sw corresponding to secret data sw before and after data embedding when the shared parameter is 3. The result shows that the angle will become smaller after data embedding.Figure 6
The changes of angle between prediction errorΔvi′ and direction vector b→sw before and after data embedding.In addition, a large embedding key will make 3D model disturbed obviously. Hence, the embedding key will be discussed specifically in Section4 to balance the distortion of the directly decrypted model and the accuracy of data extraction.


### 3.4. Data Extraction and Model Recovery

After receiving the encrypted model with secret data, receiver can decrypt 3D model with private keyλ and obtain the directly decrypted 3D model. The decryption of 3D model is as follows.
(30)vi,j″=Dci,j′=Lci,j′λmodN2LgλmodN2modN.The directly decrypted 3D model is similar to the original model because only the coordinates of some vertices are modified slightly during data embedding.After decrypting 3D model, all vertices are first classified into the embedded set and the referenced set using the dyeing algorithm. Secondly, prediction error of the vertex in embedded set is computed and the mapping table is constructed with the shared parametern. Then, the angles between prediction error and all direction vector are computed, and the smallest angle θsw is selected, which is the angle between Δvi′ and b→sw. At last, b→sw can be obtained, and the corresponding sw can be found by using the mapping table.sw is converted into n bit ww0,w1,⋯wn−1 by using
(31)wi=sw′2imod2,i=0,1,2,⋯,n−1.After data extraction, the embedding key and direction vector can be used to recovery the original 3D model by using(32)vi′=vi″−φ⋅b→sw.


## 3.1. Preprocessing

Because the input of the Paillier cryptosystem should be a positive integer, the vertex coordinates firstly are converted from decimal to positive integer.3D models are consisted of vertex data and connectivity data. The vertex data includes the coordinates of each vertex in the spatial domain. The connectivity data reflects the connection relationship between vertices. A 3D model Fairy and its local region are illustrated in Figure2, and the corresponding format file is shown in Table 1. Each vertex and each face of the 3D model have a corresponding index, respectively. For a 3D model M, let vii=0NV represent the sequence of vertices, where vi=vi,x,vi,y,vi,z, and NV is the number of vertices. Note that each coordinate ∣vi,j∣<1,j∈x,y,z, and the significant digit of each coordinate is 6.Figure 2
Illustration of a 3D model Fairy and its local region.Table 1
File format of Figure2.
Vertex listFace informationIndex of vertexX-axisY-axisZ-axisIndex of faceElements in each face1v1,xv1,yv1,z1(2,3,1)2v2,xv2,yv2,z2(5,1,4)3v3,xv3,yv3,z3(3,6,7)4v4,xv4,yv4,x4(5,2,1)5v5,xv5,yv5,z5(3,10,7)Normally, uncompressed vertices are 32-bit floating point numbers with a precision of 6 digits. Therefore, the vertex coordinates are converted into an integer withk significant digits by using.
(5)vi,j′=vi,j⋅10k,j∈x,y,z.Moreover, all vertex coordinates should be converted to positive integers for encryption by using.(6)vi,j′=vi,j′+10k,j∈x,y,z.Ifk is greater than 6, the model can be restored losslessly; however, the time cost of encryption and decryption is large. If k is less than 6, the time cost is small, while the model cannot be restored losslessly. In order to balance the time cost and distortion of 3D model, the best k will be selected through the experiment.


## 3.2. Encryption

Referring to Equation (2), an integer r can be randomly selected to encrypt the vertex coordinates vi′=vi,x′,vi,y′,vi,z′ with the public key N,g.
(7)ci,j=Evi,j′,ri,j=gvi,j′ri,jNmodN2,j∈x,y,z,where ci,j is the ciphertext from the plaintext vi,j′.


## 3.3. Data Embedding

Firstly, the dyeing method is designed to classify all vertices into the embedded set and the referenced set. Secondly, the prediction error of the vertex in the embedded set is computed using the referenced set. Thirdly, a one-to-one mapping is constructed to map several bits to a direction vector. Finally, for embedding secret data, the direction vector and the embedded key are used to expand the direction of the prediction error. In addition, the embedded key is calculated to reduce the accuracy of data extraction.


### 3.3.1. Classifying the Vertices

For the vertex of 3D model, 1-ring neighborhood of the vertex refers to these vertices that are directly adjacent to the vertex. As shown in Figure3, the vertex vj′ is adjacent of the vertex vi′. If a vertex is modified to embed secret data, its 1-ring neighborhood cannot be modified, and it is mainly because the 1-ring neighborhood is required to calculate the prediction value of the vertex. Therefore, the dyeing algorithm is designed to classify all vertices into the embedded set and the referenced set because the color of adjacent vertices cannot be same. The vertices in the referenced set can be used to calculate the prediction value of the vertices in the embedded set because the referenced set consists of 1-ring neighborhood of all vertices in the embedded set, while the vertices in embedded set are modified to embed secret data.Figure 3
The actual value and the prediction value of the vertex.Suppose thatSe denotes the embedded set, and Sr denotes the referenced set. In order to obtain large data hiding capacity, the number of the vertices in the embedded set should be increased. The embedded set is the nonadjacent vertex set. According to graph theory, the existing polynomial algorithms can find the largest nonadjacent vertex set if the graph is a bipartite graph. However, the connectivity data of a 3D model cannot be represented by a bipartite graph since all loops of 3D model are 3. Hence, finding the largest embedded set in a 3D model is NP-hard problem. In order to increase data hiding capacity, the dyeing algorithm is designed to increase the number of the vertices in the embedded set.Referring to the four-color theorem, different colors are required for any two adjacent vertices. For 3D models, at least seven colors are needed to dye the vertices to ensure that the colors of the adjacent vertices are different. After completing the process of dyeing, the color with most vertices is selected, and all vertices of this color are regarded as the embedded set, and the remaining vertices are regarded as the referenced set. Suppose thatC denotes the color set of dyeing all vertices, Zi denotes the color set of 1-ring neighborhood of the vertex, and ci denotes the color of the ith vertex. The steps for the vertex classification using the dyeing algorithm are listed as follows.Step 1.
Suppose that the color of all vertices is black, and traverse all vertices in order of the vertex index.Step 2.
For an unclassified vertexvi, statistic the color set of its 1-ring neighborhood.Step 3.
Dye the vertexvi using the first color in C but not in Zi.Step 4.
Determine whether the next vertexvi+1 is black. If vi+1 is black, the classification ends. If vi+1 is not black, loop from Step 2 until no vertex is black.Step 5.
Select the most frequently used color, add all vertices of this color to the embedded set, and the remaining vertices are added to the referenced set.Since all vertices are traversed only once, the time complexity of the dyeing algorithm isOn. For example, as illustrated in Figure 4, let C=red,green,yellow,blue. Traverse the vertex v1, and let c1=red since Z1=black. Traverse the vertex v2, and let c2=green since Z1=black,red. Traverse the vertex v2, and let c2=yellow since Z1=black,red,green. After traversing all vertices, the most frequently used color green is selected. The vertex set {2,6,7,11} of color green is regarded as the embedded set, while the remaining vertices as the referenced set.Figure 4
The process of classifying the vertices using the dyeing method.


### 3.3.2. Computing of Prediction Error

The accuracy of prediction error directly affects the performance of data hiding. As shown in Figure3, the vertex vj′ is adjacent to the vertex vi′, and the vertex v¯i is the prediction value of vertex vi′. According to the correlation of adjacent vertices, prediction value v¯i can be calculated by using
(8)v¯i=1Ni∑j=1Nivj′,j∈1,Ni,where Ni denotes the number of the adjacent vertices of the vertex vi′.The prediction error of the vertexvi′ can be calculated by using
(9)Δvi=vi′−v¯i,where Δvi denotes the prediction error of the vertex vi′. Δvi is a three-dimensional vector with random direction. Due to the spatial correlation, the modulus length Δvi is usually small, and experiment results show that the modulus length Δvi has the maximum D. Hence, the range of Δvi is as follows.
(10)Δvi∈0,D.


### 3.3.3. Constructing the Mapping Table

In order to embed several bits into a vertex in the embedded set, several bits should be mapped to a direction vector.Data embedder converts secret data into several groups withn bits, and n is a shared parameter. Let a group with n bits denote as ww0,w1,⋯,wn−1. Suppose that sw denotes weighted sum of w, and sw is calculated as
(11)sw=∑i=0n−1wi⋅2i,sw∈0,2n−1.In order to embedsw into a vertex, the corresponding direction vector of swshould be constructed. Suppose that b→sw denotes the direction vector of sw, and sw is embedded by expanding the direction of prediction error with direction vector b→sw. The one-to-one mapping between weighted sum and direction vector is constructed as shown in Table 2. Let bk,j∈−1,1,k∈0,7, and if n≤3, eight direction vectors can be constructed. The mapping between direction vector and weighted sum is shown at the top three rows in Table 2. Let bk,j∈−1,0,1,k∈0,26, and if n=4, twenty-six direction vectors are constructed as shown at the fifth row in Table 2. Let bk,j∈−2,−1,0,1,2,k∈0,110, and if n=5 or n=6, 110 direction vectors are constructed. Let Wbk denote the direction weight of direction vector. As shown in Table 2, the direction vector b→k is sorted according to the value Wbk, and the direction weight Wbk of the direction vector is calculated as follows.
(12)Wbk=9bk,1+3bk,2+bk,3.Table 2
The one-to-one mapping table between weighted sum and direction vector.
Embed one bit into a vertex, which meansn=1, and sw∈0,1. On this condition, let bk,j∈−1,1.sw∈0,10(-1,-1,-1)1(-1,-1,1)Embed two bits into a vertex, which meansn=2, and sw∈0,3. On this condition, let bk,j∈−1,1.sw∈0,30(-1,-1,-1)1(-1,-1,1)2(-1,1,-1)3(-1,1,1)Embed three bits into a vertex, which meansn=3, and sw∈0,7. On this condition, let bk,j∈−1,1.sw∈0,70(-1,-1,-1)1(-1,-1,1)2(-1,1,-1)3(-1,1,1)4(1,-1,-1)5(1,-1,1)6(1,1,-1)7(1,1,1)Embed four bits into a vertex, which meansn=3, and sw∈0,15. On this condition, letbk,j∈−1,0,1.sw∈0,150(-1,-1,-1)1(-1,-1,0)2(-1,-1,1)3(-1,0,-1)4(-1,0,0)5(-1,0,1)6(-1,1,-1)7(-1,1,0)8(-1,1,1)9(0,-1,-1)10(0,-1,0)11(0,-1,1)12(0,0,-1)13(0,0,1)14(0,1,-1)15(0,1,0)Hence, if the shared parametern is obtained, the mapping table between weighted sum and direction vector can be constructed. For different sw, the corresponding direction vector b→sw can be found through the mapping table.For example, ifn=2, four direction vectors b→sw should be constructed to represent four weighted sum sw, respectively. Let bk,j∈−1,1, eight direction vectors can be constructed, and the first four direction vectors are selected according to the direction weight Wbk. As a result, the four direction vectors (-1,-1,-1), (-1,-1,1), (-1,1,-1), and (-1,1,1) are constructed to represent sw∈0,3, respectively.


### 3.3.4. Data Embedding

In order to embed secret data into the vertex, the vertex coordinates are required to be modified by using the direction vector and the embedding key. The weighted sumsw of ww0,w1,⋯,wn−1 is embedded in the vertex vi′ by using Equation (13).
(13)vi″=vi′+φb→sw,where vi″ is the modified vertex coordinate of vi′, parameter φ is the embedding key, and b→sw=bsw,x,bsw,y,bsw,z is the corresponding direction vector of sw.Referring to Equation (13), data embedding in the encrypted domain is performed as
(14)ci,j′=ci,j⋅csw=Evi,j,ri,j⋅E−φ⋅bsw,j,rsw−1modN2,ifφ⋅bsw,j<0,j∈1,2,3,ci,j′=ci,j⋅csw=Evi,j,ri,j⋅Eφ⋅bsw,j,rswmodN2,ifφ⋅bsw,j>0,j∈1,2,3,ci,j′=ci,j,ifφ⋅bsw,j=0,j∈1,2,3,where ci,j′ is the ciphertext of vi,j″, and csw is the ciphertext of φ⋅bsw,j. Moreover, if φ⋅bsw,j>0, addition homomorphism of Paillier cryptosystem is utilized to embed secret data. If φ⋅bsw,j<0, subtraction homomorphism expansion of Paillier cryptosystem is utilized to embed secret data.After data embedding, the corresponding change of the prediction error in the plaintext is as follows.(15)Δvi′=Δvi+φ⋅b→sw.AfterΔvi being changed, the angle between the direction of prediction error and direction vector will be small.In order to improve accuracy of data extraction, two inferences about vector are provided to calculate the embedded key.Inference 1.
Suppose thatm→1 and m→2 are two three-dimensional vectors. If the directions of m→1 and m→2 are the same, the modulus length m→1+m→2 has the maximum. If the directions of m→1 and m→2 are the opposite, the modulus length m→1+m→2 has the minimum. The proof is listed as follows.
(16)m→1+m→22=m→12+m→22+2m→1⋅m→1⋅cosθm→1,m→2,where θm→1,m→2 is the angle between m→1 and m→2. According to Equation (16), since m→1+m→2 is related to the angle, the above inference holds.Inference 2.
For two unit vectorsn→1 and n→2, let θn→1,n→2 denote the angle between two vectors, and let θn→1,n→1−n→2 denote the angle between n→1 and n→1−n→2. θn→1,n→1−n→2 and θn→1,n→2 are positively related. The smaller θn→1,n→2, the smaller θn→1,n→1−n→2. In addition, θn→1,n→1−n→2∈0,π/2. The proof is listed as follows.
(17)cosθn→1,n→1−n→2=n→1×n→1−n→2n→1⋅n→1−n→2=n→12−n→1⋅n→2cosθn→1,n→2n→1⋅n→1−n→2,where × denotes cross product. Since n→1 and n→2 are unit vector, Equation (18) can be obtained according to Equation (17).
(18)cosθn→1,n→1−n→2=1−cosθn→1,n→2/2.
According to Equation (18), cosθn→1,n→1−n→2>0, and θn→1,n→1−n→2∈0,π/2. The above inference holds.


### 3.3.5. Embedding Key Calculation

The embedding key influences the accuracy of data extraction. If the embedding key satisfies a certain condition, secret data can be extracted correctly.Figure5 shows the angle between prediction error and three direction vectors. Suppose that θsw denotes the angle between prediction error Δvi and direction vector b→sw corresponding to the secret data sw, and θk denotes the angle between prediction error Δvi and other direction vector b→kk∈0,2n−1,k≠sw. θsw is computed as
(19)cosθsw=Δvi′×b→swΔvi′b→sw.Figure 5
The angle between the prediction error and three direction vectors.Since the secret data is extracted by using the smallest angle between the prediction error and the direction vector, in order to improve the accuracy of data extraction,θsw should be smaller than θkk∈0,2n−1,k≠sw. After data embedding, Equation (20) should be satisfied.
(20)∀k∈0,2n−1,k≠sw,cosθsw>cosθk.The following equation can be derived by using Cosine Theorem.(21)∀k∈0,2n−1,k≠sw,Δvi′×b→swΔvi′b→sw>Δvi′×b→kΔvi′b→k.It can be derived to the following equation.(22)Δvi+φb→sw×b→swb→sw−b→kb→k>0.Suppose that the vectorM→=b→sw/b→sw−b→k/b→k, and Equation (22) can be simplified as
(23)Δvi+φb→sw×M→>0.According to Inference2, the angle between b→sw and M→ is smaller than π/2, so b→sw×M→>0. Equation (24) can be derived.
(24)φ>Δv×−M→b→sw×M→.Since the modulus lengthΔv∈0,D, Equation (25) can be derived according to Inference 1.
(25)Δv=D−M→⋅−M→,φ>Δv×−M→b→sw×M→max=D⋅M→b→sw×M→.It can be derived to the following equation by using Cosine Theorem.(26)φ>D⋅M→b→sw⋅M→⋅cosθb→sw,M→⇔φ>Db→sw⋅cosθb→sw,M→.Suppose thatθb→sw,M→ denotes the angle between M→ and b→sw, in order to ensure that θsw is smaller than θk, θsw should satisfy the following equation.
(27)φ=Db→sw⋅cosθb→sw,M→.Ifφ satisfies Equation (27), secret data can be extracted correctly. According to Inference 2 and Equation (27), φ has the maximum if the angle between b→sw and b→k is smallest.Since direction vector is related to the shared parametersn, the shared parameters influence the value of φ. According to Equation (27), the relationship between φ and n is obtained as follows.
(28)φ=D,ifn=1,2,3,φ=3D,ifn=4,For example, for a clear description, letn=3. In this condition, the angle between b→0=−1,−1,−1 and direction vector b→1=−1,−1,1 is the smallest. The embedding key can be calculated by the following equation.
(29)M→=b→0b→0−b→1b→1=13−1,−1,2,cosb→0,M→=13,φ=Db→0cosb→0,M→=D.In order to explain the whole processes, the data embedding example is given as follows. For convenience, suppose thatn=2, the ith vertex vi′=1410,2120,790, the prediction value v¯i=1430,2280,750, and the secrete data w′=1,0. Since n=2, the weighted sum sw∈0,3 according to Equation (11), and four direction vectors can be obtained according to the mapping table. Four direction vectors b→0=−1,−1,−1, b→1=−1,−1,1, b→2=−1,1,−1, and b→3=−1,1,1 correspond to sw=0, sw=1, sw=2, and sw=3, respectively. Since w′=1,0, then sw′=2 can be computed, and sw′=2 corresponds to b→2=−1,1,−1. In addition, φ=250 can be obtained by Equation (28). The prediction error can be computed, and Δvi=−20,−160,40 according to Equation (9). Initially, the angle between Δvi and b→0,b→1,b→2,b→3 can be computed, and θ0=60.88°, θ1=40.12°, θ2=128.7°, and θ3=110.3°. After data hiding, θ2 between Δvi and b→2 should be the smallest angle. During data hiding, vi″=vi′+φb→2 and Δvi′=Δvi+φb→2. Hence, vi″=1160,2370,540 and Δvi′=−270,90,−210. Then, θ0=50.49°, θ1=91.87°, θ2=21.58°, and θ3=75.83° can be computed. The result shows that θ2 between Δvi′ and b→2 will be smallest after data hiding, and the secret data can be extracted by finding the smallest angle.Figure6 shows the changes of angles θsw between prediction error Δvi′ of 100 vertices and direction vector b→sw corresponding to secret data sw before and after data embedding when the shared parameter is 3. The result shows that the angle will become smaller after data embedding.Figure 6
The changes of angle between prediction errorΔvi′ and direction vector b→sw before and after data embedding.In addition, a large embedding key will make 3D model disturbed obviously. Hence, the embedding key will be discussed specifically in Section4 to balance the distortion of the directly decrypted model and the accuracy of data extraction.


## 3.3.1. Classifying the Vertices

For the vertex of 3D model, 1-ring neighborhood of the vertex refers to these vertices that are directly adjacent to the vertex. As shown in Figure3, the vertex vj′ is adjacent of the vertex vi′. If a vertex is modified to embed secret data, its 1-ring neighborhood cannot be modified, and it is mainly because the 1-ring neighborhood is required to calculate the prediction value of the vertex. Therefore, the dyeing algorithm is designed to classify all vertices into the embedded set and the referenced set because the color of adjacent vertices cannot be same. The vertices in the referenced set can be used to calculate the prediction value of the vertices in the embedded set because the referenced set consists of 1-ring neighborhood of all vertices in the embedded set, while the vertices in embedded set are modified to embed secret data.Figure 3
The actual value and the prediction value of the vertex.Suppose thatSe denotes the embedded set, and Sr denotes the referenced set. In order to obtain large data hiding capacity, the number of the vertices in the embedded set should be increased. The embedded set is the nonadjacent vertex set. According to graph theory, the existing polynomial algorithms can find the largest nonadjacent vertex set if the graph is a bipartite graph. However, the connectivity data of a 3D model cannot be represented by a bipartite graph since all loops of 3D model are 3. Hence, finding the largest embedded set in a 3D model is NP-hard problem. In order to increase data hiding capacity, the dyeing algorithm is designed to increase the number of the vertices in the embedded set.Referring to the four-color theorem, different colors are required for any two adjacent vertices. For 3D models, at least seven colors are needed to dye the vertices to ensure that the colors of the adjacent vertices are different. After completing the process of dyeing, the color with most vertices is selected, and all vertices of this color are regarded as the embedded set, and the remaining vertices are regarded as the referenced set. Suppose thatC denotes the color set of dyeing all vertices, Zi denotes the color set of 1-ring neighborhood of the vertex, and ci denotes the color of the ith vertex. The steps for the vertex classification using the dyeing algorithm are listed as follows.Step 1.
Suppose that the color of all vertices is black, and traverse all vertices in order of the vertex index.Step 2.
For an unclassified vertexvi, statistic the color set of its 1-ring neighborhood.Step 3.
Dye the vertexvi using the first color in C but not in Zi.Step 4.
Determine whether the next vertexvi+1 is black. If vi+1 is black, the classification ends. If vi+1 is not black, loop from Step 2 until no vertex is black.Step 5.
Select the most frequently used color, add all vertices of this color to the embedded set, and the remaining vertices are added to the referenced set.Since all vertices are traversed only once, the time complexity of the dyeing algorithm isOn. For example, as illustrated in Figure 4, let C=red,green,yellow,blue. Traverse the vertex v1, and let c1=red since Z1=black. Traverse the vertex v2, and let c2=green since Z1=black,red. Traverse the vertex v2, and let c2=yellow since Z1=black,red,green. After traversing all vertices, the most frequently used color green is selected. The vertex set {2,6,7,11} of color green is regarded as the embedded set, while the remaining vertices as the referenced set.Figure 4
The process of classifying the vertices using the dyeing method.


## 3.3.2. Computing of Prediction Error

The accuracy of prediction error directly affects the performance of data hiding. As shown in Figure3, the vertex vj′ is adjacent to the vertex vi′, and the vertex v¯i is the prediction value of vertex vi′. According to the correlation of adjacent vertices, prediction value v¯i can be calculated by using
(8)v¯i=1Ni∑j=1Nivj′,j∈1,Ni,where Ni denotes the number of the adjacent vertices of the vertex vi′.The prediction error of the vertexvi′ can be calculated by using
(9)Δvi=vi′−v¯i,where Δvi denotes the prediction error of the vertex vi′. Δvi is a three-dimensional vector with random direction. Due to the spatial correlation, the modulus length Δvi is usually small, and experiment results show that the modulus length Δvi has the maximum D. Hence, the range of Δvi is as follows.
(10)Δvi∈0,D.


## 3.3.3. Constructing the Mapping Table

In order to embed several bits into a vertex in the embedded set, several bits should be mapped to a direction vector.Data embedder converts secret data into several groups withn bits, and n is a shared parameter. Let a group with n bits denote as ww0,w1,⋯,wn−1. Suppose that sw denotes weighted sum of w, and sw is calculated as
(11)sw=∑i=0n−1wi⋅2i,sw∈0,2n−1.In order to embedsw into a vertex, the corresponding direction vector of swshould be constructed. Suppose that b→sw denotes the direction vector of sw, and sw is embedded by expanding the direction of prediction error with direction vector b→sw. The one-to-one mapping between weighted sum and direction vector is constructed as shown in Table 2. Let bk,j∈−1,1,k∈0,7, and if n≤3, eight direction vectors can be constructed. The mapping between direction vector and weighted sum is shown at the top three rows in Table 2. Let bk,j∈−1,0,1,k∈0,26, and if n=4, twenty-six direction vectors are constructed as shown at the fifth row in Table 2. Let bk,j∈−2,−1,0,1,2,k∈0,110, and if n=5 or n=6, 110 direction vectors are constructed. Let Wbk denote the direction weight of direction vector. As shown in Table 2, the direction vector b→k is sorted according to the value Wbk, and the direction weight Wbk of the direction vector is calculated as follows.
(12)Wbk=9bk,1+3bk,2+bk,3.Table 2
The one-to-one mapping table between weighted sum and direction vector.
Embed one bit into a vertex, which meansn=1, and sw∈0,1. On this condition, let bk,j∈−1,1.sw∈0,10(-1,-1,-1)1(-1,-1,1)Embed two bits into a vertex, which meansn=2, and sw∈0,3. On this condition, let bk,j∈−1,1.sw∈0,30(-1,-1,-1)1(-1,-1,1)2(-1,1,-1)3(-1,1,1)Embed three bits into a vertex, which meansn=3, and sw∈0,7. On this condition, let bk,j∈−1,1.sw∈0,70(-1,-1,-1)1(-1,-1,1)2(-1,1,-1)3(-1,1,1)4(1,-1,-1)5(1,-1,1)6(1,1,-1)7(1,1,1)Embed four bits into a vertex, which meansn=3, and sw∈0,15. On this condition, letbk,j∈−1,0,1.sw∈0,150(-1,-1,-1)1(-1,-1,0)2(-1,-1,1)3(-1,0,-1)4(-1,0,0)5(-1,0,1)6(-1,1,-1)7(-1,1,0)8(-1,1,1)9(0,-1,-1)10(0,-1,0)11(0,-1,1)12(0,0,-1)13(0,0,1)14(0,1,-1)15(0,1,0)Hence, if the shared parametern is obtained, the mapping table between weighted sum and direction vector can be constructed. For different sw, the corresponding direction vector b→sw can be found through the mapping table.For example, ifn=2, four direction vectors b→sw should be constructed to represent four weighted sum sw, respectively. Let bk,j∈−1,1, eight direction vectors can be constructed, and the first four direction vectors are selected according to the direction weight Wbk. As a result, the four direction vectors (-1,-1,-1), (-1,-1,1), (-1,1,-1), and (-1,1,1) are constructed to represent sw∈0,3, respectively.


## 3.3.4. Data Embedding

In order to embed secret data into the vertex, the vertex coordinates are required to be modified by using the direction vector and the embedding key. The weighted sumsw of ww0,w1,⋯,wn−1 is embedded in the vertex vi′ by using Equation (13).
(13)vi″=vi′+φb→sw,where vi″ is the modified vertex coordinate of vi′, parameter φ is the embedding key, and b→sw=bsw,x,bsw,y,bsw,z is the corresponding direction vector of sw.Referring to Equation (13), data embedding in the encrypted domain is performed as
(14)ci,j′=ci,j⋅csw=Evi,j,ri,j⋅E−φ⋅bsw,j,rsw−1modN2,ifφ⋅bsw,j<0,j∈1,2,3,ci,j′=ci,j⋅csw=Evi,j,ri,j⋅Eφ⋅bsw,j,rswmodN2,ifφ⋅bsw,j>0,j∈1,2,3,ci,j′=ci,j,ifφ⋅bsw,j=0,j∈1,2,3,where ci,j′ is the ciphertext of vi,j″, and csw is the ciphertext of φ⋅bsw,j. Moreover, if φ⋅bsw,j>0, addition homomorphism of Paillier cryptosystem is utilized to embed secret data. If φ⋅bsw,j<0, subtraction homomorphism expansion of Paillier cryptosystem is utilized to embed secret data.After data embedding, the corresponding change of the prediction error in the plaintext is as follows.(15)Δvi′=Δvi+φ⋅b→sw.AfterΔvi being changed, the angle between the direction of prediction error and direction vector will be small.In order to improve accuracy of data extraction, two inferences about vector are provided to calculate the embedded key.Inference 1.
Suppose thatm→1 and m→2 are two three-dimensional vectors. If the directions of m→1 and m→2 are the same, the modulus length m→1+m→2 has the maximum. If the directions of m→1 and m→2 are the opposite, the modulus length m→1+m→2 has the minimum. The proof is listed as follows.
(16)m→1+m→22=m→12+m→22+2m→1⋅m→1⋅cosθm→1,m→2,where θm→1,m→2 is the angle between m→1 and m→2. According to Equation (16), since m→1+m→2 is related to the angle, the above inference holds.Inference 2.
For two unit vectorsn→1 and n→2, let θn→1,n→2 denote the angle between two vectors, and let θn→1,n→1−n→2 denote the angle between n→1 and n→1−n→2. θn→1,n→1−n→2 and θn→1,n→2 are positively related. The smaller θn→1,n→2, the smaller θn→1,n→1−n→2. In addition, θn→1,n→1−n→2∈0,π/2. The proof is listed as follows.
(17)cosθn→1,n→1−n→2=n→1×n→1−n→2n→1⋅n→1−n→2=n→12−n→1⋅n→2cosθn→1,n→2n→1⋅n→1−n→2,where × denotes cross product. Since n→1 and n→2 are unit vector, Equation (18) can be obtained according to Equation (17).
(18)cosθn→1,n→1−n→2=1−cosθn→1,n→2/2.
According to Equation (18), cosθn→1,n→1−n→2>0, and θn→1,n→1−n→2∈0,π/2. The above inference holds.


## 3.3.5. Embedding Key Calculation

The embedding key influences the accuracy of data extraction. If the embedding key satisfies a certain condition, secret data can be extracted correctly.Figure5 shows the angle between prediction error and three direction vectors. Suppose that θsw denotes the angle between prediction error Δvi and direction vector b→sw corresponding to the secret data sw, and θk denotes the angle between prediction error Δvi and other direction vector b→kk∈0,2n−1,k≠sw. θsw is computed as
(19)cosθsw=Δvi′×b→swΔvi′b→sw.Figure 5
The angle between the prediction error and three direction vectors.Since the secret data is extracted by using the smallest angle between the prediction error and the direction vector, in order to improve the accuracy of data extraction,θsw should be smaller than θkk∈0,2n−1,k≠sw. After data embedding, Equation (20) should be satisfied.
(20)∀k∈0,2n−1,k≠sw,cosθsw>cosθk.The following equation can be derived by using Cosine Theorem.(21)∀k∈0,2n−1,k≠sw,Δvi′×b→swΔvi′b→sw>Δvi′×b→kΔvi′b→k.It can be derived to the following equation.(22)Δvi+φb→sw×b→swb→sw−b→kb→k>0.Suppose that the vectorM→=b→sw/b→sw−b→k/b→k, and Equation (22) can be simplified as
(23)Δvi+φb→sw×M→>0.According to Inference2, the angle between b→sw and M→ is smaller than π/2, so b→sw×M→>0. Equation (24) can be derived.
(24)φ>Δv×−M→b→sw×M→.Since the modulus lengthΔv∈0,D, Equation (25) can be derived according to Inference 1.
(25)Δv=D−M→⋅−M→,φ>Δv×−M→b→sw×M→max=D⋅M→b→sw×M→.It can be derived to the following equation by using Cosine Theorem.(26)φ>D⋅M→b→sw⋅M→⋅cosθb→sw,M→⇔φ>Db→sw⋅cosθb→sw,M→.Suppose thatθb→sw,M→ denotes the angle between M→ and b→sw, in order to ensure that θsw is smaller than θk, θsw should satisfy the following equation.
(27)φ=Db→sw⋅cosθb→sw,M→.Ifφ satisfies Equation (27), secret data can be extracted correctly. According to Inference 2 and Equation (27), φ has the maximum if the angle between b→sw and b→k is smallest.Since direction vector is related to the shared parametersn, the shared parameters influence the value of φ. According to Equation (27), the relationship between φ and n is obtained as follows.
(28)φ=D,ifn=1,2,3,φ=3D,ifn=4,For example, for a clear description, letn=3. In this condition, the angle between b→0=−1,−1,−1 and direction vector b→1=−1,−1,1 is the smallest. The embedding key can be calculated by the following equation.
(29)M→=b→0b→0−b→1b→1=13−1,−1,2,cosb→0,M→=13,φ=Db→0cosb→0,M→=D.In order to explain the whole processes, the data embedding example is given as follows. For convenience, suppose thatn=2, the ith vertex vi′=1410,2120,790, the prediction value v¯i=1430,2280,750, and the secrete data w′=1,0. Since n=2, the weighted sum sw∈0,3 according to Equation (11), and four direction vectors can be obtained according to the mapping table. Four direction vectors b→0=−1,−1,−1, b→1=−1,−1,1, b→2=−1,1,−1, and b→3=−1,1,1 correspond to sw=0, sw=1, sw=2, and sw=3, respectively. Since w′=1,0, then sw′=2 can be computed, and sw′=2 corresponds to b→2=−1,1,−1. In addition, φ=250 can be obtained by Equation (28). The prediction error can be computed, and Δvi=−20,−160,40 according to Equation (9). Initially, the angle between Δvi and b→0,b→1,b→2,b→3 can be computed, and θ0=60.88°, θ1=40.12°, θ2=128.7°, and θ3=110.3°. After data hiding, θ2 between Δvi and b→2 should be the smallest angle. During data hiding, vi″=vi′+φb→2 and Δvi′=Δvi+φb→2. Hence, vi″=1160,2370,540 and Δvi′=−270,90,−210. Then, θ0=50.49°, θ1=91.87°, θ2=21.58°, and θ3=75.83° can be computed. The result shows that θ2 between Δvi′ and b→2 will be smallest after data hiding, and the secret data can be extracted by finding the smallest angle.Figure6 shows the changes of angles θsw between prediction error Δvi′ of 100 vertices and direction vector b→sw corresponding to secret data sw before and after data embedding when the shared parameter is 3. The result shows that the angle will become smaller after data embedding.Figure 6
The changes of angle between prediction errorΔvi′ and direction vector b→sw before and after data embedding.In addition, a large embedding key will make 3D model disturbed obviously. Hence, the embedding key will be discussed specifically in Section4 to balance the distortion of the directly decrypted model and the accuracy of data extraction.


## 3.4. Data Extraction and Model Recovery

After receiving the encrypted model with secret data, receiver can decrypt 3D model with private keyλ and obtain the directly decrypted 3D model. The decryption of 3D model is as follows.
(30)vi,j″=Dci,j′=Lci,j′λmodN2LgλmodN2modN.The directly decrypted 3D model is similar to the original model because only the coordinates of some vertices are modified slightly during data embedding.After decrypting 3D model, all vertices are first classified into the embedded set and the referenced set using the dyeing algorithm. Secondly, prediction error of the vertex in embedded set is computed and the mapping table is constructed with the shared parametern. Then, the angles between prediction error and all direction vector are computed, and the smallest angle θsw is selected, which is the angle between Δvi′ and b→sw. At last, b→sw can be obtained, and the corresponding sw can be found by using the mapping table.sw is converted into n bit ww0,w1,⋯wn−1 by using
(31)wi=sw′2imod2,i=0,1,2,⋯,n−1.After data extraction, the embedding key and direction vector can be used to recovery the original 3D model by using(32)vi′=vi″−φ⋅b→sw.


## 4. Experiment Results and Discussion

The proposed method was implemented in Matlab 2016b under Window 7. We implemented the following experiment on 100 3D models and calculated the average of 100 3D models. Figure7 shows a group of experiment results of five 3D models in different parses. The phases from left to right are original 3D model, encrypted 3D model, data-embedded 3D model, directly decrypted 3D model, and recovered 3D model. Directly decrypted 3D models have low distortion, and recovered 3D models have high similarity compared to original 3D model.Figure 7
Illustrative examples showing the appearance of five models in different phases, include original 3D model, encrypted 3D model, data-embedded 3D model, directly decrypted 3D model, and recovery 3D model. (a) Fairy, (b) boss, (c) Devil, (d) Thing, and (e) Lord.
(a)(b)(c)(d)(e)The similarity of disturbed 3D models is evaluated by the signal-to-noise ratio (SNR). The higher the SNR, the better the imperceptibility after embedding watermark. SNR is computed as(33)SNR=10lg∑i=1NVvi,x−v¯x2+vi,y−v¯y2+vi,z−v¯z2∑i=1NVgi,x−vi,x2+gi,y−vi,y2+gi,z−vi,z2,where v¯x,v¯y,v¯z are the mean of vertex coordinates, vivi,x,vi,y,vi,z are the original vertex coordinates, and gigi,x,gi,y,gi,z are the coordinates of disturbed 3D model.SNRD is used to evaluate the similarity of directly decrypted models, and SNRR is used to evaluate the similarity of recovered models. In addition, the bit error rate (BER) is used to measure the error rate of data extraction. The lower the BER, the higher the accuracy of data extraction.


### 4.1. Decimal Reservation Digitsk

In order to observe the effect of decimal reservation digitsk on the quality of the decrypted model and time cost, we changed the value of k from 1 to 8 and perform encrypting and decrypting on 3D models. As shown in Figure 8(a), k=6 is a threshold, which enables 3D models recovery losslessly or limits recovery losslessly. Since the significant digits of vertex coordinates is 6, it is easy to cause permanent distortion if k<6. The distortion of directly decrypted model (SNRD) is calculated, which is shown in Figure 8(b). The time cost of encryption and decryption is related to the value k, which is shown in Figure 8(c). In order to obtain high quality of decrypted models and reduce the time cost, k is set to 4 in the next experiment.Figure 8
(a) Ratio of lossless recovery under differentk. (b) Average SNR of decrypted model under different k. (c) Average execution time of encryption and decryption under different k.
(a)(b)(c)


### 4.2. The Maximum of the Modulus LengthD

D is the maximum of the modulus length of the prediction error. Due to the spatial correlation of natural 3D model, the actual value and its prediction value of the vertex coordinates are relatively close. Hence, the modulus length of the prediction error always is small. In order to calculate the range of the prediction error, the experiment is performed on 40 3D models. Figure 9 shows the maximum modulus length of 40 3D models. For all 3D models, it can be observed that all maximum modulus lengths are less than 250. Hence, D is set to 250 in the next experiment.Figure 9
The maximum modulus length of forty 3D models.


### 4.3. The Choice of the Embedding Key and the Shared Parameter

According to Equation (13), the embedding key φ directly affects the distortion of decrypted model. If φ is large and satisfies Equation (27), secret data will be extracted correctly, but the quality of 3D models will be decreased obviously. If φ is small, the change of prediction error also will be small, and the accuracy of data extraction will reduce. However, there are several existing methods that can improve the accuracy of data extraction, such as ECC code and BCD code. Hence, in order to balance the accuracy of data extraction and the decrypted model, the experiment is carried out by select φ from 50 to 350 with the interval of 20.The larger the shared parameter, the greater the embedding capacity. However, the larger the shared parameter leads to that, more direction vectors are constructed, which affects the accuracy of data extraction. The experiment is carried out by selectingn from 1 to 6.Table3 shows the effect of the embedding key and shared parameter on BER of data extraction. Figure 10(a) shows the effect of the embedding key and shared parameter on SNRR of decrypted model. Figure 10(b) shows the effect of the embedding key and shared parameter on SNRD of decrypted model. With the change of n from 1 to 4, there are corresponding values of φ with high accuracy and low distortion. When n=1 and φ=110, BER=1.54%, SNRD=22.13, and SNRR=37.63. When n=2 and φ=110, BER=2.25%, SNRD=22.13, and SNRR=35.83. When n=3 and φ=110, BER=2.76%, SNRD=22.13, and SNRR=35.12. When n=4 and φ=170, BER=2.88%, SNRD=17.28, and SNRR=34.85. It is observed that the proposed method has high accuracy, high embedding capacity, and low distortion when n=3 and φ=110.Table 3
The effect of the embedding key and shared parameter on bit error rate of data extraction.
nφ1234565014.2%17.3%24.8%33.5%46.4%46.7%707.34%9.12%12.6%23.4%38.9%38.9%903.21%4.25%5.79%16.5%32.9%32.9%1101.54%2.25%2.76%10.8%25.4%25.5%1300.79%1.22%1.63%6.86%18.2%18.3%1500.32%0.63%0.98%4.25%13.2%13.3%1700.14%0.26%0.53%2.84%9.47%9.47%1900.08%0.11%0.24%1.77%6.24%6.25%2100.03%0.05%0.09%1.25%4.83%4.83%2300.01%0.02%0.04%0.84%3.05%3.06%2500000.53%2.24%2.25%2700000.32%1.76%1.76%2900000.21%1.43%1.46%2100000.15%1.09%1.09%3300000.09%0.79%0.79%3500000.04%0.42%0.42%Figure 10
(a) The effect of the embedding key and shared parameter onSNRD of decrypted model. (b) The effect of the embedding key and shared parameter on SNRR of decrypted model.
(a)(b)Figure11 shows decrypted models when n=3, and φ changes from 90 to 150. Figure 12 shows decrypted model when n changes from 1 to 4.Figure 11
Four decrypted models devil whenn=3, and φ changes from 90 to 150. (a) φ=90, (b) φ=110, (c) φ=130, and (d) φ=150.
(a)(b)(c)(d)Figure 12
Four decrypted models fairy whenn changes from 1 to 4. (a) n=1, φ=110; (b) n=2, φ=110; (c) n=3, φ=110; and (d) n=4, φ=170.
(a)(b)(c)(d)


### 4.4. The Effect of the Number of the Vertices onSNRR

Table4 shows the relationship between the number of the vertices and SNRR. If a 3D model has a large number of vertices, then the distance between the adjacent vertices will become small, which makes 3D model has a small D. In addition, D directly influence SNRR because of the relationship between D and ϕ. Hence, if a 3D model has more vertices, then the value of SNRR will be small, which means that the decrypted model has low distortion.Table 4
The relationship between the number of the vertices andSNRR.
ModelVerticesDEmbedding rateError rateSNRDSNRRFairy425220583.7%2.79%18.4334.79Boss1066318475.9%2.54%19.8534.52Devil2787216977.8%2.36%21.3235.16Thing11081213776.8%2.88%22.8735.84Lord25034311877.4%1.94%24.1635.32


### 4.5. Performance Comparison

In order to show the performance of the proposed method, we compare the proposed method with the existing method in [26] and in [28], as shown in Table 5. Compared with method in [26], the proposed method has three times the capacity and lower distortion than method in [26]. Moreover, the proposed has a lower BER, which can be reduced to zero by making the embedding key satisfy Equation (27).Table 5
The performance of the proposed method compared with the existing method.
MethodsEmbedding keyBERSNRDSNRRCapacity (bpv)The proposed methodφ=1102.76%22.1335.120.872φ=250015.24∞0.872Method in [26]4.22%5.3531.970.369Method in [28]030.08∞0.396Compared to method in [28], the embedding capacity of the proposed method is smaller. However, since several bits can be mapped to a direction vector using the mapping table, the capacity can be improved by embedding several bits into a vertex. Hence, the proposed method has a higher embedding capacity.In the proposed method, the distortion and the accuracy can be adjusted by using the embedding key. When the embedding key is 110, 3D models after data hiding has lower distortion. When the embedding key is 250, the BER of data extraction can be reduced to zero. In addition, the distortion will increase as the embedding key increases, the BER will decrease as the embedding key decreases.


## 4.1. Decimal Reservation Digitsk

In order to observe the effect of decimal reservation digitsk on the quality of the decrypted model and time cost, we changed the value of k from 1 to 8 and perform encrypting and decrypting on 3D models. As shown in Figure 8(a), k=6 is a threshold, which enables 3D models recovery losslessly or limits recovery losslessly. Since the significant digits of vertex coordinates is 6, it is easy to cause permanent distortion if k<6. The distortion of directly decrypted model (SNRD) is calculated, which is shown in Figure 8(b). The time cost of encryption and decryption is related to the value k, which is shown in Figure 8(c). In order to obtain high quality of decrypted models and reduce the time cost, k is set to 4 in the next experiment.Figure 8
(a) Ratio of lossless recovery under differentk. (b) Average SNR of decrypted model under different k. (c) Average execution time of encryption and decryption under different k.
(a)(b)(c)


## 4.2. The Maximum of the Modulus LengthD

D is the maximum of the modulus length of the prediction error. Due to the spatial correlation of natural 3D model, the actual value and its prediction value of the vertex coordinates are relatively close. Hence, the modulus length of the prediction error always is small. In order to calculate the range of the prediction error, the experiment is performed on 40 3D models. Figure 9 shows the maximum modulus length of 40 3D models. For all 3D models, it can be observed that all maximum modulus lengths are less than 250. Hence, D is set to 250 in the next experiment.Figure 9
The maximum modulus length of forty 3D models.


## 4.3. The Choice of the Embedding Key and the Shared Parameter

According to Equation (13), the embedding key φ directly affects the distortion of decrypted model. If φ is large and satisfies Equation (27), secret data will be extracted correctly, but the quality of 3D models will be decreased obviously. If φ is small, the change of prediction error also will be small, and the accuracy of data extraction will reduce. However, there are several existing methods that can improve the accuracy of data extraction, such as ECC code and BCD code. Hence, in order to balance the accuracy of data extraction and the decrypted model, the experiment is carried out by select φ from 50 to 350 with the interval of 20.The larger the shared parameter, the greater the embedding capacity. However, the larger the shared parameter leads to that, more direction vectors are constructed, which affects the accuracy of data extraction. The experiment is carried out by selectingn from 1 to 6.Table3 shows the effect of the embedding key and shared parameter on BER of data extraction. Figure 10(a) shows the effect of the embedding key and shared parameter on SNRR of decrypted model. Figure 10(b) shows the effect of the embedding key and shared parameter on SNRD of decrypted model. With the change of n from 1 to 4, there are corresponding values of φ with high accuracy and low distortion. When n=1 and φ=110, BER=1.54%, SNRD=22.13, and SNRR=37.63. When n=2 and φ=110, BER=2.25%, SNRD=22.13, and SNRR=35.83. When n=3 and φ=110, BER=2.76%, SNRD=22.13, and SNRR=35.12. When n=4 and φ=170, BER=2.88%, SNRD=17.28, and SNRR=34.85. It is observed that the proposed method has high accuracy, high embedding capacity, and low distortion when n=3 and φ=110.Table 3
The effect of the embedding key and shared parameter on bit error rate of data extraction.
nφ1234565014.2%17.3%24.8%33.5%46.4%46.7%707.34%9.12%12.6%23.4%38.9%38.9%903.21%4.25%5.79%16.5%32.9%32.9%1101.54%2.25%2.76%10.8%25.4%25.5%1300.79%1.22%1.63%6.86%18.2%18.3%1500.32%0.63%0.98%4.25%13.2%13.3%1700.14%0.26%0.53%2.84%9.47%9.47%1900.08%0.11%0.24%1.77%6.24%6.25%2100.03%0.05%0.09%1.25%4.83%4.83%2300.01%0.02%0.04%0.84%3.05%3.06%2500000.53%2.24%2.25%2700000.32%1.76%1.76%2900000.21%1.43%1.46%2100000.15%1.09%1.09%3300000.09%0.79%0.79%3500000.04%0.42%0.42%Figure 10
(a) The effect of the embedding key and shared parameter onSNRD of decrypted model. (b) The effect of the embedding key and shared parameter on SNRR of decrypted model.
(a)(b)Figure11 shows decrypted models when n=3, and φ changes from 90 to 150. Figure 12 shows decrypted model when n changes from 1 to 4.Figure 11
Four decrypted models devil whenn=3, and φ changes from 90 to 150. (a) φ=90, (b) φ=110, (c) φ=130, and (d) φ=150.
(a)(b)(c)(d)Figure 12
Four decrypted models fairy whenn changes from 1 to 4. (a) n=1, φ=110; (b) n=2, φ=110; (c) n=3, φ=110; and (d) n=4, φ=170.
(a)(b)(c)(d)


## 4.4. The Effect of the Number of the Vertices onSNRR

Table4 shows the relationship between the number of the vertices and SNRR. If a 3D model has a large number of vertices, then the distance between the adjacent vertices will become small, which makes 3D model has a small D. In addition, D directly influence SNRR because of the relationship between D and ϕ. Hence, if a 3D model has more vertices, then the value of SNRR will be small, which means that the decrypted model has low distortion.Table 4
The relationship between the number of the vertices andSNRR.
ModelVerticesDEmbedding rateError rateSNRDSNRRFairy425220583.7%2.79%18.4334.79Boss1066318475.9%2.54%19.8534.52Devil2787216977.8%2.36%21.3235.16Thing11081213776.8%2.88%22.8735.84Lord25034311877.4%1.94%24.1635.32


## 4.5. Performance Comparison

In order to show the performance of the proposed method, we compare the proposed method with the existing method in [26] and in [28], as shown in Table 5. Compared with method in [26], the proposed method has three times the capacity and lower distortion than method in [26]. Moreover, the proposed has a lower BER, which can be reduced to zero by making the embedding key satisfy Equation (27).Table 5
The performance of the proposed method compared with the existing method.
MethodsEmbedding keyBERSNRDSNRRCapacity (bpv)The proposed methodφ=1102.76%22.1335.120.872φ=250015.24∞0.872Method in [26]4.22%5.3531.970.369Method in [28]030.08∞0.396Compared to method in [28], the embedding capacity of the proposed method is smaller. However, since several bits can be mapped to a direction vector using the mapping table, the capacity can be improved by embedding several bits into a vertex. Hence, the proposed method has a higher embedding capacity.In the proposed method, the distortion and the accuracy can be adjusted by using the embedding key. When the embedding key is 110, 3D models after data hiding has lower distortion. When the embedding key is 250, the BER of data extraction can be reduced to zero. In addition, the distortion will increase as the embedding key increases, the BER will decrease as the embedding key decreases.


## 5. Conclusion

The method is proposed to preserve privacy and protect copyright of 3D models. Moreover, the proposed method has very good potential for practical applications since the directly decrypted models have lower distortion than the original models. Original 3D model is preprocessed, and the vertex of 3D model is encrypted by using Paillier cryptosystem. In the cloud, the dyeing method is designed to classify all vertices into the embedded set and the referenced set. After that, secret data is embedded by expanding direction of prediction error with direction vector. The prediction error of the vertex in the embedded set is computed by using the referenced set, and the direction vector is obtained according to the mapping table. Secret data can be extracted by comparing the angle between the direction of prediction error and direction vector, and the original model can be restored using the referenced set. The proposed method is efficient to protect copyright of 3D models in the cloud when the cloud administrator does not know the content of the 3D models. Moreover, the proposed has higher capacity and lower distortion than the existing methods.For the future work of RDH-ED method, we will investigate the following two possible research directions. (1) Extracting information from plaintext is expanded to extracting from plaintext and ciphertext. (2) Further improve the similarity between the directly decrypted model and the original model.



---

*Source: 8851999-2020-09-01.xml*