EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 11, No. 2, 2018, 410-416 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global Secret sharing schemes based on extension fields Selda Çalkavur Department of Mathematics, Kocaeli University, Kocaeli, Turkey Abstract. A (t, n)−secret sharing scheme is a method of distribution of information among n participants such that t > 1 can reconstruct the secret but t − 1 cannot. There is numerous research about secret sharing schemes. However there is little research on secret sharing schemes based on extension fields. In this paper, we study secret sharing schemes based on extension fields over finite fields. We use two methods to recover the secret. We define the access structure and the accessibility degree for these secret sharing schemes. We also describe our theorems, definitions and a corollary. 2010 Mathematics Subject Classifications: 12F05, 94A62 Key Words and Phrases: Extension fields, secret sharing, secret sharing schemes 1. Introduction Secret sharing has been a subject of study for over 30 years. A secret sharing scheme is a way of distributing a secret among a finite set of people such that only some distinguished subsets of these subsets can recover the secret. The collection of these special subsets is called the access structure of the scheme. Secret sharing schemes were constructed by Shamir [11] and Blakley [1] in 1979. Shamir scheme was based on polynomial interpolation but was later shown by Mc Eliece and Sar- wate to be an application of Massey scheme [8], a scheme based on codes, to Reed Solomon codes [9]. Massey [8] used linear codes for secret sharing and explored the relationship between the access structure and the minimal codewords of the dual code of the underlying code in 1993. Several authors has been studied on secret sharing schemes [3], [4], [7], [8]. Secret sharing schemes were applied to various fields such as cloud computing, con- trolling, nuclear weapons in military, recovering information from multiple servers, and controlling access in banking system [5]. Another secret sharing system is the (t, n)-threshold system [10]. A (t, n)-threshold scheme is a method of distribution of information among n participants such that t > 1 participants can reconstruct the secret but t− 1 cannot. Email address: selda.calkavur@kocaeli.edu.tr (S. Çalkavur) http://www.ejpam.com 410 c© 2018 EJPAM All rights reserved. S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 410-416 411 In this work, we present a (t, n)-threshold scheme based on extension fields over finite fields. The material is organized as follows. Section II contains some algebraic background. Section III describes the schemes and analyses their security. We also determine the access structure of these secret sharing schemes and prove its properties. Section IV collects concluding remarks. 2. Algebraic preliminaries 2.1. Roots of irreducible polynomials In this section, we remind some information about the set of roots of an irreducible polynomial over a finite field. Lemma 1. Let f ∈ Fq[x] be an irreducible polynomial over a finite field Fq and α be a root of f in extension field of Fq. Then for a polynomial h ∈ Fq[x] we have h(α)=0 if and only if f divides h [6]. Lemma 2. Let f ∈ Fq[x] be an irreducible polynomial over Fq of degree m. Then f(x) divides xq n − x if and only if f divides h [6]. Theorem 1. If f is an irreducible polynomial in Fq[x] of degree m, then f has a root α in Fqm. Furthermore, all the roots of f are simple and are given by the m distinct elements α, αq, αq2 , ..., αqm−1 of Fqm [6]. Corollary 1. Let f be an irreducible polynomial in Fq[x] of degree m. Then the splitting field of f over Fq is given by Fqm [6]. Definition 1. Let Fqm be an extension of Fq and let α ∈ Fqm . Then the elements α, αq, αq2 , ..., αqm−1 are called the conjugates of α with respect to Fq [6]. The conjugates of α ∈ Fqm with respect to Fq are distinct if and only if minimal polynomial of α over Fq has degree m. Otherwise, the degree d of this polynomial is a proper divisor of m and then the conjugates of α with respect to Fq are the distinct elements α, αq, αq2 , ..., αqd−1 each repeated m/d times. Theorem 2. The conjugates of α ∈ Fq∗ with respect to any subfield of Fq have the same order in the group Fq∗, where Fq∗ is a cyclic group of nonzero elements of which consists of nonzero elements of Fq [6]. Corollary 2. If α is a primitive element of Fq, then so are all its conjugates with respect to any subfield of Fq [6]. 2.2. Traces and norms In this part, we consider the viewpoint of regarding a finite extension F = Fqm of the finite field K = Fq as a vector space over K. S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 410-416 412 Definition 2. For α ∈ F = Fqm and K = Fq, the trace TrF/K (α) of α over K is defined by TrF/K (α) = α+ αq + αq2 + ...+ αqm−1 . If K is the prime subfield of F , then TrF/K (α) is called the absolute trace of α and simply denoted by TrF (α) [6]. Definition of the trace may be obtained as follows. Let f ∈ K[x] be the minimal polynomial of α over K and its degree d is a divisor of m. Then g(x) = f(x)m/d ∈ K[x] is called the characteristic polynomial of α over K. By Theorem 1, the roots of f in F are given by α, αq, αq2 , ..., αqd−1 and by Definition 1, the roots of g in F are precisely the conjugates of α with respect to K. Hence g(x) = xm + am−1x m−1 + ...+ a0 = (x− α).(x− αq)...(x− αqm−1 ) (1) and a comparison of coefficients shows that TrF/K (α) = −am−1. (2) TrF/K (α) is always an element of K [6]. Definition 3. For α ∈ F = Fqm and K = Fq, the norm NF/K(α) of α over K is defined by NF/K(α) = α.αq.αq2 .....αqm−1 = αqm−1/(q − 1). Moreover, by comparing the constant terms in (1), it can be written the following equation: NF/K(α) = (−1)m.a0. NF/K(α) is also an element of K [6]. The number of distinct bases of F over K is too large, but there are two special types of bases . The first base is a polynomial basis {1, α, α2, ..., αm−1}, made up of the powers of a defining element α of F over K, where α is taken to be a primitive element of F . Another type of basis is a normal basis. Definition 4. Let K = Fq and F = Fqm . Then a basis of F over K of the form {α, αq, αq2 , ..., αqm−1}, consisting of a suitable element α ∈ F and its conjugates with respect to K, is called a normal basis of F over K [6]. 2.3. Secret sharing schemes In this section we should think about a case of some malicious behaviors lying among participants which are called cheaters. They modify their shares in order to cheat. If a group of participants can recover the secret by combining their shares, then any group of participants containing this group can also recover the secret. Definition 5. An access group is a subset of a set of participants that can recover the secret from its shares. A collection Γ of access groups of participants is called an access S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 410-416 413 structure of the scheme. An element A ∈ Γ is called a minimal access element. Hence a set is a minimal access group if it can recover the secret but no proper subset can recover the secret. Let Γ̄ be the set of all minimal access elements. We call Γ̄ the minimal access structure [5]. Determining the minimal access structure is a hard problem [3]. Now let us consider the accessibility of an access structure of secret sharing scheme based on binary linear code. Let P = {P1, P2, ..., Pm} be a set of m participants and let Ap be the set of all access elements on P . Definition 6. The accessibility index on P is the map δp(Γ): Ap → R given by δp(Γ) = |Γ| 2m for Γ ∈ Ap, where m = |P |. The number δp(Γ) will be called the accessibility degree of structure Γ [2]. 3. The Schemes In this section, we present the new (t, n)− threshold schemes that combine of Shamir scheme with our schemes. 3.1. First scheme Let Fq be the secret space and Fqm be the sharing space. We consider a finite extension of Fqm of the finite field Fq as a vector space over Fq, where m is the dimensional of Fqm over Fq. Assume a characteristic polynomial g(x) of α, where α ∈ Fqm and the degree of g(x) is m such that g(x) = xm + am−1x m−1 + ...+ a0. • Let all of elements of Fqm , except 0, be the participants. • The dealer pics the element −am−1 ∈ Fq as the secret and distributes to m elements of Fqm which are α, αq, αq2 , ..., αqm−1 . We know that these elements are also the normal basis elements of Fqm and uniquely determined and each element of Fqm can be written as the linear combination of basis elements. These m participants recover the secret while pooling their shares. In the first scheme, we need the trace function of α to recover the secret. TrF/K (α) = α+ αq + αq2 + ...+ αqm−1 . We also know that TrF/K (α) is also equal to −am−1, where −am−1 is the coefficient of xm−1 for the characteristic polynomial g(x). So α, αq, αq2 , ..., αqm−1 elements can reach the secret together. S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 410-416 414 3.2. Second scheme Now we construct another scheme using the norm function. In this scheme the dealer pics the element (−1)m.a0 ∈ Fq as the secret and distributes to the m elements of Fqm which are α, αq, αq2 , ..., αqm−1 . These m participants recover the secret while combining their shares as follows. NF/K(α) = α.αq.αq2 .....αqm−1 . We know that NF/K(α) is also equal to (−1)ma0. So α, αq, αq2 , ..., αqm−1 elements can reach the secret together. If m − h say, with 1 ≤ h < m, participants group together they can guess the secret with probability 1 h+1 ≤ 1 2 . Another possible attack would be to isolate elements of Fqm which are reached the secret. In our secret sharing schemes, only the conjugates of α with respect to Fq can recover the secret. These elements are also the normal basis elements which are uniquely determined. Theorem 3. In these secret sharing schemes based on extension fields we have the fol- lowing. i) The access structure consists of the m elements. ii) No element of number less than m can be used in recovering the secret. Proof. i) The secret is recovered thanks to the normal basis elements and their number is m. ii) These m elements are uniquely determined. So there is no element which has this property. The proof is clear. Corollary 3. With the above condition the extension field Fqm determines (m, qm − 1)−threshold scheme. Proof. It is clear that the number of non-zero elements of Fqm is qm − 1 and the number of normal basis elements is m. These m elements out of qm − 1 can reach the secret together. Definition 7. The access structure of these secret sharing schemes is given by Γ = {(αk, β)|k = 1, q, q2, ..., qm−1, β ∈ Fqm}. Theorem 4. The number of parties in these secret sharing schemes is qm − 1 and the access structure has the following properties: i) Only m elements can be used to recover the secret but (m− 1) cannot. ii) When the parties come together, up to [m2 ] cheaters can be found in each group. ( ”[x]” denotes the greatest integer less than or equal to x.) Proof. i) It is seen that by Definition 7. ii) By definition of our scheme is 2 ≤ m iff 1 ≤ m 2 . S. Çalkavur / Eur. J. Pure Appl. Math, 11 (2) (2018), 410-416 415 The accessibility degree of the access structure for these secret sharing schemes based on extension fields over finite fields can be defined as follows. Definition 8. The accessibility index on P is the map δp(Γ):Ap → R given by δp(Γ) = |Γ| qm − 1 , for Γ ∈ Ap, where m = |P | is the number of participants in the access structure. The number δp(Γ) will be called the accessibility degree of structure Γ. Example 1. Let F23 be the secret sharing space. This space is also m−dimensional vector space over F2. Consider the polynomial f(x) = x3 +x2 +1 ∈ F2[x]. The coefficients of polynomial are a0 = 1, a1 = 1, a2 = 1. So the secret is −a2 = −1 = 1 and m = 3, q = 2. The normal basis elements of Fqm are α, α2, α23−1 = α4. It is clear that α0 = 1, α1 = α, α2 = α2, α3 = α2 + 1, α4 = α3 + α = α2 + α+ 1, α5 = α3 + α2 + α = α+ 1, α6 = α2 + α, α7 = α3 + α2 = 1. All the sharings are K1 = (α0, 1), K2 = (α1, α), K3 = (α2, α2), K4 = (α3, α2 + 1), K5 = (α4, α2 + α+ 1), K6 = (α6, α2 + α), K7 = (α7, 1). K2,K3 and K5 participants recover the secret while combining their shares by using the trace function of α as follows. TrF/K (α) = α+ α2 + α4 = α+ α2 + (α2 + α+ 1) = 1. Now we assume that the secret is (−1)3.a0 = (−1).1 = −1 = 1 and the same partici- pants recover the secret calculating the norm of α as follows. NF/K(α) = α.α2.α2 = α3.α4 = (α2 + 1).(α2 + α+ 1) = 1. As it is seen that both of these schemes are the (3, 7)−threshold schemes. The acces- sibility degree of the access structure is 3 23−1 = 3 7 = 0, 42. 4. Conclusion In the present article we constructed some (t, n)−threshold schemes using the trace and norm functions. These schemes are mainly based on finite extensions over finite fields. REFERENCES 416 We introduced the access structure of these schemes. We defined the accessibility degree of the access structure. We obtained the new results. Possible attacks have been considered. Our scheme has the same distributed as Shamir’s scheme does. We send an element of Fq and the normal basis elements of Fqm use the trace and norm functions to recover the secret. The secret can be recovered only by the special participants which are uniquely deter- mined. This means the access structure of these schemes is very strong and reliable. References [1] Blakley, G.R., ”Safeguarding cryptographic keys”, American Federation of Informa- tion Processing Societies, National Computer Conference, pp. 313-317, (1979). [2] Carreras, F., Magana, A., Munuera, C., The accessibility of an access structure, RAIRO-Theoretical Informatics and Applications, 40.04, pp. 559-567. (2006). [3] Ding, C., Kohel, D. R., Ling, S., Secret-sharing with a class of ternary codes, Theo- retical Computer Science, 246(1), pp.285-298, (2000). [4] Dougherty, S. T., Mesnager, S., Solé, P., Secret sharing schemes based on self-dual codes, Information Theory Workshop (2008), ITW’08, IEEE (2008). [5] Kim. J.L., Lee, N., Secret sharing schemes based on additive codes over GF (4), Applicable Algebra in Engineering, Communication and Computing, pp. 1-19, (2016). [6] R. Lidl, H. Niederreiter, Finite Fields, vol. 20, Cambridge. [7] Li, Zhihui, Xue, Ting Xue, Lai, Hong, Secret sharing schemes from binary linear codes, Information Sciences 180(22), pp. 4412-4419, (2010). [8] Massey, J. L., Minimal codewords and secret sharing,“in Proc. 6th Joint Swedish- Russian Workshop on Information Theory, Mölle, Sweden, pp. 276-279, (1993). [9] McEliece R, J. and Sarwate D. V., On sharing secrets and Reed-Solomon codes, Common. Assoc. Comp. Mach., vol. 24, pp. 583-584, (1981). [10] Piepryzk, J. and Zhang, X. M., Ideal threshold schemes from MDS codes, Proceed- ings of Information Security and Cryptology ICISC 2002, Lecture Notes in Computer Science, vol. 2587, Springer-Verlag, Berlin, pp. 269-279, (2003). [11] Shamir, A., How to share a secret, Comm. of the ACM 22 pp. 612-613, (1979).