ISSN 2148-838X J. Algebra Comb. Discrete Appl. 9(3) • 175–184 Received: 4 July 2021 Accepted: 25 November 2021 Journal of Algebra Combinatorics Discrete Structures and Applications On Mignotte secret sharing schemes over Gaussian integers Research Article Diego Munera-Merayo Abstract: Secret Sharing Schemes (SSS) are methods for distributing a secret among a set of participants. One of the first Secret Sharing Schemes was proposed by M. Mignotte, based on the Chinese remainder theorem over the ring of integers. In this article we extend the Mignotte’s scheme to the ring of Gaussian Integers and study some of its properties. While doing this we aim to solve a gap in a previous construction of such extension. In addition we show that any access structure can be made through a SSS over Z[i]. 2010 MSC: 94A62, 13F07 Keywords: Secret sharing, Mignotte sharing scheme, Gaussian integer, Chinese remainder theorem 1. Introduction Secret sharing schemes (SSS’s) are methods for distributing a secret among a set of participants. Among their applications we may highlight key management, threshold and visual cryptography, e- voting, multiparty computation and more. Given the increasing importance of information security in today’s society, it is not surprising that SSS’s have become an active field of research within public key cryptography. In a SSS, a secret s is broken into n pieces or shares. Each share is given to one out of n participants. This shares are designed ensuring that some authorized coalitions of participants can reconstruct the secret by pooling the shares of its members, while non-authorized coalitions cannot do it. This family of authorized coalitions is called access structure of the scheme. The problem of secret sharing was firstly introduced by A. Shamir in [11]. In that article he also suggested a method to perform it: the so-called Shamir threshold secret sharing schemes, based on Lagrangian interpolation. Since the publication of Shamir’s work, several other methods have been proposed. For our purposes within this article, we may highlight the ones by M. Mignotte [9] and C. Diego Munera-Merayo; University of Valladolid (email:diego.munuera@alumnos.uva.es). 175 https://orcid.org/0000-0002-7735-6203 D. Munera-Merayo / J. Algebra Comb. Discrete Appl. 9(3) (2022) 175–184 Asmuth and J. Bloom [1], both based on the Chinese remainder theorem for coprime modules over the ring of integers Z. This three methods belong to the category of threshold (t,n) schemes. This means that their access structures are formed by all the coalitions with at least t out of n participants, for a certain t. On the other hand, the Chinese remainder theorem has many known applications in cryptography, [3]. It is based on a well known property of integers, the so-called Euclidean division: for any two integers n,m with m 6= 0, there exists integers q (quotient) and r (remainder) such that m = nq +r with 0 ≤ r < |m|. Of course, Euclidean division is not exclusive to Z. As there exist other rings that admit it, the called Euclidean Domains. Among these we may highlight the ring of univariate polynomials over a field K[X], and the ring of Gaussian Integers Z[i]. As a consequence a Chinese remainder theorem holds over both K[X] and Z[i], and therefore we can extend the Mignotte secret sharing scheme to these rings. In the literature we can find successive generalizations of Mignotte’s scheme. Firstly by S. Iftene to not necessarily coprime integers [7]. Later T. Galibus and G. Matveev [5] provided a version over polynomial rings of one variable. In that paper the authors also showed the remarkable property that any access structure can be realized by a Mignotte polynomial SSS. Finally, in [10] an extension of Mignotte threshold scheme to the ring of Gaussian Integers is proposed, and subsequently applied to the problem of image sharing.Recall that Gaussian Integers play a role in digital signal processing, cryptography, coding, and many other fields of science and technology, see [2]. And that Mignotte’s threshold scheme has already been proposed for image sharing, [13]. However, the extension of Mignotte SSS to Gaussian Integers proposed in [10] contains a crucial gap. Contrary to what occurs over Z and K[X], in the Euclidean division over Z[i], quotient and remainder are not unique. Thus, given v,z ∈ Z[i], the expression v (mod z) does not uniquely identify one element of Z[i]. This causes that the solution of a system of simultaneous congruence equations is not unique over Z[i] and, finally, that Mignotte’s scheme based on it may provide wrong recovered secrets. In this article we propose a new version of Mignotte’s SSS over Z[i] that works properly and inves- tigate some of its properties. The paper is organized as follows: in Section 2 we recall some basic facts on SSS’s and the arithmetic of Z[i]. The proposed scheme is developed in Section 3, where we also study its main properties. In particular, following [5] we show that any access structure can be realized by our scheme. Also we characterize those access structures which are obtained from coprime modules. Some examples are included in order to illustrate the obtained results. 2. Some background on SSS’s and Gaussian integers First, we recall some known facts about secret sharing schemes and Gaussian Integers. A complete study of most of this subjects can be found in [12] for secret sharing and [4] for Gaussian Integers. 2.1. Secret sharing schemes Let P = {1, . . . ,n} be a set of n participants and S be a finite and non-empty set of secrets. We want to share a secret s ∈S among the participants in P. For that purpose, each participant will receive a data si about the secret, which we will call its share. A dealer computes the s1, . . . ,sn from s and assigns si to each participant i. A secret sharing scheme is a method R of calculating the shares si so that certain groups of participants, previously determined, can recover s by pooling the shares of their members; while making it impossible for any other coalition of participants to recover the secret. We will call access structure of the scheme (denoted by A) to the family of all coalitions authorized to recover the secret. Note that this family is monotone increasing. We say that a scheme is perfect if unauthorized coalitions cannot deduce any information about the secret. Another important feature to take into account in a scheme R is the size of the shares distributed 176 D. Munera-Merayo / J. Algebra Comb. Discrete Appl. 9(3) (2022) 175–184 to the participants. Let us denote by Si the set of all possible values that si can take when s runs over S. It can be proved that when no unauthorized coalition can discard any element of S to be the shared secret, it holds that |Si| ≥ |S|. We define the information rate of R as ρ(R) = min { log |Si| log |S| : i = 1, . . . ,n } . If ρ(R) = 1 then the scheme R is called ideal. 2.2. The Chinese remainder theorem In its classical version, over the ring of integers, the Chinese remainder theorem states the following. Theorem 2.1. Let a1, . . . ,an ∈ Z, and let m1, . . . ,mn be relatively pairwise coprime integers such that m1, . . . ,mn ≥ 2. The system of simultaneous congruence equations x ≡ ai (mod mi), i = 1, . . . ,n has a unique solution modulo lcm(m1, . . . ,mn). Furthermore, this solution can be explicitly given as x = a1q1r1 + · · ·+ anqnrn. Where qi = m1 · · ·mn/mi and ri = q−1i in Z/miZ, for i = 1, . . . ,n. This theorem can be generalized, as the integers need not to be relatively pairwise coprime. In this case there exists a solution if and only if ai ≡ aj(mod lcm(mi,mj)) for all 1 ≤ i,j ≤ n. Furthermore, it can be stated over Euclidean rings, such as Gaussian Integers. 2.3. Mignotte SSS over Z The Mignotte’s original secret sharing scheme allows the construction of threshold (t,n) schemes over a set P = {1, . . . ,n} of n participants as follows [9]: Let m : m1 < m2 < · · · < mn, be a sequence of n pairwise relatively coprime integers such that mn−t+2 · · ·mn < m1 · · ·mt. The integer mi is assigned to participant i. Let us write m− = mn−t+2 · · ·mn, m+ = m1 · · ·mt and for a coalition C ⊆ P, let m(C) = ∏ i∈C mi. The above condition on the mi’s implies that m(C) ≤ m − when |C| < t and m(C) ≥ m+ when |C| ≥ t. The scheme operates as follows: Let S = {s ∈ Z : m− < s < m+} be the set of secrets to be shared. Given a secret s, the share of participant i is si = s (mod mi). An authorized coalition A with |A| ≥ t may recover the secret by solving the system (SA) x ≡ si (mod mi), i ∈ A whose solution x is unique modulo m(A) as guaranteed by the Chinese remainder theorem. Since s < m+ ≤ m(A), it holds that x = s. An unauthorized coalition B with |B| < t, may try to recover the secret by solving the system (SB) x ≡ si (mod mi), i ∈ B whose solution x is unique modulo m(B). But since x < m(B) ≤ m− ≤ s, it holds that x 6= s and so B does not recover the legitimate secret. 2.4. Extensions of Mignotte SSS In [7] Iftene suggested an extension of Mignotte SSS over the integers as follows. Let m : m1,m2, · · · ,mn, be a sequence of n (not necessarily coprime) integers. For a coalition C ⊆ P let us denote by lcm(C) the least common multiple of {mi : i ∈ C}. Take two integers m− < m+ such that the 177 D. Munera-Merayo / J. Algebra Comb. Discrete Appl. 9(3) (2022) 175–184 interval (m−,m+) does not contain the lcm(C) of any coalition C ⊆ P. Furthermore, we impose that π(m+−4m−) 4m− > 1. In this setting let us consider the family A = A(m,m+) = {A ⊆ P : lcm(A) ≥ m+}. This is a monotonous increasing family, so we may consider it as an access structure over P. The set of secrets is S = {s ∈ Z : m− ≤ s < m+}. Sharing and reconstruction of secrets is carried out as in the original Mignotte scheme. Another extension of Mignotte’s scheme to the ring of polynomials in one variable over a finite field, Fq[X], was given in [5]. Following this idea, other extensions of the method to Euclidean rings have been made, such as [10] or [13]. From now on we will focus on the extension to Gaussian Integers. 2.5. The ring of Gaussian integers A Gaussian Integer is a complex number z = a + bi, where both a and b are integers. The set of Gaussian Integers is thus Z[i]. Over this ring we may consider the Euclidean function norm of z, N(z) = a2 + b2 = zz (where z denotes the complex conjugated of z). Thus the norm is multiplicative, N(vz) = N(v)N(z) for all v,z ∈ Z[i] and satisfies N(v) ≤ N(vz) if z 6= 0. The most interesting arithmetic property of Z[i] is the existence of an Euclidean division with respect to the norm: given v,z ∈ Z[i] with z 6= 0, there exist q,r ∈ Z[i] such that v = zq + r with N(r) < N(z). We say that Z[i] is an Euclidean Domain. Thus Z[i] is also a Principal Ideal Domain [4], and therefore a Chinese remainder theorem similar to Theorem 2.1, holds over it. We observe, however, that the quotient and remainder of the Euclidean division are not uniquely determined, unlike what we have over Fq[X] or what we can do over Z, see [8]. For example we have 10i = (5 + 4i)(1 +i) + (i−1) = (5 + 4i)(1 + 2i) + (3−4i). Thus there is no a consistent way to define the expression v (mod z), as it does not uniquely identify any element. As a result, the solution of a system of congruence equations is not uniquely determined. 2.6. The Mignotte SSS over Z[i] of [10] In [10] the authors propose an extension of Mignotte’s scheme to a threshold (t,n) SSS over Z[i], and they use this extension to give a method for sharing secret images. However they did not take into account the lack of uniqueness of Euclidean division. This causes that the proposed SSS may lead to reconstruct the wrong secrets. The method goes as expected: In order to share a secret among a set P of n participants, we begin from a sequence m : m1, . . . ,mn of pairwise coprime Gaussian Integers such that N(m1) < · · · < N(mn) and N(mn−t+2 · · ·mn) < N(m1 · · ·mt). The set of secrets is S = {s ∈ Z[i] : N(mn−t+2 · · ·mn) ≤ N(s) < N(m1 · · ·mt)}. The sharing of a secret s ∈ S and its subsequent reconstruction are performed in the usual way: Given a secret s, the share of participant i is si = s (mod mi). A coalition A with |A| ≥ t, may recover the secret by solving the system (SA) x ≡ si (mod mi), i ∈ A. We will now show an example of how it operates and how it may lead to mistakes. Example 2.2. (Example 3.3 of [10]). Let n = 3, m : 7 + 4i,−3 − 13i,11 + 8i and take t = 2. The set of secrets is then S = {s ∈ Z[i] : 185 ≤ N(s) < 11570}. Let s = 70 − 70i. Note that N(s) = 9800 so s is a valid secret. The shares are s1 = 1 + 2i,s2 = 4,s3 = 3 − i. The authorized coalition {2,3} wants to recover the secret. To that end they solve the system{ x ≡ 4 (mod −3−13i) x ≡ 3− i (mod 11 + 8i) whose solution is x = 70−70i, but also x = −1 + 97i, and both are valid secrets. Most computer systems choose the solution of smaller norm. Since N(−1 + 97i) = 9410 < N(70 + 70i) = 9800, then the coalition {2,3} recovers s = −1 + 97i, which is a wrong secret. 178 D. Munera-Merayo / J. Algebra Comb. Discrete Appl. 9(3) (2022) 175–184 3. A Mignotte SSS over Gaussian integers We now aim to develop an extension of Mignotte SSS to Gaussian Integers, making sure that the remainders are uniquely determined. That is, to ensure that the expression v (mod z) refers to a unique element of Z[i]. On top of that, we will not impose the condition that the modules m1, · · · ,mn are coprime, so that we find more general schemes. 3.1. Fundamental domains In order to ensure the uniqueness of the remainder, we will operate in restrictions of Z[i]. Let z ∈ Z[i], z 6= 0.We may define the fundamental domain of z is the subset of C F(z) = {z(α + βi) : α,β ∈ R,−1 2 < α,β ≤ 1 2 }. Geometrically F(z) is a semi-open square in C ∼ R2, with vertices z(1 2 + 1 2 i), z(1 2 − 1 2 i), z(−1 2 − 1 2 i), z(−1 2 + 1 2 i). Figure 1. Fundamental domain of z. As seen in the above figure F(z) is centered at 0 and has side length |z| = √ N(z) . Note that for every Gaussian Integer v ∈F(z) it holds that N(v) ≤ N(z)/2. On this space, we find the following. Proposition 3.1. Given two Gaussian Integers v,z ∈ Z[i] with z 6= 0, there exists q,r ∈ Z[i] such that r ∈F(z) and v = zq + r. Moreover such q and r are unique and N(r) ≤ N(z)/2. Proof. Let us consider the complex number v/z = x + yi. Let a, b be the integers a = dx − 1 2 e and b = dy− 1 2 e. Thus −1 2 < x−a ≤ 1 2 , −1 2 < y−b ≤ 1 2 . Let q = a+bi. Then v = zq + (z(v/z−q)) = zq +r where r = z(v/z − q) = z((x−a) + (y − b)i) ∈F(z). To see the uniqueness, if zq1 + r1 = zq2 + r2 with r1,r2 ∈ F(z), then write r1 = z(α1 + β1i), r2 = z(α2 + β2i) with −12 < α1,β1,α2,β2 ≤ 1 2 . We have z(q2 −q1) = r1 −r2 = z((α1 −α2) + (β1 −β2)i), hence α1 −α2 and β1 −β2 are both integers. So α1 = α2 and β1 = β2. The last statement, N(r) ≤ N(z)/2, is a consequence of the fact that r ∈F(z). 179 D. Munera-Merayo / J. Algebra Comb. Discrete Appl. 9(3) (2022) 175–184 Given v,z ∈ Z[i] with z 6= 0 as above, we say that the unique remainder r ∈ F(z) of the division v = zq + r, is the principal value of v (mod z). We will write this as r = v (mod z). Let us note that the above proof gives a procedure to explicitly compute this number. Besides F(z) we shall also consider the strict fundamental domain of z, which is the set Fo(z) of points in F(z) but not on its border Fo(z) = {z(α + βi) : α,β ∈ R,−1 2 < α,β < 1 2 )} and the closure of F(z) F(z) = {z(α + βi) : α,β ∈ R,−1 2 ≤ α,β ≤ 1 2 )}. Clearly Fo(z) ⊂F(z) ⊂F(z). Now we will expose some properties of these domains, that will allow us to successfully develop the scheme. Proposition 3.2. Let v,z ∈ Z[i], z 6= 0. (a) If N(v) < N(z)/2, then F(v) ⊂F(z). (b) {u ∈ Z[i] : N(u) < N(z/2)}⊂Fo(z) ⊂{u ∈ Z[i] : N(u) ≤ N(z)/2}. Proof. (a) Since both F(v) and F(z) are squares centered at 0, it suffices to see that the highest norm of an element in F(v) is less than the smallest norm of an element on the border of F(z). As these are reached at v(1 2 + 1 2 i) and z(1 2 ) respectively, the inclusion is a consequence of the chain of inequalities N ( v(1 2 + 1 2 i) ) = 1 2 N(v) < 1 4 N(z) = N ( z(1 2 ) ) . (b) The left hand inclusion holds because the element with the lowest norm on the border of F(z) has norm N(z)/4. The right hand one is due to the property of the normalized remainder r in the Euclidean division that N(r) ≤ N(z)/2. The units (that is, the invertible elements) of Z[i] are precisely the elements with norm 1, that is ±1,±i. The associates of a Gaussian integer z are the products uz, where u is a unit. Thus, the associates of z are ±z,±iz. Clearly two associated numbers z and uz generate the same ideal in Z[i]. So given z1, . . . ,zn ∈ Z[i], the expressions gcd(z1, . . . ,zn) and lcm(z1, . . . ,zn) are defined up to associates. Note that in general F(z) 6= F(uz) and thus, for v ∈ Z[i], we may have v (mod z) 6= v (mod uz). For example, z/2 ∈F(z) but z/2 /∈F(−z) and thus, if z/2 ∈ Z[i] then we have z/2 (mod z) = z/2,z/2 (mod −z) = −z/2. Proposition 3.3. Let u,v,z be three Gaussian Integers such that u is a unit. The following properties hold. (a) Fo(z) = Fo(uz) and F(z) = F(uz). (b) If v (mod z) ∈Fo(z), then v (mod uz) = v (mod z). Proof. The proof of (a) is straightforward from the definitions of Fo(z) and F(z). (b) If v = qz + r then also v = (q/u)uz + r, so the result is a direct consequence of (a). As a consequence of this result we find that if v (mod lcm(z1, . . . ,zn)) ∈ Fo(lcm(z1, . . . ,zn)) for some choice of lcm(z1, . . . ,zn) and v (mod lcm(z1, . . . ,zn)), then the Gaussian Integer given by the expression v (mod lcm(z1, . . . ,zn)) is uniquely determined, and moreover v (mod lcm(z1, . . . ,zn)) ∈ Fo(lcm(z1, . . . ,zn)). Proposition 3.4. Let v1,v2,z be Gaussian Integers such that v1,v2 ∈ F(z). If v1 ≡ v2 (mod z) and v1 ∈Fo(z), then v1 = v2. Proof. If v1 ≡ v2 (mod z) with v1 ∈ Fo(z),v2 ∈ F(z), then there exist a unit u such that v1,v2 ∈ F(uz). The result follows from the uniqueness of the remainder in a fundamental domain stated in Proposition 3.1. 180 D. Munera-Merayo / J. Algebra Comb. Discrete Appl. 9(3) (2022) 175–184 3.2. A Mignotte SSS over Z[i] Now that we have found a way to guarantee the uniqueness of a remainder, we may expose the desired extension of the scheme. Let P = {1, . . . ,n} be a set of n participants and let m : m1,m2, . . . ,mn, be a sequence of n (not necessarily pairwise coprime) non-zero Gaussian Integers. We assign the Gaussian Integer mi to each participant i. To abbreviate, given a coalition C ⊆ P we write lcm(C) = lcm{mi : i ∈ C}. We say that N(lcm(C)) is the norm of C. Let m−,m+ be two integers such that 4m− < m+ and the norm of no coalition lies within the interval (m−,m+) , that is, for all C ⊆ P we have either N(lcm(C)) ≤ m− or N(lcm(C)) ≥ m+. Furthermore, we impose that π(m +−4m−) 4m− > 1. We may now consider the access structure over P A = {A ⊆P : N(lcm(A)) ≥ m+}. Let us now develop a SSS R realizing the structure A. The set of secrets to be shared is S = {s ∈ Z[i] : m− ≤ N(s) < m+ 4 }. The procedure goes as usual. Given a secret s ∈S, the shares si are si = s (mod mi). If an authorized coalition A wants to recover the secret, they may solve the system of congruence equations (SA) x ≡ si (mod mi) i ∈ A whose solution is unique modulo lcm(A). The secret is x (mod lcm(A)). Please note that for any coalition C the corresponding system (SC) has a solution, since s (mod lcm(C)) is so. Thus we only need the Chinese theorem to find the solution and to guarantee its uniqueness. Theorem 3.5. The above method is correct and gives a secret sharing scheme whose access structure is A. Proof. An authorized coalition A can solve the system and, from the solution x, obtain x (mod lcm(A)) ∈ F(lcm(A)). Since N(s) < m+/4 ≤ N(lcm (A))/4, Proposition 3.2 guarantees that s ∈ Fo(lcm(A)), and by Proposition 3.3 this holds for any choice of lcm(A). Then, from Proposition 3.4, we have x (mod lcm(A)) = s, and A successfully recovers the secret. An unauthorized coalition B may find the solution x of (SB) modulo lcm(B). However, since N(s) ≥ m− ≥ N(lcm(B)) > N(x), it holds that s 6= x. B can also compute x (mod lcm(B)) ∈ F(lcm(B)). But since N(s) > m−/2 > N(lcm (B))/2, again according to Proposition 3.2, we have s 6∈ F(lcm(B)). Hence x (mod lcm(B)) 6= s. We focus on this on section 3.3. Example 3.6. We will now see how Example 1 would work under this new method. Let n = 3, m : 7+4i,−3−13i,11+8i and take t = 2. The set of secrets will now be S = {s ∈ Z[i] : 185 ≤ N(s) < 2892}. Let s = 70 − 70i. Note that N(s) = 9800 so s is not a valid secret, and thus cannot be shared. This explains why the method proposed in [10] does not work on this case. 3.3. Some properties Once the method is described we may study some of its properties. Computing the information rate of this scheme leads to the so called Gauss circle problem, which asks about the number of Gaussian Integers inside a circle of radius r > 0 centered at the origin. That is to say, the number of Gaussian Integers z such that N(z) ≤ N(r) = r2, [6]. We denote this number by N(r). Since, on average, each unit square contains one Gaussian Integer, N(r) is approximately equal to the area of a circle of radius r, N(r) ∼ πr2 181 D. Munera-Merayo / J. Algebra Comb. Discrete Appl. 9(3) (2022) 175–184 It is also known a explicit expression for this number: N(r) = 1 + 4 ∞∑ j=0 (b r2 4j + 1 c−b r2 4j + 3 c) Then the number of possible secrets to be shared is |S| = N( √ m+ −1 2 )−N( √ m− −1) = 4 ∞∑ j=0 (b m+ −1 16j + 16 c−b m+ −1 16j + 12 c)−{4 ∞∑ j=0 (b m− −1 4j + 1 c−b m− −1 4j + 3 c)} ∼ π ( m+ −1 4 −m− + 1 ) ∼ π ( m+ 4 −m− ) . On the other hand, the set Si of possible shares for participant i is precisely the set of congruence classes of Gaussian Integers modulo mi. It is well known that the number of such congruence classes is the norm N(mi), [4]. Unfortunately, the scheme is not perfect. An unauthorized coalition B can solve (SB) and thus it may compute x = s (mod lcm(B)). So it may deduce that the secret is of the form x + λ lcm(B) for some λ ∈ Z[i]. Thus it can discard all secrets of S not satisfying this condition. Since N(lcm(B)) < m−, this fact reduces for B the set of secrets to a set of cardinality equal to  4 ∞∑ j=0 (b m+ −1 16j + 16 c−b m+ −1 16j + 12 c)−{4 ∞∑ j=0 (b m− −1 4j + 1 c−b m− −1 4j + 3 c)}  /N(lcm(B)) ∼ π(m+ −4m−)/4 N(lcm(B)) > π(m+ −4m−) 4m− . So this number should be large enough in order to guarantee the security of the scheme. Note that we have imposed that number to be larger than 2, so that the coalition B never compute the correct secret. Example 3.7. Let m be the sequence of pairwise coprime Gaussian Integers m : 15+14i,10−18i,13+16i. Take m− = 425,m+ = 178504. This choice leads to a (2,3) threshold access structure. The set of secrets is S = {s ∈ Z[i] : 425 ≤ N(s) ≤ 44625}. The number of possible secrets is then |S| = N( √ 44625)−N( √ 424) ∼ 138858 while the set of possible shares has cardinality at most N(13 + 16i) = 425. Of course the scheme is not perfect. As noted before, an unauthorized coalition B can reduce the whole set of secrets to a set of size at least (approximately) π ( (m+/4)2 − (m− −1)2 ) m− ≈ 327. 182 D. Munera-Merayo / J. Algebra Comb. Discrete Appl. 9(3) (2022) 175–184 3.4. Any access structure can be realized by a Mignotte SSS over Z[i] An interesting question is to characterize those access structures that can be realized by a Mignotte construction. The next proposition is analogous to Theorem 2.2 of [5]. Even the proof is an adaptation of it, we will include it for the convenience of the reader. Theorem 3.8. For any access structure A over n participants and any integer S, there is sequence m : m1, . . . ,mn of Gaussian Integers such that the Mignotte SSS over Z[i] arising from m realizes the structure A with a set of secrets S of cardinality |S|≥ S. Proof. Let A be an access structure over a set P of n participants and let B1, . . . ,Bt be the maximal unauthorized coalitions forA. Choose t pairwise coprime Gaussian Integers µ(1), . . . ,µ(t) with N(µ(j)) > 8 for all j = 1, . . . , t, and let µ = µ(1) · · ·µ(t). Now for i = 1, . . . ,n and j = 1, . . . , t, define µ (j) i = { 1 if i ∈ Bj µ(j) if i 6∈ Bj and mi = µ (1) i · · ·µ (t) i . Then the Mignotte scheme associated to the sequence m : m1, . . . ,mn realizes the structure A. To see that let m+ = N(µ) and ` = m+/min{N(µ(1)), . . . ,N(µ(t))}. Note that 4` < m+. Let A ∈A be an authorized coalition. For each maximal unauthorized coalition Bj there is a participant i (depending on j) such that i ∈ A\Bj. Thus µ (j) i = µ (j) and hence µ(j)|lcm(A). Since this reasoning holds for any j = 1, . . . , t, we conclude that lcm(A) = µ, so N(lcm(A)) = m+. Conversely, let B be an unauthorized coalition. Then there exists j such that B ⊆ Bj. It follows that µ (j) i = 1 for all i ∈ B, and hence N(lcm(B)) ≤ m +/N(µ(j)) ≤ `. We have proved that A = {A ⊆ P | N(lcm(A)) ≥ m+}, so the sequence m : m1, . . . ,mn realizes the structure A with set of secrets S = {s ∈ Z[i] : m− ≤ N(s) < m + 4 }, where m− = max{N(lcm(B1)), . . . ,N(lcm(Bt))} ≤ `. Since m+ 4 −m− ≥ `, by choosing the Gaussian Integers µ(1), . . . ,µ(t) having large enough norm, it is clear that we can always get |S|≥ S. The simplest case of Mignotte’s construction arises when all the numbers in the sequence m are pairwise coprime. Let us recall that an access structure A is weighted threshold if there is an n-tuple w = (w1, . . . ,wn) of positive weights and a threshold t such that A = {A ⊆P : ∑ i∈A wi ≥ t}. The proof that a weighted access structure defined by real weights can be also written by using integer weights is straightforward. Proposition 3.9. If the Gaussian Integers in the sequence m : m1,m2, · · · ,mn are pairwise coprime, then for any m+ the access structure A(m,m+) is a weighted threshold access structure. Proof. A coalition C is authorized if and only if N(lcm(C)) = ∏ i∈C N(mi) ≥ m +, that is if and only if ∑ i∈C log(N(mi)) ≥ log(m +), so A(m,m+) is weighted threshold structure with weights log(N(mi)), j = 1 . . . ,n, and threshold log(m+). Example 3.10. Let m be the sequence of pairwise coprime Gaussian Integers m : 6 + 5i,1 − 9i,13 + 16i, and take m− = 5002,m+ = 25925. This sequence leads to the access structure A whose minimal authorized coalitions are {1,3} and {2,3}, which certainly is a weighted threshold access structure with weights 1,1,2 and threshold t = 3. 183 D. Munera-Merayo / J. Algebra Comb. Discrete Appl. 9(3) (2022) 175–184 References [1] C. A. Asmuth, J. Bloom, A modular approach to key safeguarding, IEEE Trans. Inf. Theory 29(2) (1983) 208–210. [2] R. Blahut, Algebraic methods for signal processing and communications. Springer-Verlag (1992). [3] P. Dingyi, S. Arto, D. Cunsheng, Chinese remainder theorem: applications in computing, coding and cryptography. World Sci. (1996). [4] J. B. Fraleigh, A first course in abstract algebra, 2nd Edition, Addison-Wesley (1976). [5] T. Galibus, G. Matveev, Generalized Mignotte’s sequences over polynomial rings, Electron. Notes Theor. Comput. Sci. 186 (2007) 43–48. [6] R. K. Guy, Unsolved problems in number theory, 3rd Edition, Springer-Verlag (2004). [7] S. Iftene, General secret sharing based on the Chinese remainder theorem with applications in eâĂŞvoting, Electron. Notes Theor. Comput. Sci. 186 (2007) 67–84. [8] M. A. Jodeit, Uniqueness in the division algorithm, Amer. Math. Montly 74(7) (1967), 835-836. [9] M. Mignotte, How to share a secret, In Proceedings of the Workshop on Cryptography Burg Feuer- stein, 1982, 149, Springer-Verlag (1983) 371–375. [10] I. Ozbek, F. Temiz, I. Siap, A generalization of the Mignotte’s scheme over Euclidean domains and applications to secret image sharing, J. Algebra Comb. Discrete Appl. 6(3) (2019) 147–161. [11] A. Shamir, How to share a secret?, Communications of ACM 22(11) (1979) 612–613. [12] D. Stinson, Cryptography: theory and practice, CRC Press (2005). [13] G. Ulutas, M. Ulutas, V. Nabiyev, Secret sharing scheme based on Mignotte’s scheme, IEEE 19th Signal Processing and Communications Applications Conference (SIU), Antalya (2011) 291–294. 184 https://doi.org/10.1109/TIT.1983.1056651 https://doi.org/10.1109/TIT.1983.1056651 https://link.springer.com/book/10.1007/978-1-4612-2826-4 https://doi.org/10.1142/3254 https://doi.org/10.1142/3254 https://www.worldcat.org/title/first-course-in-abstract-algebra/oclc/991699474?referer=br&ht=edition https://doi.org/10.1016/j.entcs.2006.12.044 https://doi.org/10.1016/j.entcs.2006.12.044 https://link.springer.com/book/10.1007%2F978-0-387-26677-0 https://doi.org/10.1016/j.entcs.2007.01.065 https://doi.org/10.1016/j.entcs.2007.01.065 https://doi.org/10.2307/2315810 https://doi.org/10.1007/3-540-39466-4_27 https://doi.org/10.1007/3-540-39466-4_27 https://mathscinet.ams.org/mathscinet-getitem?mr=4010414 https://mathscinet.ams.org/mathscinet-getitem?mr=4010414 https://doi.org/10.1145/359168.359176 https://www.worldcat.org/title/cryptography-theory-and-practice/oclc/1158700191&referer=brief_results https://doi.org/10.1109/SIU.2011.5929644 https://doi.org/10.1109/SIU.2011.5929644 Introduction Some background on SSS's and Gaussian integers A Mignotte SSS over Gaussian integers References