EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 3, 2024, 1751-1761 ISSN 1307-5543 – ejpam.com Published by New York Business Global Threshold Changeable Secret Sharing (TCSS) via Skew Polynomials Angga Wijaya1,3,∗, Intan Muchtadi Alamsyah2, Aleams Barra2 1 Doctoral Program of Mathematics, Faculty Mathematics and Natural Sciences, Institut Teknologi Bandung, Jl. Ganesha No. 10, 40132 Bandung, Indonesia 2 Algebra Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jl. Ganesha No. 10, 40132 Bandung, Indonesia 3 Department of Informatics Engineering, Faculty of Industrial Technology, Institut Teknologi Sumatera, Jl. Terusan Ryacudu, 36365 South of Lampung, Indonesia Abstract. Secret sharing is a tool to divide a secret into multiple shares, so that to reconstruct the secret, it is necessary to collect several shares under certain conditions. Secret sharing was first introduced by Adi Shamir, the scheme is based on polynomials. The secret is represented as a constant value polynomial, and the points on the polynomial graph serve as shares. Secret reconstruction is performed through Lagrange interpolation at a minimum of k out of n points, known as a threshold scheme (k, n). In 2010, Zhang Y. designed a secret sharing scheme through skew polynomials. Involving the role of the automorphism σ in the skew polynomial ring increase the complexity in share distribution and secret reconstruction. In 2012, Zhang Z. designed a secret sharing scheme with a threshold that can change according to the participants present during the reconstruction process, known as Threshold Changeable Secret Sharing (TCSS). This aims to prevent external parties from pretending to be valid participants in order to learn the secret. In this research, a TCSS scheme will be designed using skew polynomials. The aim is to make the TCSS scheme’s calculations more complex, making it harder for adversaries to access the secret. 2020 Mathematics Subject Classifications: 94A62, 12E10 Key Words and Phrases: Secret sharing, threshold changeable secret sharing, skew polynomials 1. Introduction Initially proposed by Shamir [13] as a threshold scheme utilizing polynomials and later by Blakley [1] as a scheme involving geometric hyperplanes, the concept of secret sharing plays a pivotal role in safeguarding information among individuals or participants in a group who may not fully trust each other. The fundamental notion is to partition a secret into multiple shares in a manner that ensures no single share holds any information about ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i3.5262 Email addresses: angga.wijaya@if.itera.ac.id (A. Wijaya), ntan@itb.ac.id (I. Muchtadi Alamsyah), barra@itb.ac.id (A. Barra) https://www.ejpam.com 1751 © 2024 EJPAM All rights reserved. A. Wijaya, I. Muchtadi Alamsyah, A. Barra / Eur. J. Pure Appl. Math, 17 (3) (2024), 1751-1761 1752 the original secret. This arrangement enables a collective group of participants who meet specific conditions to access and disclose the original secret. The applications of secret sharing span various domains, encompassing key management [6], multiparty computation [12][4], digital signature protocols [2], and more. The (k, n) threshold scheme indicates that to reconstruct the secret, a minimum of k participants out of a total of n participants must collaborate by combining their shares. Consequently, secret sharing schemes involve two primary stages: share generation and secret reconstruction. Share generation is conducted by a trusted dealer. During the secret reconstruction phase, only a subset of participants with valid shares, comprising at least k individuals from the total n participants, is capable of executing the reconstruction process. The issue arises when there are more than k participants gathered, but among them, there is a minimum of k valid participants, and at least one of the remaining ones acts as an adversary, pretending to be a valid participant. Of course, the adversary doesn’t possess valid shares. However, with a threshold scheme (k, n), under such conditions, it is still possible to reconstruct the secret. This poses a risk as it allows adversaries who should not have access to the secret to gain knowledge they are not entitled to. Hence, the idea of a changeable threshold secret sharing (TCSS) emerged, as introduced by Martin [8] and further discussed by Meng [9]. Initially, the threshold is set as k by the dealer, but during secret reconstruction, it can be changed to k′ with k′ > k. In this scenario, each participant should have a share corresponding to the number of participants involved in the reconstruction at that time. Moreover, advancements in secret sharing research were made by Zhang [15] and John- son [7], who introduced the threshold secret sharing scheme (k, n) based on skew polyno- mials. The concept of skew polynomials was previously introduced by Noether [10] and Ore [11]. The skew polynomial ring, denoted as R[x, σ], is defined, with R taking the form of a field, and σ representing an automorphism on R. The utilization of skew polynomials in polynomial evaluation and Lagrange interpolation introduces complexity due to the involvement of the automorphism function σ, as outlined by Eric [3] in the methodology for performing interpolation using skew polynomials. Consequently, the secret sharing scheme becomes more intricate. In this research, the original Threshold Changeable Secret Sharing (TCSS) scheme is implemented using skew polynomials. Consequently, this process experiences an increase in computational time, making it more time-consuming for adversaries to reconstruct the secret. 2. Preliminaries The following are definitions, basic theories and theorems from previous research. Definition 1. [14](Secret-Sharing Scheme) Let S be a set of secrets, where |S| ≥ 2. A secret sharing scheme Π on U = {u1, ..., un} with domain of secrets S is a mapping from S to a set of n-tuples Πn i=1Si, where Si is called the share domain of ui. A. Wijaya, I. Muchtadi Alamsyah, A. Barra / Eur. J. Pure Appl. Math, 17 (3) (2024), 1751-1761 1753 Definition 2. [5](Skew Polynomials Ring) Let R be a field, σ is a ring automorphism on R. R[x, σ] is skew polynomial ring with usual polynomial addition and left scalar multiplication. For right scalar multiplication : x · a = σ(a) · x for all a ∈ R Definition 3. [15](Skew Polynomial Ring - Evaluation) Let R[x, σ] skew polynomial ring, f(x) ∈ R[x, σ], and any a ∈ R. Define the set {Nn : R → R | n ≥ 0} recursively for all a ∈ R, N0(a) = 1 and Nn+1(a) = σ(Nn(a))a. Based on remainder theorem : f(x) = q(x)(x− a) + r with r ∈ R, the right remainder of f(x) by (x− a) is r = ΣaiNi(a). So the evaluation of f(x) on a : f(a) = r = ΣaiNi(a) Theorem 1. [3] Let ∆ = {x1, x2, ..., xn} and xi ∈ R, where R is division ring. Then (i) There exist nonzero polynomial f ∈ R[x, σ] such that f(xi) = 0. (ii) The set I of polynomials vanishing on ∆ form a left ideal in R[x, σ]. (iii) If f∆ is monic polynomial of the smallest degree in I, then I = R[x, σ]f∆ where f∆ is called minimal polynomial of ∆. Procedure to find minimal polynomial of {x1, x2, ..., xn}: (i) Let ∆ = {x1, x2} (ii) The polynomial vanishing on ∆ is : f{x1,x2}(x) = (x− σ(x2 − x1)x2(x2 − x1) −1)(x− x1) (iii) By recursively for ∆ = {x1, x2, ..., xn}, the polynomial vanishing on ∆ is : f{x1,x2,...,xn}(x) = (x− σ(f{x1,x2,...,xn−1}(xn))xn(f{x1,x2,...,xn−1}(xn)) −1)(f{x1,x2,...,xn−1}(x)) Theorem 2. [3] Let ∆ = {x1, x2, ..., xn} and xi ∈ R where R is a division ring. For any y1, y2, ..., yn ∈ K there exist a unique polynomial f ∈ R such that f(xi) = yi and deg f ≤ n− 1 if and only if deg f∆ = n where f∆ is the minimal polynomial of the set ∆. The Interpolation Polynomial of set ∆ : f(x) = n∑ i=0 yi · Li(xi) −1 · Li(x) where Li(x) is minimal monic polynomial such that Li(xj) = 0 for i ̸= j. A. Wijaya, I. Muchtadi Alamsyah, A. Barra / Eur. J. Pure Appl. Math, 17 (3) (2024), 1751-1761 1754 3. Main Result The outcome of this study is a secret sharing scheme outlined in three stages: setup, share generation, and secret reconstruction. Subsequently, there is a subsequent examina- tion of the algorithmic complexity within the devised scheme. 3.1. Setup In this stage, the dealer determines the total number of participants, denoted as n, and the initial threshold value required for secret reconstruction, denoted as k. The skew polynomial structure R[x, σ] is also defined, with the restriction that R is a field, and σ is an automorphism on R. The dealer then selects the secret s, represented by an element in R, in other words, s is an element of R. 3.2. Share Generation Phase (i) Dealer set polynomials : ft(x) = s+ at,1x+ at,2x 2 + ...+ at,k−1x k−1 with s = secret, t ∈ {k, k + 1, . . . , n}, at,j ∈ R for j ∈ {1, . . . , t− 1} and at,t−1 ̸= 0. (ii) Dealer choose X = {xi} with xi ∈ R for i ∈ {1, . . . , n} and satisfy X is σ-pairwise distinct which mean for i ̸= j, xi and xj is not σ-conjugate, that is for all c ∈ R, xi ̸= σ(c)xjc −1 (iii) Evaluate value xi on polynomials ft(x) for all i ∈ {1, . . . , n} and t ∈ {k, k+1, . . . , n} using skew polynomials evaluation method. ft(xi) = s+ t−1∑ u=1 at,uNu(xi) with N0(xi) = 0 and Nv+1(xi) = σ(Nv(xi))xi for v ≥ 0. (iv) Set the share for participant i is (xi, ft(xi)) for all t ∈ {k, k + 1, . . . , n}. So each participants has n− k + 1 shares which will be used to reconstruct the secret based on corresponding the value of threshold t (number of collected participants). (v) Dealer send the corresponding share (xi, y(t,i)) = (xi, ft(xi)) to each participants privately. 3.3. Secret Reconstruction Phase (i) The collected participants have information about R, σ, n, k and t. (ii) Initial threshold is k, since the number of collected participant t ≤ k. If the number of collected participant t > k, the threshold change from k to t. A. Wijaya, I. Muchtadi Alamsyah, A. Barra / Eur. J. Pure Appl. Math, 17 (3) (2024), 1751-1761 1755 (iii) Participants collect their share (xi, y(t,i)) corresponding the value of current thresh- old, assume t is current threshold. (iv) Participants interpolate the collected shares (xi, y(t,i)) by skew polynomials Lagrange interpolation method. ft(x) = t∑ i=1 y(t,i)(Li(xi) −1Li(x)) with Li(x) is monic minimal polynomial such that Li(xj) = 0 for i ̸= j. (v) Evaluate ft(0) = s as the secret. 3.4. Example Let a dealer and set of participant = {p1, p2, p3}. Number of participants = n = 3. Dealer determine initial threshold k = 2 and secret = s = 5 + 5i ∈ C. Dealer construct initial polynomial for k = 2: f2(x) = (5 + 5i) + (1− i)x Dealer determine xi value for participant share : x1 = 1 + i, x2 = 1 + 2i, x3 = 1 + 3i Evaluate xi value on f2(x) using skew polynomials evaluation method: f2(1 + i) = (5 + 5i)N0(1 + i) + (1− i)N1(1 + i) = (5 + 5i) · 1 + (1− i)σ(N0(1 + i)) · (1 + i) = (5 + 5i) + (1− i)(1 + i) = 7 + 5i, f2(1 + 2i) = (5 + 5i)N0(1 + 2i) + (1− i)N1(1 + 2i) = (5 + 5i) · 1 + (1− i)σ(N0(1 + 2i)) · (1 + 2i) = (5 + 5i) + (1− i)(1 + 2i) = 8 + 6i, f2(1 + 3i) = (5 + 5i)N0(1 + 3i) + (1− i)N1(1 + 3i) = (5 + 5i) · 1 + (1− i)σ(N0(1 + 3i)) · (1 + 3i) = (5 + 5i) + (1− i)(1 + 3i) = 9 + 7i. Dealer construct polynomial for k = 3: f3(x) = (5 + 5i) + (1− 2i)x+ (2− i)x2 A. Wijaya, I. Muchtadi Alamsyah, A. Barra / Eur. J. Pure Appl. Math, 17 (3) (2024), 1751-1761 1756 Evaluate xi value on f3(x) using skew polynomials evaluation method: f3(1 + i) = (5 + 5i)N0(1 + i) + (1− 2i)N1(1 + i) + (2− i)N2(1 + i) = 10 + 4i, f3(1 + 2i) = (5 + 5i)N0(1 + 2i) + (1− 2i)N1(1 + 2i) + (2− i)N2(1 + 2i) = 20, f3(1 + 3i) = (5 + 5i)N0(1 + 3i) + (1− 2i)N1(1 + 3i) + (2− i)N2(1 + 3i) = 32− 4i. Initial share for participant: (1 + i, 7 + 5i), (1 + 2i, 8 + 6i), (1 + 3i, 9 + 7i) Participant share when there are 3 collected participants: (1 + i, 10 + 4i), (1 + 2i, 20), (1 + 3i, 32− 4i) That is the end of share generation phase. Next step is secret reconstruction phase. For example, there are 3 participants with their own collected share: p1 : (1 + i, 7 + 5i), (1 + i, 10 + 4i) p2 : (1 + 2i, 8 + 6i), (1 + 2i, 20) p3 : (1 + 3i, 9 + 7i), (1 + 3i, 32− 4i) The initial threshold is k = 2. Because three participant are collected, the threshold changes to k = 3. Reconstruct secret using skew polynomials Lagrange interpolation: f3(x) = 3∑ j=1 yjLj(xj) −1Lj(x) Assume: x1 = 1 + i, x2 = 1 + 2i, x3 = 1 + 3i Then, L1(x) = (x− σ(x3 − x2)x3(x3 − x2) −1)(x− x2) = (x+ (1 + 3i))(x− (1 + 2i)), L2(x) = (x− σ(x3 − x1)x3(x3 − x1) −1)(x− x1) = (x+ (1 + 3i))(x− (1 + i)), A. Wijaya, I. Muchtadi Alamsyah, A. Barra / Eur. J. Pure Appl. Math, 17 (3) (2024), 1751-1761 1757 L3(x) = (x− σ(x2 − x1)x2(x2 − x1) −1)(x− x1) = (x+ (1 + 2i))(x− (1 + i)) Reconstruct f3(x) using skew polynomials Lagrange interpolation: f3(x) = (10 + 4i)(L1(1 + i))−1L1(x) + (20)(L2(1 + 2i))−1L2(x) + (32− 4i)(L3(1 + 3i))−1L3(x) Evaluate 0 on f3(x) to get the secret, s = f3(0) = (5 + 5i). 3.5. Algorithm Complexity In this stage, a complexity comparison will be carried out between the TCSS scheme algorithm using regular polynomials and using skew polynomials. The following are the steps which are considered to determine complexity. Share Generation Phase : (i) Determining set of X = {xi} for all i ∈ {1, . . . , n}. (ii) Evaluation ft(xi) for each participant i for all t ∈ {k, k + 1, . . . , n}. Secret reconstruction phase : interpolation polynomial ft(x). 3.5.1. TCSS via regular polynomials In share generation phase, the requirement to determine set of X = {xi} is only pairwise distinct, with i ∈ {1, ..., n}. Which mean after select a value of xi, next value is not allowed equal to all previous value. So the number of comparison steps: T (n) = 1 + 2 + · · ·+ (n− 1) = 1 2 (n− 1)n = 1 2 n2 − 1 2 n The complexity is O(n2). For evaluation ft(xi), the number of arithmetic operations: T (n) = n · n∑ t=k (t− 1) + t∑ j=1 (1 + (j − 1))  = n · n∑ t=k ( (t− 1) + 1 2 t(t+ 1) ) = n · n∑ t=k ( 1 2 t2 + 3 2 t− 1 ) A. Wijaya, I. Muchtadi Alamsyah, A. Barra / Eur. J. Pure Appl. Math, 17 (3) (2024), 1751-1761 1758 For the worst case, assume the minimum k = 1. T (n) = n · n∑ t=1 ( 1 2 t2 + 3 2 t− 1 ) = n · ( 1 2 n∑ t=1 t2 + 3 2 n∑ t=1 t− n∑ t=1 1 ) = n · ( 1 2 ( 1 6 n(n+ 1)(2n+ 1) ) + 3 2 ( 1 2 n(n+ 1) ) − n ) The complexity is O(n4). The total complexity of share generation for the case of a regular polynomial is O(n2)+ O(n4) = O(n4). In the secret reconstruction phase, for interpolation polynomial ft(x). The Lagrange formula: ft(x) = t∑ i=1 y(t,i) t∏ j=1,j ̸=i (x− xj) (xi − xj)  For the worst case, the maximum t = n. Number of arithmetic operations: T (n) = (n− 1) · (1 + (n− 1) · 2) The complexity is O(n2). 3.5.2. TCSS via skew polynomials In share generation phase, the requirement to determine set of X = {xi} is σ-pairwise distinct, with i ∈ {1, ..., n}. Which mean after select a value of xi, next value is not allowed equal to all previous value or the σ-conjugate of all previous value. So the number of comparison steps: T (n) = 2 + 4 + . . .+ 2(n− 1) = (n− 1)n = n2 − n The complexity is O(n2). For evaluation ft(xi), the formula: ft(xi) = s+ t−1∑ u=1 at,uNu(xi) with N0(xi) = 0 and Nv+1(xi) = σ(Nv(xi))xi for v ≥ 0. Number of arithmetic operations: T (n) = n · n∑ t=k (t− 1) + t∑ j=1 (1 + 2j)  A. Wijaya, I. Muchtadi Alamsyah, A. Barra / Eur. J. Pure Appl. Math, 17 (3) (2024), 1751-1761 1759 = n · n∑ t=k ( (t− 1) + t+ 1 2 t(t+ 1) ) = n · n∑ t=k ( 1 2 t2 + 5 2 t− 1 ) T (n) = n · n∑ t=1 ( 1 2 t2 + 5 2 t− 1 ) = n · ( 1 2 n∑ t=1 t2 + 5 2 n∑ t=1 t− n∑ t=1 1 ) = n · ( 1 2 ( 1 6 n(n+ 1)(2n+ 1) ) + 5 2 ( 1 2 n(n+ 1) ) − n ) The complexity is O(n4). The total complexity of share generation for case regular polynomial is O(n2)+O(n4) = O(n4). In the secret reconstruction phase, for interpolation polynomial ft(x). The Skew La- grange formula: ft(x) = t∑ i=1 y(t,i) (Li(xi)) −1 Li(x) with Li(x) is the monic minimal polynomial such that Li(xj) = 0 for i ̸= j. First, determine the number of operation for finding Li(x). For the worst case the maximum t = n. Assume the number of operation for finding Li(x) that vanish 2 elements in ∆ is a constant value z. By adding 1 element in ∆, the total operation for finding Li(x) is added by evaluation of new element on previous generated function. Based on evaluation of skew polynomials, the number operation of finding Li(x): T (n) = z + n∑ i=3 z + αi2 + βi+ γ For some constants α, β, and γ. Then, T (n) = c3n 3 + c2n 2 + c1n+ c0 For some constants c0, c1, c2, and c3. Assume the number of operation for evaluation xi on Li(x) is d2n 2 + d1n+ d0. Number of arithmetic operations in skew Lagrange interpolation: T (n) = (n− 1)(c3n 3 + c2n 2 + c1n+ c0 + d2n 2 + d1n+ d0 + 3) REFERENCES 1760 The complexity is O(n4). Based on the complexity analysis of the algorithm, it is found that the algorithmic complexity during the share generation phase is the same for both secret sharing schemes, whether using regular polynomials or skew polynomials the algorithm complexity = O(n4). However, in the secret reconstruction phase, there is an increase in algorithmic complexity in the scheme using skew polynomials compared to using regular polynomials, rising from O(n2) to O(n4). 4. Conclusion Threshold Changeable Secret Sharing (TCSS) can be performed via skew polynomials. Comparison with the regular polynomial, the algorithm complexity remains stable during share generating phase but it has increasing significant during secret reconstruction phase. This provides an advantage in preventing adversaries from easily reconstructing the secret but it doesn’t quite affect to dealer for generating shares. Acknowledgements This work was funded by the Research and Community Service Program of the In- donesian Ministry of Education, Culture, Research and Technology 2023. The author also expresses gratitude to Institut Teknologi Sumatera for funding the author’s doctoral studies during the completion of this research. References [1] G.R. Blakley. Safeguarding cryptographic keys. In Proc. AFIPS NCC, volume 48, pages 313–317, 1979. [2] F. Ding, Y. Long, and P. Wu. Study on secret sharing for sm2 digital signature and its application. In 2018 14th International Conference on Computational Intelligence and Security (CIS), pages 205–209, 2018. [3] A.L. Erić. Polynomial interpolation problem for skew polynomials. Applicable Anal- ysis and Discrete Mathematics, pages 403–414, 2007. [4] D. Escudero. An introduction to secret-sharing-based secure multiparty computation. Cryptology ePrint Archive, 2022. [5] H. Gluesing-Luerssen. Skew-polynomial rings and skew-cyclic codes. arXiv preprint arXiv:1902.03516, 2019. [6] G. Hanaoka. A hierarchical non-interactive key-sharing scheme with low memory size and high resistance against collusion attacks. The Computer Journal, 45:293–303, 2002. REFERENCES 1761 [7] D. Johnson. Secret sharing schemes and noncommutative polynomial interpolation. University of Manitoba, Canada, 2018. [8] K. M. Martin, J. Pieprzyk, R. Safavi-naini, and H. Wang. Changing thresholds in the absence of secure channels. In Australas. Conf. Inf. Secur. Privacy, Springer, volume 095, pages 177–178, 1999. [9] K. Meng, F. Miao, W. Huang, and Y. Xiong. Threshold changeable secret sharing with secure secret reconstruction. Information Processing Letters, 157:105928, 2020. [10] E. Noether and W. Schmeidler. Moduln in nichtkommutativen bereichen, insbeson- dere aus differential-und differenzenausdrücken. Mathematische Zeitschrift, 8:1–35, 1920. [11] O. Ore. Theory of non-commutative polynomials. Annals of mathematics, pages 480–508, 1933. [12] K. Patel. Secure multiparty computation using secret sharing. In 2016 Interna- tional Conference on Signal Processing, Communication, Power and Embedded Sys- tem (SCOPES), pages 863–866, 2016. [13] A. Shamir. How to share a secret. Comm. ACM, 22:612–613, 1979. [14] T. Tassa and N. Dyn. Multipartite secret sharing by bivariate interpolation. Journal of Cryptology, 22:227–258, 2009. [15] Y. Zhang. A secret sharing scheme via skew polynomials. In 2010 International Conference on Computational Science and Its Applications, pages 33–38, 2010.