Reducing file size and time complexity in secret sharing based document protection

1.   Introduction

The rapid development of network technology has brought us into the era of informationization. The Internet facilitates the exchange of information with others, various web applications ^[1,2] greatly facilitate people's daily life. However, information security has become a major issue in the communication via Internet. Many approaches can be employed to protect secret information. $(k, n)$ Secret sharing scheme is an important issue in cryptography which provides an efficient way to safely keeping secret key. In $(k, n)$ Secret sharing, a secret is encrypted into $n$ shares in such a way that any group of at least $k$ shares can recover the secret and less than $k$ shares get nothing on this secret. There are different approaches to achieve secret sharing, for instance, Shamir's scheme ^[3] was based on polynomial; Blakley's scheme ^[4] was based on geometry, and Chinese Reminder Theorem was another approach for secret sharing schemes ^[5,6].

Many kinds of digital information can be regarded as secret key that can be protected using Shamir's secret sharing scheme. For instance, $(k, n)$ secret image sharing schemes ^[7,8,9] takes digital image as secret key, and encrypts it into meaningless shadows such that $k$ or more shadows can reconstruct the image, less than $k$ shadows get nothing on the secret image. In 2014, Tu and Hsu proposed a novel document protecting scheme ^[10] which is based on Shamir's $(k, n)$ secret sharing. In their scheme, a secret document is regarded as secret key and is encrypted into $n$ shares via a cover document, both at least $k$ shares and cover document are necessary to recover the secret document, less than $k$ shares or lack of cover image leads no information on the secret document. Comparing to other secret sharing based document protecting scheme ^[11,12], Tu-Hsu's scheme has the following advantages. First, the cover document looks innocent that would probably be ignored by hackers. Second, those schemes ^[11,13] adopts a $(n, n)$ secret sharing scheme, on the contrary, Tu-Hsu's scheme uses $(k, n)$ secret sharing which is more applicable than the schemes ^[11,13].

As we know, the size of share is an important issue in secret sharing, since smaller share size can reduce storage and computation cost. Lots of works ^[14,15,16] addressed the topic of reducing share size in secret sharing based cryptographic schemes. The share in Tu-Hsu's scheme is generated byte-wisely in $GF(257)$ from all inner codes of secret document, where $257$ is a Fermat Prime that satisfies $257 = 2^{2^{3}}+1$. The computation in $GF(257)$ can guarantee that all inner codes can be correctly recovered since it is the smallest prime larger than $2^{8} = 256$. However, the computation in $GF(257)$ would cause share size expansion when the it equals to $255$ or $256$. In fact, the problem of share size expansion can be solved by using $GF(2^{8})$ ^[17,18] instead of $GF(257)$, but the time complexity of computation in $GF(2^{8})$ is much higher than running time in $GF(257)$. It needs to transform integers in $[0,255]$ into corresponding polynomials in $GF(2^{8})$, and then the computation between integers is transformed int computation between polynomials ($\mbox{mod} x^{8}+x^{4}+x^{3}+x+1$). Some secret image sharing schemes computed shadows in $GF(251)$ that can resolve the problem of share size expansion, but it would cause image distortion during reconstruction. Therefore the approach of $GF(251)$ can not be adopted in document protecting scheme since each inner code of document should be correctly reconstructed.

In this paper, we construct a new secret sharing based document protecting scheme which is extended from Tu-Hsu's scheme ^[10]. In their scheme, all inner codes of secret document are encrypted into shares single byte-wisely in $GF(257)$. Another reasonable choice is using $GF(2^{8})$ rather than the ordinary arithmetic $GF(257)$, i.e., mod $251$, to deal with sharing byte-wisely, so that the calculation can process the whole range $[0,255]$. And, file size is not expanded, because we do not have the values of $255$ and $256$. However, mathematical calculations in polynomial processing under $GF(2^{8})$ are complicated. If we process not byte-wisely, but deal with $N$ bits each time. Tu-Hsu's approach is based on $GF(257)$, i.e., $GF(2^{8}+1)$. Thus, we may use $GF(2^{N}+1)$, where $2^{N}+1$ is prime. In fact, the value of $257$ in Tu-Hsu's approach is a Fermat prime. As we know, the only known Fermat primes are $3, 5, 17,257$, and $65537$, where $N$ is $1, 2, 4, 8$, and $16$, respectively. Our motivation is still using a simple modular arithmetic, modularizing a Fermat prime. Different from their approach, our scheme combines each two inner codes of secret document into a new double-bytes inner code (i.e., $N = 16$), and all these double-byte inner codes are encrypted into shares with computation in $GF(65537)$, where $65537$ is also a Fermat prime that equals to $2^{2^{4}}+1$. Using our approach, each share takes two bytes storage space which can be read and stored efficiently in programs and the share size can be reduced from Tu-Hsu's scheme. On the other hand, the number of combined inner codes in secret document is half of inner codes number using Tu-Hsu's approach, thus the time complexity in our scheme is expected half of Tu-Hsu's approach, experimental results demonstrate that our scheme is capable of saving almost half running time from Tu-Hsu's scheme.

The rest of this paper is organized as follows. In next section, we introduce Shamir's $(k, n)$ secret sharing scheme, Tu-Hsu's secret sharing based document protecting scheme and definition of Fermat Prime respectively. Our proposed scheme is described in Section 3, and the analysis on share size and running time in our scheme is also discussed in this part. In section 4, the comparisons of share size and running time between our scheme and Tu-Hsu's scheme are shown in the experimental results. The conclusion is made in section 5.

2.   Preliminaries

2.1.   Shamir's $(k, n)$ secret sharing scheme

A $(k, n)$ secret sharing scheme is a method where a secret is encrypted into $n$ shares, in such way that any $k$ or more shares can reconstruct the secret and fewer than $k$ shares get nothing on the secret. More formally, in secret sharing scheme, there exists $n$ users $\mathcal{P} = \{P_{1}, P_{2}, ..., P_{n}\}$ and a dealer $\mathcal{D}$. In 1979, Shamir introduced a polynomial based $(k, n)$ secret sharing scheme which is shown in following Scheme 1.

Scheme 1: Shamir's $(k, n)$ secret sharing scheme

Sharing phase:

$1$ $\mathcal{D}$ randomly chooses a $k-1$ degree polynomial $f(x)\in GF(q)[x]$ which satisfies $s = f(0)\in GF(q)$. ($q$ is a prime number which satisfies the security requirement)

$2$ $\mathcal{D}$ selects $n$ different integers $x_{1}, x_{2}, ..., x_{n}$ in $GF(q)$ as $n$ different IDs and computes $n$ shares $v_{i} = f(x_{i}), i = 1, 2, ..., n$.

$3$ $\mathcal{D}$ sends each share and its ID $(v_{i}, x_{i}), i\in[1, n]$ to $P_{i}$ respectively.

Reconstruction phase:

$1$ $m(\geq k)$ users (say $P_{1}, P_{2}, ..., P_{m}$) pool their shares and IDs $(v_{i}, x_{i}), i = 1, 2, ..., m$ together.

$2$ Computing the interpolated polynomial $f(x)$ on $(v_{i}, x_{i}), i = 1, 2, ..., m$ by the following Lagrange equation:

Then the secret $s = f(0)$.

2.2.   Fermat Prime Number

The Fermat Number is a sequence of integers $F_{t}$ that satisfies:

A prime number $N$ is called Fermat Prime Number, when there exist $t\geq0$, and satisfies that $N = 2^{2^{t}}+1$. $F_{0} = 1, F_{1} = 3, F_{2} = 17, F_{3} = 257$ and $F_{4} = 65537$ are five Fermat Prime Numbers and any Fermat Prime Number $F_{t}$ for $t\geq5$ has not been found yet.

2.3.   Tu-Hsu's scheme

Tu and Hsu constructed a document protecting scheme using Shamir's $(k, n)$ secret sharing. Their scheme can be also divided into Sharing Phase and Reconstruction Phase: During Sharing Phase, a secret document SD was encrypted into $n$ shares on different IDs, where these IDs are generated from a cover document CD; in Reconstruction Phase, acknowledgement of CD and a group of at least $k$ shares can reconstruct SD. Before Sharing Phase, all the words in SD and CD are encoded into inner codes using an appropriate encoding method. We use the notations $S_{i}, i = 1, 2, ..., m$ and $C_{i}, i = 1, 2, ..., l$ to present the inner codes of SD and CD in byte-wise respectively. Tu-Hsu's scheme is described in following Scheme 2.

Scheme 2: Tu-Hsu's $(k, n)$ secret sharing based document protecting scheme

Sharing phase: Input: secret document SD $= (S_{1}, S_{2}, ..., S_{m})$, cover document CD $= (C_{1}, C_{2}, ..., C_{l})$; Output: $n$ shares $V_{1}, V_{2}, ..., V_{n}$

$1$ The $l$ inner codes $(C_{1}, C_{2}, ..., C_{l})$ is divided into multiple $n$-length blocks $B_{1}, B_{2}, ..., B_{\lfloor\frac{l}{n}\rfloor}$, where the $n$ inner codes in each block are different. The method for generating these $n$-length blocks is introduced in following Algorithm 1.

$2$ For each $k-1$ inner codes $(S_{r(k-1)+1}, S_{r(k-1)+2}, ..., S_{r(k-1)+k-1}, r = 0, 1, ..., \frac{m}{k-1})$ in $SD$, $\mathcal{D}$ constructs a $k-1$ degree polynomial $f_{r}(x)\in GF(257)[X]$ using these $k-1$ inner codes as coefficients, and the constant term $A_{r, 0}$ is randomly selected:

(The reason for only $k-1$ (not $k$) inner codes are used as coefficients is to enhance the security level.)

$3$ For each polynomial $f_{r}(x), r\in[0, \frac{m}{k-1}]$, using $n$ different inner codes $x_{r, j}, j = 1, 2, ..., n$ in $B_{(r+1)mod \lfloor\frac{l}{n}\rfloor}$ as different IDs to compute $n$ sub-shares $v_{r, j} = f_{r}(x_{r, j}), j = 1, 2, ..., n$.

$4$ The share $V_{j}, j = 1, 2, ..., n$ for each user $P_{j}$ is

Reconstruction phase: Input cover document CD, $k$ shares $V_{1}, V_{2}, ..., V_{k}$; Output: secret document SD

$1$ Obtain the multiple $n$-length blocks $B_{1}, B_{2}, ..., B_{\lfloor\frac{l}{n}\rfloor}$ from CD using following Algorithm 1.

$2$ Reconstructing $f_{r}(x), r = 0, 1, ..., \frac{m}{k-1}$ using Lagrange interpolation:

where $x_{r, i}, i\in[1, k]$ are the IDs of $v_{r, i}$ that are obtained from $B_{(r+1)mod \lfloor \frac{l}{2n}\rfloor}$

$3$ The last $k-1$ coefficients in $f_{r}(x)$ are $k-1$ corresponding inner codes of SD, thus SD (all inner codes) can be recovered.

The method of dividing all inner codes in CD into multiple $n$-length blocks is described in following Algorithm 1. Using Algorithm 1, one can guarantee that the $n$ elements in each block are different.

In Sharing Phase, Tu and Hsu selects the prime $257$ in the finite field $GF(257)$ to computing shares and reconstructing document. As introduced previously, $257$ is a Fermat Prime that satisfies $257 = 2^{8}+1$, it is only $1$ larger than $2^{8} = 256$, where $256$ is exactly one byte length. Since each inner code of secret document in Tu-Hsu's scheme takes one byte storage space, the share generation and secret reconstruction achieve highest efficiency when the the corresponding computation is in $GF(257)$.

However, computation in $GF(257)$ would causes some sub-shares equal to $256$, that cannot be stored in one byte space. To ensure the correctness of each sub-share, they adopt a special way to present $255$ and $256$. The sub-share $255$ is stored in two bytes $255||0$, and sub-share $256$ is stored in two bytes $255||1$. During Reconstruction phase, when a sub-share is $255$, one should know that the next byte is also combined with previous byte. If the value is $0$ in next byte, the sub-share is $255$, otherwise the sub-share is $256$. For instance, if a group of sub-shares is $(45, 79,255, 0, 80,178)$ which is stored in $6$ bytes, then there are $5$ sub-shares $(45, 79,255, 80,178)$ in total; if a group of sub-shares is $(97,255, 1, 75)$ which is stored in $4$ bytes, there are $3$ sub-shares $97,256, 75$; if a group of sub-shares is $(189,253, 94,180)$ which is stored in $4$ bytes, there are $4$ sub-shares $189,253, 94,180$.

3.   Proposed scheme

The share size is an important issue in secret sharing scheme. For instance, Shamir's $(k, n)$ secret sharing hides the secret $s$ in one coefficient $a_{0}$, thus the size of share equals to the size of secret, $|V| = |S|$; $(k, n)$ secret image sharing scheme uses all $k$ coefficients to hide a group of $k$ pixels, the share size is $\frac{1}{k}$ time of secret image, $|V| = \frac{|S|}{k}$. Tu-Hsu's scheme uses $k-1$ out of $k$ coefficients to hide a group of $k-1$ inner codes of secret document, the theoretical share size is $|V| = \frac{|S|}{k-1}$. However, Tu-Hsu's scheme uses $GF(257)$ in share generation, when the share belongs to $\{0, 1, ..., 254\}$, it can be stored in one byte, and there is no share size expansion; but when the share equals to $255$ or $256$, it is stored in two bytes, this would causes share size expansion from the theoretical size.

In this paper, we aim to construct a new secret sharing based secret document protecting scheme that can reduce share size from Tu-Hsu's scheme. In Tu-Hsu's scheme, all inner codes of secret document are encrypted single-byte wisely in $GF(257)$, and it causes share size expansion when the share equals to $255$ or $256$. The probability of share size expansion is $\frac{2}{257}$. Different from their approach, our scheme first combines each two inner codes of secret document into one inner code, where each new inner code in our approach takes double-bytes storage space. Then the shares are generated from this double-bytes inner codes with the computation in $GF(65537)$, and the secret reconstruction is also computed in $GF(65537)$ from double-byte shares. Notice that $65537$ is also a Fermat Prime Number which is introduced previously, and $65537$ is the only Fermat Prime Number which is larger than $257$. The computation in $GF(65537)$ has following advantages:

$1$ $65537$ is only $1$ larger than $2^{16} = 65536$, where $63336$ is exact two bytes length. Therefore the computation in $GF(65537)$ has high efficiency as the computation in $GF(257)$.

$2$ The share size using our approach would expand when the share equals to $65535$ or $65536$. The probability of share size expansion is $\frac{2}{65537}$, which is much smaller than the probability $\frac{2}{257}$ of share size expansion in Tu-Hsu's approach. Therefore our scheme can reduce share size from Tu-Hsu's scheme.

$3$ The number of inner codes in our approach is half inner codes number in Tu-Hsu's approach, thus our scheme has less time complexity than Tu-Hsu's scheme.

Our proposed scheme is described in following Scheme 3.

Scheme 3: Our proposed scheme

Sharing phase: Input: secret document $SD = (S_{1}, S_{2}, ..., S_{m})$, cover document $CD = (C_{1}, C_{2}, ..., C_{l})$; Output: $n$ shares $V_{1}, V_{2}, ..., V_{n}$

$1$ Combine each of two inner codes in $SD$ and $CD$, thus $SD = (S^{*}_{1}, S^{*}_{2}, ..., S^{*}_{\frac{m}{2}})$ and $CD = (C^{*}_{1}, C^{*}_{2}, ..., C^{*}_{\frac{l}{2}})$. Each new inner code in $SD$ and $CD$ is stored in double-bytes.

$2$ Dividing $(C^{*}_{1}, C^{*}_{2}, ..., C^{*}_{\frac{l}{2}})$ into multiple $n$-length blocks $B^{*}_{1}, B^{*}_{2}, ..., B^{*}_{\lfloor \frac{l}{2n}\rfloor}$ using Algorithm 1.

$3$ For each group of $k-1$ inner codes $(S^{*}_{r(k-1)+1}, S^{*}_{r(k-1)+2}, ..., S^{*}_{r(k-1)+k-1}, r\in[0, \frac{m}{2(k-1)}]$ in $SD$, $\mathcal{D}$ randomly selects an integer $A_{r, 0}\in[0, 65536]$ and generates a $k-1$ degree polynomial $f^{*}_{r}(x)$:

$4$ For each polynomial $f^{*}_{r}(x), r\in[0, \frac{m}{2(k-1)}]$, using $n$ different integers $x_{r, j}, j = 1, 2, ..., n$ in $B_{(r+1)mod w}$ as $n$ different IDs to compute $n$ sub-shares $v_{r, j} = f_{r}(x_{r, j}), j = 1, 2, ..., n$. If a sub-share is $65535$ or $65536$, it is stored in three bytes where the first double-bytes is set $65535$ and the last byte is set $0$ or $1$ respectively.

$5$ The share $V_{j}, j = 1, 2, ..., n$ for each user $P_{j}$ is

Reconstruction phase: Input cover document $CD$, $k$ shares $V_{1}, V_{2}, ..., V_{k}$; Output: secret document $SD$

$1$ Obtain the $n$-length blocks $B^{*}_{1}, B^{*}_{2}, ..., B^{*}_{\lfloor\frac{l}{2n}\rfloor}$ from $CD$ using Algorithm 1.

$2$ Reconstructing the polynomials $f^{*}_{r}(x), r = 0, 1, ..., \frac{m}{2(k-1)}$ using Lagrange interpolation:

where $x_{r, i}, i\in[1, k]$ are the IDs of $v_{r, i}$ that are obtained from $B^{*}_{(r+1)\mbox{mod} \lfloor \frac{l}{2n}\rfloor}$

$3$ The last $k-1$ coefficients in $f^{*}_{r}(x)$ are $k-1$ inner codes of $SD$, thus $SD$ (all inner codes) can be recovered correspondingly.

The difference between our scheme and Tu-Hsu's scheme is that the proposed scheme combines each two bytes of inner codes into a double-bytes block, and computing sub-shares in $GF(P)$ where $P = 65537$. In Tu-Hsu's scheme, sub-shares are computed in $GF(257)$, and the sub-share size expands from one byte to two bytes when the sub-share equals to $255$ or $256$, the probability that the sub-share equals to $255$ or $256$ is $\frac{2}{257}$, thus the theoretical average share size (combined by all sub-shares) is

In our scheme, the sub-share size expands from double-bytes to three bytes when sub-share equals to $63355$ or $65536$, the probability that the sub-share equals to $65535$ or $65536$ is $\frac{2}{65537}$, thus the theoretical average share size (combined by all sub-shares) is

It is obvious that $|V_{Pro}| < |V_{Tu-Hsu}|$, therefore our scheme can reduce share size of Tu-Hsu's scheme.

In addition, since our scheme encrypts secret document double-bytes wisely, the number of inner codes for a secret document in our scheme is $\frac{1}{2}$ times of Tu-Hsu's scheme. As analyzed in ^[10], the time complexities for share generation and secret document reconstruction is $O(hn)$ and $O(hk)$ respectively, where $h$ denotes the number of inner codes of secret document. Since the multiplications in $GF(257)$ and $GF(65537)$ have similar running time, the time complexities in our scheme are $O(\frac{hn}{2})$ and $O(\frac{hk}{2})$ for share generation and secret document reconstruction respectively. It means that our approach is capable of saving half running time from Tu-Hsu's approach.

4.   Comparisons

In this section, we use experimental results to show the advantages of our scheme to Tu-Hsu' scheme. Our experiments adopt the same samples in ^[10] as the secret document and cover document, and three different thresholds $(2, 5), (3, 6), (4, 7)$ secret sharing schemes were implemented on Tu-Hsu's approach and our approach using Matlab language, respectively. The program runs at platform of CPU i5-7300HQ, and 8.0 GB RAM, and the operating system is Window 7 Professional. The share size and running time are compared in three thresholds secret sharing schemes between these two approaches. Figure 1 shows the secret document and cover document, both are in traditional Chinese. Figure 2 lists the inner codes of the secret document ($76$ bytes) and cover document, which are transformed by the encoding method "Big5".

Figure 1.  Content of secret document and cover document.

DownLoad: Full-Size Img PowerPoint

Figure 2.  Inner codes of secret document and cover document.

DownLoad: Full-Size Img PowerPoint

Experiment 1: $(2, 5)$ secret sharing based on secret document and cover document using Tu-Hsu's approach and our approach.

In Experiment 1, the secret document is first encoded into $5$ shares using Tu-Hsu's $(2, 5)$ secret sharing where the all inner codes of secret document is encrypted single byte-wisely. Then we use our approach to encode secret document into $5$ shares where the inner codes are encrypted double-byte wisely. Figure 3 lists the shares that are generated in Tu-Hsu's approach and our approach respectively.

Figure 3.  Shares in Experiment 1.

DownLoad: Full-Size Img PowerPoint

$(2, 5)$ secret sharing scheme uses only $1$ inner code as a coefficient in polynomials to generating shares, thus the size of share would equals to the size of secret document theoretically. From Figure 3 we can see that the sizes of $5$ share using Tu-Hsu's approach are $76, 76, 77, 78, 76$ bytes respectively. The share size expansion are caused by the three sub-shares $256,256,255$ (marked in red), which are stored in two bytes. On the other hand, the sizes of $5$ shares using our approach are all $76$ bytes, there is no share size expansion using our approach.

Experiment 2: $(3, 6)$ secret sharing based on secret document and cover document using Tu-Hsu's approach and our approach.

In Experiment 2, secret document is first encoded into $6$ shares using Tu-Hsu's $(3, 6)$ secret sharing where the all inner codes of secret image is encrypted byte-wisely. Then we use our approach to encode secret document into $6$ shares where the inner codes are encrypted double-byte wisely. Figure 4 lists a group of $6$ shares that are generated in Tu-Hsu's approach and our approach respectively.

Figure 4.  Shares in Experiment 2.

DownLoad: Full-Size Img PowerPoint

Since both $(3, 6)$ secret sharing in Tu-Hsu's approach and our approach takes a group of $2$ inner codes as coefficients in a polynomial, the theoretical share size is $\frac{1}{2}$ of the secret document. As listed in Figure 4, share 1 and 5 consists of $39$ bytes which is caused by the sub-shares marked in red, and each share in our approach is $38$ bytes which equals to $\frac{1}{2}$ of secret document.

Experiment 3: $(4, 7)$ secret sharing based on secret document and cover document using Tu-Hsu's approach and our approach.

In Experiment 3, secret document is first encoded into $7$ shares using Tu-Hsu's $(4, 7)$ secret sharing where the all inner codes of secret image is encrypted byte-wisely. Then we use our approach to encode secret document into $7$ shares where the inner codes are encrypted double-byte wisely. Figure 5 lists a group of $7$ shares that are generated in Tu-Hsu's approach and our approach respectively. We can also observe that the share size in our approach is smaller than the share size in Tu-Hsu' approach.

Figure 5.  Shares in Experiment 3.

DownLoad: Full-Size Img PowerPoint

As we discussed previously, the operations in $GF(257)$ and $GF(65537)$ have similar time complexity, and thus the share encryption and secret reconstruction using our scheme is expected to save $\frac{1}{2}$ running time from Tu-Hsu's approach. To authenticate this assumption, we implement the all previous experiments and a $(5, 8)$ secret sharing based secret document protection scheme three times, and record the running times of Tu-Hsu's approach and our approach respectively, the following Table 1 lists all the data from these experiments which includes the total share size, running time for share generation and secret reconstruction.

Table 1.  Comparisons between Tu-Hsu's approach and our approach.

Threshold	Approach	Total Share Size			Running Time (second)
		(byte)			Share Generation			Secret Reconstruction
		$(1)$	$(2)$	$(3)$	$(1)$	$(2)$	$(3)$	$(1)$	$(2)$	$(3)$
$(2, 5)$	Tu-Hsu's	$383$	$382$	$383$	$0.007$	$0.007$	$0.011$	$0.448$	$0.423$	$0.417$
	Our	$380$	$380$	$380$	$0.004$	$0.005$	$0.006$	$0.256$	$0.239$	$0.217$
$(3, 6)$	Tu-Hsu's	$230$	$228$	$230$	$0.014$	$0.013$	$0.012$	$0.403$	$0.399$	$0.407$
	Our	$228$	$228$	$228$	$0.006$	$0.008$	$0.009$	$0.227$	$0.263$	$0.230$
$(4, 7)$	Tu-Hsu's	$184$	$184$	$183$	$0.013$	$0.011$	$0.010$	$0.479$	$0.469$	$0.455$
	Our	$182$	$182$	$182$	$0.009$	$0.007$	$0.005$	$0.252$	$0.246$	$0.258$
$(5, 8)$	Tu-Hsu's	$155$	$154$	$155$	$0.016$	$0.014$	$0.015$	$0.489$	$0.495$	$0.493$
	Our	$152$	$152$	$152$	$0.008$	$0.008$	$0.009$	$0.261$	$0.259$	$0.258$

---

 | Show Table

DownLoad: CSV

The statistical results in Table 1 shows that our approach is capable of reducing share size from Tu-Hsu's approach and also save almost half running time in share generation or secret reconstruction. Next, we use $10$ secret documents with different sizes ($100$ bytes to $1000$ bytes) to test the running times for secret reconstruction with three approaches: computations in $GF(2^{8}), GF(257)$ and $GF(65537)$ respectively. The following Table 2 lists all the running times for secret reconstruction with three thresholds $(2, 5), (3, 6), (4, 7)$, and Figures 6–8 show the comparisons of running time between three computation approaches under different threshold respectively. From the comparison we can see that the computation in $GF(65537)$ is capable of saving half running time for secret reconstruction from computation in $GF(257)$ and also reducing the share size. Although the problem of share size expansion can be also solved by the computation in $GF(2^{8})$, the running time in $GF(2^{8})$ is much longer than the computations in $GF(257)$ and $GF(65537)$.

Table 2.  Running times for secret reconstruction using three approaches.

Threshold		$(2, 5)$			$(3, 6)$			$(4, 7)$
Approach		$GF(257)$	$GF(65537)$	$GF(2^{8})$	$GF(257)$	$GF(65537)$	$GF(2^{8})$	$GF(257)$	$GF(65537)$	$GF(2^{8})$
Size	$100$	$0.58$	$0.34$	$5.46$	$0.59$	$0.29$	$3.78$	$0.63$	$0.33$	$3.42$
	$200$	$1.15$	$0.64$	$11.01$	$1.15$	$0.62$	$8.01$	$1.27$	$0.66$	$7.05$
	$300$	$1.86$	$1.02$	$16.97$	$1.88$	$0.62$	$11.84$	$1.88$	$0.65$	$9.05$
	$400$	$2.13$	$1.18$	$17.71$	$2.06$	$1.09$	$13.20$	$2.29$	$1.14$	$12.08$
	$500$	$2.68$	$1.46$	$21.82$	$2.46$	$1.23$	$16.39$	$2.76$	$1.46$	$14.30$
	$600$	$3.47$	$1.82$	$27.11$	$3.27$	$1.66$	$22.30$	$3.58$	$1.82$	$20.01$
	$700$	$3.99$	$2.35$	$36.58$	$3.92$	$2.09$	$26.49$	$4.79$	$2.21$	$24.48$
	$800$	$4.58$	$2.54$	$42.72$	$4.43$	$2.26$	$30.44$	$4.89$	$2.52$	$26.90$
	$900$	$5.21$	$2.78$	$46.94$	$4.93$	$2.48$	$34.12$	$5.36$	$2.86$	$30.20$
	$1000$	$5.80$	$3.10$	$54.24$	$5.33$	$2.80$	$33.33$	$6.19$	$3.20$	$34.40$

---

 | Show Table

DownLoad: CSV

Figure 6.  Running time for $(2, 5)$ threshold secret reconstruction using three approaches.

DownLoad: Full-Size Img PowerPoint

Figure 7.  Running time for $(3, 6)$ threshold secret reconstruction using three approaches.

DownLoad: Full-Size Img PowerPoint

Figure 8.  Running time for $(4, 7)$ threshold secret reconstruction using three approaches.

DownLoad: Full-Size Img PowerPoint

5.   Conclusion

This paper proposes a new secret sharing based secret document protection scheme, which is capable of reducing share size and saving running time from Tu-Hsu's scheme. In Tu-Hsu's scheme, all inner codes of a secret document are encrypted single-byte wisely, and the shares are computed through Shamir's $(k, n)$ secret sharing in $GF(257)$. When the share in Tu-Hsu's scheme equals to $255$ or $256$, the share size is expanded from one byte to two bytes. On the contrary, our scheme combines each two inner codes of secret document in Tu-Hsu' scheme into one double-bytes inner code, and the shares are generated from these double-bytes inner codes through Shamir's $(k, n)$ secret sharing in $GF(65537)$. The share size would expand only when it equals to $65535$ or $65536$, which has much smaller probability of share size expansion than Tu-Hsu's scheme. Thus, our scheme can reduce share size from Tu-Hsu's scheme. On the other hand, by combining each two inner codes into one double-bytes inner code, our scheme has half computational complexity to Tu-Hsu's scheme, and the experimental results can also prove that our scheme saves almost half running time from Tu-Hsu's scheme.

Acknowledgement

This work was supported by National Natural Science Foundation of China under Grant No. 61502384, 61571360, 61872289; This research was supported in part by Ministry of Science and Technology (MOST), under Grant 107-2221-E-259-007.

Conflict of interest

The authors declare that they have no conflict of interest.