Enhanced multisecret-sharing schemes using LCD codes and weighing orthogonal matrices
- Open Access
- 18.04.2025
- Original Research
Erschienen in:
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by (Link öffnet in neuem Fenster)
Abstract
1 Introduction
In this study, we focus on orthogonal matrices, specifically weighing orthogonal matrices. Several researchers have proposed methods for constructing orthogonal matrices [2‐5]. In [6], a table of lower bounds on the largest size of an LCD code was designed based on orthogonal matrix constructions. Ephremidze and Spitkovsky [7] introduced a superfast method for generating orthogonal matrices in finite fields. Additionally, Kumari and Mahato [9] presented techniques for constructing self-orthogonal, orthogonal and antiorthogonal matrices over finite fields. Hill [8] applied orthogonal matrices in cryptography through the Hill cipher, where the inverse of an orthogonal matrix is given by its transpose.
Orthogonal matrices have significant applications in cryptography [10, 11]. For example, Koukouvinos et al. [13] used circulant Hadamard cores to construct an encryption scheme in 2013, while Kumari and Mahato [9] proposed an encryption scheme based on weighted orthogonal matrices.
Anzeige
Secret sharing schemes play a fundamental role in cryptographic protocols. The concept was first introduced by Blakley [12] and Shamir [14] in 1979. Since then, various researchers have explored secret sharing techniques, including schemes based on self-dual codes [15], threshold-based methods using one-way functions [16], and approaches leveraging Golay codes [20]. Ding, Laihonen and Renvall [21] investigated code-based multisecret-sharing schemes, while Çalkavur et al. [22] provided an extensive overview of secret sharing schemes in their 2022 book, Code Based Secret Sharing Schemes.
In a traditional secret sharing scheme, a dealer distributes a secret among participants, with only specific subsets authorized to reconstruct the original secret. Li et al. [23] recently introduced an efficient quantum secret sharing scheme based on restricted threshold access structures, while Saurabh and Sinha [24] proposed perfect secret sharing schemes using combinatorial squares.
Multisecret-sharing schemes represent an important extension of secret sharing, allowing multiple secrets to be distributed simultaneously. Recent advancements include DNA-based multisecret-sharing schemes over the ring \({\mathbb{Z}_4} \times R\), where \(R = {\mathbb{Z}_4} + u{\mathbb{Z}_4}\), with \({u^2} = 0\) [25] and quantum multisecret-sharing methods with access structures [26]. Other researchers have explored multisecret-sharing techniques using one-way functions [17], threshold schemes [18], and lattice-based cryptographic constructions [19].
LCD codes have gained considerable attention due to their applications in cryptography, data storage, and communication systems. They have also been utilized in lattice constructions [29] and network coding [27, 30]. Recent studies have focused on optimizing LCD codes, such as the work of Lu, Li and Ren [33] on quaternary Hermitian LCD codes in 2024. Secret sharing schemes based on LCD codes have also been explored, including the work of Ghosh et al. [34] and Alahmadi et al. [35], who proposed a multisecret-sharing scheme using LCD codes. Crnkovic et al. [31] studied LCD codes derived from weighing matrices, and Zoubir et al. [32] introduced new construction methods for LCD codes.
Anzeige
Building on previous research [31, 35], this paper investigates multisecret-sharing schemes based on LCD codes derived from weighing orthogonal matrices. We propose two new schemes:
1.
A multisecret-sharing scheme using Euclidean LCD codes from weighing orthogonal matrices.
2.
A multisecret-sharing scheme using LCD codes from skew weighing orthogonal matrices.
We analyze the access structures, coalition statistics, security properties, and information-theoretic efficiency of these schemes. Finally, we compare our proposed methods with existing multisecret-sharing schemes.
The remainder of this paper is structured as follows. Section 2 provides background on linear codes, secret-sharing schemes, and ramp secret-sharing schemes. Section 3 presents the proposed multisecret-sharing schemes based on LCD codes and weighing orthogonal matrices. Section 4 provides a comparative analysis of our schemes against existing multisecret-sharing methods. Section 5 evaluates the performance of the proposed schemes through encryption time, decryption time, and memory usage benchmarks. Section 6 concludes the paper with insights and future research directions. By leveraging LCD codes and weighing orthogonal matrices, our approach enhances security, efficiency, and scalability, making it a promising solution for modern cryptographic applications such as secure cloud storage, blockchain security, and distributed computing.
2 Preliminaries
In this part section, we provide an overview of key concepts relevant to our study, including linear codes, secret sharing schemes, and ramp secret sharing schemes. We also introduce the fundamental principles of multisecret-sharing schemes based on LCD codes.
2.1 Linear codes
Consider an \([n,k]\)—linear code \(C\) over the finite field \({\mathbb{F}_q}\), where \(C\) is a subspace of \({({\mathbb{F}_q})^n}\). The parameters \(n\) and \(k\) represent the length and dimension of the code, respectively. The dual code of \(C\), denoted as \({C^ \bot }\), consists of all codewords that are orthogonal to every codeword in \(C\). \({C^ \bot }\) is an \([n,n - k]\)–code.
The generator matrix \(G\) of \(C\) is a \(k \times n\) matrix whose rows form a basis for \(C\). The parity-check matrix \(H\) is an \((n - k) \times n\) matrix that serves as a generator matrix for \({C^ \bot }\).
A linear code \(C\) is called an LCD code (Linear Complementary Dual code) if it satisfies \(C \cap {C^ \bot } = \{ 0\} \). LCD codes are widely used in cryptography and error correction due to their structural properties and robustness against attacks.
Remark 1
The condition \(C \cap {C^ \bot } = \{ 0\} \) for an LCD code depends on the finite field \({\mathbb{F}_q}\). The most important result to know about LCD codes is that every \([n,k]\)-code is equivalent to an LCD code for \(q > 3\) [1]. Additionally, for certain fields, LCD codes can be optimized by selecting generator matrices that ensure self-orthogonality conditions are minimized.
2.2 Secret sharing schemes
Secret sharing is a cryptographic technique that involves distributing a secret among participants in such a way that only authorized subsets can reconstruct it. A secret sharing scheme consists of the following components:
-
Secret: A valuable piece of information, such as cryptographic key.
-
Dealer: The entity responsible for selecting and distributing the secret.
-
Shares: Portions of the secret assigned to participants.
-
Sharing Set: The collection of all distributed shares.
-
Access Structure: The set of minimal coalitions (subsets of participants) that can reconstruct the secret.
-
Information Rate: The ratio between the secret’s size and the size of an individual participant’s share.
-
Ideal Scheme: A secret sharing scheme is ideal if its information rate is 1.
2.3 Ramp secret sharing schemes
A ramp secret sharing scheme divides a secret \(m\) into multiple pieces \({m_1},{m_2}, \ldots,{m_M},\) where only certain subsets of shares can recover the full secret. In a \((T,M,n)\)‒threshold ramp secret sharing scheme:
-
Any subset of at least \(T\) shares can fully recover the secret.
-
Any subset of at most \(T - M\) shares has no information about the secret.
-
If a subset of size \(l\) has no information about the secret, but a subset of size \(l + 1\) does, the scheme is said to have \(l\)‒privacy.
2.4 Multisecret-sharing schemes based on LCD codes
A multisecret-sharing scheme using LCD codes is structured as follows.
-
Select an \([n,k]\)‒LCD code \(C\) over \({\mathbb{F}_q}\) with generator matrix \(G\) and parity-check matrix \(H\).
-
Define the secret space as \({({\mathbb{F}_q})^n}\).
-
Choose a secret \(S = ({s_1},{s_2}, \ldots,{s_n})\) from the code \(C\).
-
Determine the minimal access elements, which correspond to the rows of \(G\).
-
Assign each participant a share \(y \in {({\mathbb{F}_q})^n}\), calculated as$$y = < c,s > = c.{S^T},$$
-
where \({S^T}\) denotes the transpose of \(S\).
-
Compute the set of shares as$$G \cdot {S^T} = {Y^T},$$
-
where \(Y = ({y_1},{y_2}, \ldots,{y_k})\).
-
Since \(C\) is an LCD code, the matrix \( ( {\begin{array}{*{20}{c}} G \\ H \end{array}} )\) is invertible, ensuring that the secret can be uniquely reconstructed.
-
The secret is recovered by solving the linear system$$G \cdot {S^T} = {Y^T},$$$$H \cdot {S^T} = 0.$$
This structure ensures that only authorized subsets of participants can reconstruct the secret, thereby preventing unauthorized access.
3 Construction of multisecret-sharing schemes using LCD codes and weighing orthogonal matrices
In this section, we first review the construction of LCD codes derived from weighing orthogonal matrices as presented in [36]. Based on these constructions, we propose novel multisecret-sharing schemes.
3.1 Euclidean LCD codes from weighing orthogonal matrices
Lemma 1
[37] Let \(G\) be a generator matrix for a linear code over a given field. Then, \(det(G \cdot {G^T}) \ne 0\) if and only if \(G\) generates an LCD code.
Using this characterization, we establish the following result:
Proposition 1
Consider the matrix \({B_1} = a{J_n} + x{I_n},a,x \in \mathbb{F}\) for some field \(\mathbb{F}\). The matrix \({B_1}\) is similar to the \((n \times n)\) matrix
$${B_2} = \left( {\begin{array}{*{20}{c}} {x + na}&{O_{n - 1}^T} \\ {a{J_{n - 1}}}&{x{I_{n - 1}}} \\ {}&{} \end{array}} \right),$$
where \({J_n}\) is the all-ones matrix and \({I_n}\) is the identity matrix. The determinant of \(det({B_1})\) is given by \(det({B_1}) = (x + na){x^{n - 1}}.\)
Proof. It is seen that \(V{B_1}{V^{ - 1}} = {B_2}\), where
$$V = \left( {\begin{array}{*{20}{c}} 1&{J_{n - 1}^T} \\ {{O_{n - 1}}}&{{I_{n - 1}}} \\ {}&{} \end{array}} \right)$$
and
$${V^{ - 1}} = \left( {\begin{array}{*{20}{c}} 1&{ - {J^T}} \\ {{O_{n - 1}}}&{{I_{n - 1}}} \\ {}&{} \end{array}} \right).$$
The result is obtained.□
Theorem 1
Let \(W(n,m)\) be a weighing orthogonal matrix, and let \(G = [W|{I_n}]\) be a generator matrix over \({\mathbb{F}_q}\). Then, \(G\) generates a \([2n,n]\)‒LCD code \(C\) if \(m + 1 \ne 0\) in \({\mathbb{F}_q}\).
Corollary 1
The matrix \(G{^{\prime}} = [W|\alpha {I_n}]\) generates the dual code \({C^ \bot }\) if \(\alpha \in {\mathbb{F}_q}\) satisfies \(\alpha + m = 0\) in \({\mathbb{F}_q}\).
Proof. The \(n\)‒dimensional code generated by \(G{^{\prime}}\) is included in \({C^ \bot }\) since each row of \(G{^{\prime}}\) is orthogonal to each row of \(G\).□
3.2 Multisecret-sharing schemes with Euclidean LCD codes from weighing orthogonal matrices
Based on the above results, we construct multisecret-sharing schemes using Euclidean LCD codes.
Theorem 2 Let \(W(n,m)\) be a weighing orthogonal matrix, and let \(G = [W|{I_n}]\) be a generator matrix over \({\mathbb{F}_q}\). A multisecret-sharing scheme based on \(C\), the LCD code generated by \(G\), has the following properties if \(m + 1 \ne 0\) over \({\mathbb{F}_q}\).
(i)
The access structure consists of \(n\)‒tuples of linearly independent codewords.
(ii)
The minimum number elements required to reconstruct the secret is \(n\).
Proof. Step 1: Showing that \(G\) Generates an LCD Code
Since \(W(n,m)\) is a weighing orthogonal matrix, it satisfies the orthogonality condition \(W{W^T} = m{I_n}\). The generator matrix of the LCD code is given by \(G = [W|{I_n}].\) To confirm that \(G\) generates an LCD code, we compute
$$G \cdot {G^T} = W \cdot {W^T} + {I_n} \cdot I_n^T.$$
Since \({I_n} \cdot I_n^T = {I_n}\), we obtain
$$G \cdot {G^T} = m \cdot {I_n} + {I_n} = (m + 1) \cdot {I_n}.$$
Because \((m + 1) \cdot {I_n}\) is a diagonal matrix with nonzero diagonal entries (assuming \(m + 1 \ne 0\) in \({\mathbb{F}_q}\)), it is full rank. By Lemma 1, this implies that \(G\) generates an LCD code.
Step 2: Constructing the Access Structure
In a multisecret-sharing scheme based on a \([2n,n]\)‒LCD code [35], the secret is reconstructed using a full-rank generator matrix \(G\), meaning that an authorized set for participants corresponds to \(n\) linearly independent rows of \(G\). Thus, the access structure consists of subsets of \(n\)‒tuples of linearly independent codewords.
Step 3: Determining the Minimal Coalition Size
Since \(G\) is a \([2n,n]\) matrix, the secret is encoded in a vector \(S\) of dimension \(n\), where
$${G^ \cdot }{S^T} = {Y^T}.$$
To reconstruct the secret \(S\), we must solve the system
$${G^ \cdot }{S^T} = {Y^T}.$$
Since \(G\) is full-rank, at least \(n\) linearly independent rows of \(G\) are required to ensure a unique solution for \(S\). This means that the number of participants needed to recover the secret is precisely \(n\).
Conclusion
-
The access structure consists of \(n\)‒tuples of linearly independent codewords.
-
The minimum coalition size required to reconstruct the secret is \(n\).
Thus, Theorem 2 is proven. □
Corollary 2 A multisecret-sharing scheme satisfying the conditions of Theorem 2 also forms a \((n,2n,{q^n})\) ramp secret sharing scheme with \(n - 1\) privacy.
Proof. Among the \({q^n}\) participants, only \(n\) can recover the secret. However, these \(n\) participants must be linearly independent. Some dependent \(n\)‒tuples cannot recover the secret. Additionally, the secret is divided into multiple shares \(({s_1},{s_2}, \ldots,{s_{2n}})\).□
3.2.1 Coalition statistics
Theorem 3
The number of minimal coalitions in the proposed multisecret-sharing scheme is given by
$$\frac{{{q^n}({q^n} - 1)({q^n} - q) \ldots ({q^n} - {q^{n - 1}})}}{{n!}}.$$
This formula is derived by assuming that all bases in the LCD code are equally probable. However, in practice, LCD codes may introduce structural biases in the distribution of codewords, affecting the probability of forming certain bases.
Justification of Equiprobability Assumption
In classical linear codes, any randomly chosen set of \(n\) independent codewords forms a valid basis with uniform probability. This is generally true for random linear codes over \({\mathbb{F}_q}\), where the likelihood of selecting a valid basis follows a uniform distribution. For LCD codes, the condition \(C \cap {C^ \bot } = \{ 0\} \) ensures that codewords are linearly independent with high probability, but it may also constrain the number of possible bases due to additional structural properties of LCD codes (e.g., orthogonality constraints). If the distribution of codewords in an LCD code deviates from uniformity, the actual number of minimal coalitions may be lower than the theoretical estimate.
Impact on the Number of Coalitions
If the equiprobability assumption does not hold, the total number of minimal coalitions could be overestimated. The deviation depends on:
1.
Field Size \(q\): Larger \(q\) values make the uniformity assumption more accurate since the space of possible.
2.
Code Structure: Some LCD codes may have a preferred subspace structure, reducing the number of independent bases.
3.
Weight Distribution of Codewords: If LCD codes favor specific weight distributions, certain coalitions may be more likely than others.
Future work could analyze the exact impact of these factors by experimentally estimating the number of bases in practical LCD constructions.
Proof. Step 1: Understanding Minimal Coalitions
A minimal coalition is the smallest set of participants that can reconstruct the secret. Since the multisecret-sharing scheme is based on an LCD code of dimension \(n\), any valid set of participants must correspond to an \(n\)‒tuple of linearly independent codewords in \(C\). The number of minimal coalitions is therefore equal to the number of bases that can be formed from \(C\), where a basis is a set of \(n\) linearly independent codewords.
Step 2: Counting the Number of Bases in \(\,C\)
The set of codewords in \(C\) forms an \(n\)‒dimensional vector space over \({\mathbb{F}_q}\), meaning there are \({q^n}\) possible codewords in \(C\). To construct a basis, we select \(n\) linearly independent vectors from this space.
-
The first vector can be any nonzero vector in \({({\mathbb{F}_q})^n}\), giving \({q^n} - 1\) choices.
-
The second vector must be independent of the first, meaning it can be any vector in \({({\mathbb{F}_q})^n}\) that is not a multiple of the first, giving \({q^n} - q\) choices.
-
The third vector must lie in the span of the first two vectors, giving \({q^n} - {q^2}\) choices.
-
Continuing this process, the number of choices for the \(i\)‒th vector is \({q^n} - {q^{i - 1}}\).
Thus, the total number of ways to select an ordered basis of \(C\) is
$$({q^n} - 1)({q^n} - q)({q^n} - {q^2}) \ldots ({q^n} - {q^{n - 1}}).$$
However, since the order of the basis vectors does not matter, we must divide by the number of ways to arrange \(n\) vectors, which is \(n!\). Therefore, the total number of minimal coalitions is
$$\frac{{{q^n}({q^n} - 1)({q^n} - q) \ldots ({q^n} - {q^{n - 1}})}}{{n!}}.$$
Security Implications
Since the number of minimal coalitions increases rapidly as \(q\) and \(n\) grow, it becomes increasingly difficult for an attacker to determine the secret. The large number of possible coalitions enhances security by ensuring that unauthorized sets of participants cannot reconstruct the secret.
Thus, Theorem 3 is proven. □
Remark 2 This value is strictly less than \( ( {\begin{array}{*{20}{c}} {{q^n}} \\ {2n} \end{array}} ) \), which reinforces the security of the scheme.
3.2.2 Security analysis
Suppose that a coalition of \(c\) participants, where \(c < n\), attempts to reconstruct the secret. The subspace \({A_c}\) spanned by their associated codewords is a subset of \(C\). Let \({B_c}\) be a complementary subspace such that \(C = {A_c} \oplus {B_c}\), where \(dim{A_c} = c\) and \(dim{B_c} = n - c\).
Using Theorem 3, the number of ways to extend a basis of \({A_c}\) to a basis of \(C\) is given by
$$T(n,c) = \frac{{\prod\nolimits_{i = 0}^{n - 1} ({q^n} - {q^i})}}{{(n - c)!\prod\nolimits_{i = 0}^{c - 1} ({q^c} - {q^i})}}.$$
Thus, an adversary attempting to reconstruct the secret with probability
$${q^{ - (n - c)}}.\frac{1}{{T(n,c)}}$$
has a negligible chance of success when \(n\) is large. The security of the scheme is thus dependent of the choice of \(n\) and \(q\).
3.2.3 Security considerations in ramp secret sharing
The proposed scheme employs a ramp secret-sharing approach, which allows a trade-off between security and efficiency. Unlike threshold secret-sharing, where unauthorized participants learn nothing, ramp schemes permit partial information leakage to unauthorized coalitions. This section clarifies the extent of information leakage and the security implications of different parameter choices.
1.
Information Leakage to Unauthorized Coalitions
In a \((T,M,n)\)-ramp secret-sharing scheme, different participant subsets have different levels of access to the secret:
-
Coalitions with fewer than \(T - M\) participants gain no information about the secret.
-
Coalitions with \(T - M\) to \(T - 1\) participants learn partial information but cannot fully reconstruct the secret.
-
Coalitions with at least \(T\) participants can fully recover the secret.
The amount of information leaked to unauthorized coalitions depends on the structure of the underlying LCD code. Since LCD codes ensure that minimal coalitions are required for secret recovery, they help control how much information leaks in the ramp model. However, a formal analysis of the entropy reduction in unauthorized sets could strengthen the security analysis.
2.
Security Trade-offs in Different Parameter Settings
The choice of \(n\) (code length), \(k\) (code dimension), and \(q\) (finite field size) affects both security and efficiency:
-
Larger \(n\) increases security by making minimal coalitions harder to form, but increases computational complexity.
-
Smaller \(M\) (gap between access threshold and full access) reduces information leakage but increases the number of required participants for reconstruction.
-
Larger \(q\) (field size) reduces the probability of an adversary guessing missing secret components but increases computational overhead.
By carefully selecting \((n,k,M)\), and \(q\), the scheme can balance security (minimal information leakage) and efficiency (reduced participant overhead). Future work could provide a quantitative analysis of these trade-offs, optimizing parameter choices for specific applications.
3.2.4 Information-theoretic efficiency
One of the key metrics for evaluating a secret sharing scheme is the information rate, which is defined as the ratio of the secret size to the total share size.
Since the secret is represented as an \(n\)‒dimensional codeword, the information rate \(\rho \) is given by
$$\rho = \frac{n}{{n + 1}}.$$
The information rate \(\rho \) is close to 1 as \(n \to \infty \), meaning our scheme is nearly ideal since the share size remains minimal relative to the secret size.
3.3 Multisecret-sharing schemes using LCD codes from skew-weighing orthogonal matrices
Before constructing multisecret-sharing schemes based on skew-weighing orthogonal matrices, we first recall the relevant theoretical background from [36].
A weighing orthogonal matrix \(W(n,m)\) is said to be skew-weighing if it satisfies the property \({W^T} = - W\). This property ensures the matrix is skew-symmetric, which leads to specific structural advantages in constructing LCD codes.
Theorem 4 Let \(W(n,m)\) be a skew-weighing orthogonal matrix, and let \(A\) be an \(n \times u\) incidence matrix of an \((r,\lambda )\) combinatorial design. If \(\theta \in {\mathbb{F}_q}\), then the matrix \(G = [W + \theta {I_n}|A]\) generates an LCD code \(C\) of length \(n + u\), provided that \((m + {\theta ^2} + r + (n - 1)\lambda )(m + {\theta ^2} + r - \lambda {)^{n - 1}} \ne 0\) over the finite field \({\mathbb{F}_q}\).
Proof.
\(G \cdot {G^T} = (m + {\theta ^2} + r - \lambda ){I_n} + \lambda {J_n}\) over \({\mathbb{F}_q}\). Proposition 1 and Lemma 1 finish the proof. □
3.3.1 Multisecret-sharing scheme based on skew-weighing orthogonal matrices
Using Theorem 4, we design a multisecret-sharing scheme where the LCD code is constructed from skew-weighing orthogonal matrices.
Corollary 3 If \(A = {I_n}\), then \(G\) generates a \([2n,n]\) LCD code, provided that \(m + {\theta ^2} + 1 \ne 0\) over \({\mathbb{F}_q}\). Moreover, the matrix \(G{^{\prime}} = [W + \theta {I_n}|\alpha {I_n}]\) generates the dual code \({C^ \bot }\) over \({\mathbb{F}_q}\).
Since \(C\) is a \([2n,n]\) LCD code, the same access structures and security properties as in Section 3.2 apply to this scheme.
3.3.2 Examples
Example 1. Consider the \([8,4,3]\) LCD code constructed from skew-weighing orthogonal matrices over \({\mathbb{F}_3}\). The corresponding multisecret-sharing scheme has the following properties:*
-
The access structure consists of \(4\)‒tuples of linearly independent codewords.
-
The minimal coalition size required to reconstruct the secret is 4.
-
The scheme forms a \({(4,8,3^4})\) ramp secret sharing scheme with 3 privacy.
-
The number of minimal coalitions is$$\frac{{{3^4}{{(3}^4} - {{1)(3}^4} - {{3)(3}^4} - {3^2}{{)(3}^4} - {3^3})}}{{4!}} = 81.881.280.$$
-
The information rate is \(\rho = \frac{4}{5} = 0.8\)
Example 2. Consider the \([16,8,7]\) LCD code constructed from skew weighing orthogonal matrices over \({\mathbb{F}_5}\). The corresponding multisecret-sharing scheme has the following properties:
-
The access structure consists of \(8\)‒tuples of linearly independent codewords.
-
The minimal coalition size required to reconstruct the secret is 8.
-
This scheme forms a \({(8,16,5^8})\) ramp secret sharing scheme with 7 privacy.
-
The number of minimal coalitions is$$\frac{{{5^8}{{(5}^8} - {{1)(8}^8} - {{5)(5}^8} - {5^2}) \ldots {{(5}^8} - {5^7})}}{{8!}}$$
-
The information rate is \(\rho = \frac{8}{9} = 0.88\)
Summary of Section 3. 3
-
Skew-weighing orthogonal matrices provide a structured approach to constructing LCD codes.
-
These LCD codes can be effectively used for multisecret-sharing schemes.
-
The access structures, security properties, and efficiency metrices align with those established in Sect. 3.2.
-
The proposed schemes maintain a high information rate and security level.
4 Comparison with the other schemes
In this section, we compare the proposed multisecret-sharing schemes with existing code-based secret sharing methods in terms of the number participants, secret size, number of coalitions, and information rate. The comparison is summarized in Table 1.
Table 1
Comparison with other schemes in terms of efficiency and performance
Schemes | Number of participants | Size of a secret | Number of coalitions | INFORMATION RATE |
|---|---|---|---|---|
[37] | \(n - 1\) | \(q\) | \(\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)\) | 1 |
[21] | \(n\) | \({q^k}\) | \(\left( {\begin{array}{*{20}{c}} n \\ k \end{array}} \right)\) | \(\frac{k}{{k - 1}}\) |
[28] | \(n\) | \({q^k}\) | \( \geqslant \left( {\begin{array}{*{20}{c}} n \\ {d - t} \end{array}} \right)\) | 1 |
[35] | \({q^k}\) | \({q^n}\) | \(\frac{{\prod\nolimits_{i = 0}^{k - 1} ({q^k} - {q^i})}}{{k!}}\) | \(\frac{k}{{k + 1}}\) |
This paper | \({q^n}\) | \({q^{2n}}\) | \(\frac{{\prod\nolimits_{i = 0}^{n - 1} ({q^n} - {q^i})}}{{n!}}\) | \(\frac{n}{{n + 1}}\) |
4.1 Key observations
1. Number of Participants:
-
The proposed scheme supports a larger number of participants compared to other schemes.
-
The number of participants is \({q^n}\), which is significantly larger than in traditional secret sharing schemes.
2. Secret Size:
-
The secret size in our scheme is \({q^{2n}}\), making it suitable for applications that require high-security multisecret-sharing.
3. Number of Coalitions:
-
Our scheme supports a larger number of minimal coalitions, making it more resistant to unauthorized secret reconstruction.
-
The number of coalitions grows exponentially with \(q\) and \(n\), enhancing security.
4. Information Rate:
-
The information rate \(\rho = \frac{n}{{n + 1}}\) is close to 1 as \(n \to \infty \), meaning our scheme is nearly ideal.
-
Compared to previous schemes, our method provides a more efficient ratio between the secret size and the share size.
4.2 Security and efficiency considerations
-
The security of the proposed schemes is based on the parameters \(n\) and \(q\).
-
A larger \(q\) provides better security but increases computational complexity.
-
The use of LCD codes enhances security by ensuring that minimal coalitions are required to reconstruct the secret.
-
The high number of minimal coalitions makes unauthorized reconstruction extremely difficult.
4.3 Error handling and robustness
The proposed multisecret-sharing scheme relies on LCD (Linear Complementary Dual) codes, which inherently provide some level of error resilience. However, analyzing its error-handling capability is crucial for practical cryptographic applications.
1. Error Resilience of LCD Codes
LCD codes are widely used in cryptography and communication systems due to their structural properties. Since they satisfy \(C \cap {C^ \bot } = \{ 0\} \), they allow efficient encoding and decoding while maintaining robustness against certain types of errors. The ability of an LCD code to correct errors depends on its minimum distance; a higher minimum distance increases error correction capability.
2. Impact of Errors on Secret Reconstruction
In a multisecret-sharing scheme, errors in participants’ shares could lead to incorrect reconstruction of the secret. The scheme ensures that only authorized coalitions (sets of \(n\) participants with linearly independent codewords) can retrieve the secret. If errors occur in fewer than \(n\) shares, the reconstruction might still succeed, depending on the error magnitude and the structure of the LCD code. However, if multiple shares are corrupted, it could prevent successful recovery.
3. Potential Improvements for Error Handling
To enhance error resilience, the scheme could integrate additional mechanisms such as:
-
Error-Correcting Codes (ECC): Incorporating Reed-Solomon or BCH codes into the scheme could allow detection and correction of errors in shares before secret reconstruction.
-
Redundant Shares: Using verifiable secret-sharing techniques or introducing parity checks in share generation can help detect inconsistencies.
-
Fault-Tolerant Reconstruction: Allowing reconstruction from an extended set of shares (e.g., more than \(n\)) could mitigate errors by providing alternative paths to recover the secret.
Conclusion on Error Robustness While LCD codes provide a strong foundation for secure secret sharing, additional error-handling mechanisms could improve the scheme’s reliability, especially in noisy or adversarial environments. Future research could explore hybrid approaches that combine LCD codes with advanced error correction techniques to ensure both security and robustness.
4.4 Conclusion of the comparison
-
The proposed schemes outperform previous approaches in terms of security, efficiency, and the number of supported participants.
-
The high information rate and large coalition set make the schemes suitable for practical cryptographic applications.
-
The trade-off between security and computational cost should be considered when selecting parameters.
4.5 Leveraging LCD codes for error correction in secret sharing
1. Intrinsic Error Correction of LCD Codes
-
LCD codes are known for their efficient encoding and decoding properties. Since an LCD code satisfies \(C \cap {C^ \bot } = \{ 0\} \), it ensures that errors do not propagate uncontrollably during decoding.
-
By choosing LCD codes with a sufficiently large minimum Hamming distance, the scheme can correct a certain number of erroneous shares while still allowing successful reconstruction of the secret.
2. Error-Tolerant Secret Reconstruction
-
In a multisecret-sharing scheme, participants reconstruct the secret using their shares. If errors occur in some shares, an LCD code with strong error-correcting capabilities can detect and correct these errors before they affect secret reconstruction.
-
If the number of erroneous shares is within the error-correction threshold of the LCD code, the system can still recover the original secret without loss of integrity.
3. Enhancing Robustness with Hybrid Approaches
-
The scheme can be further improved by integrating LCD codes with other error-correcting methods, such as Reed-Solomon or BCH codes, to maximize error resilience.
-
A redundancy-based approach can be used, where additional shares (error-checking symbols) are distributed to participants, allowing for detection and correction of tampered or corrupted shares.
-
Adaptive threshold schemes can be implemented where a larger set of participants provides robustness against faulty shares by using majority voting or weighted recovery techniques.
4.5.1 Conclusion
By selecting LCD codes with strong error-correction properties and integrating them with additional redundancy mechanisms, the proposed multisecret-sharing scheme can achieve greater resilience against errors. This enhancement is particularly useful in real-world applications where transmission noise, storage corruption, or adversarial interference could compromise the integrity of secret reconstruction. Future research could focus on optimizing LCD codes specifically tailored for multisecret-sharing scenarios with built-in error correction.
4.6 Computational complexity analysis
The computational cost of encoding and decoding in the proposed multisecret-sharing scheme depends on the parameters \(n\) (code length) and \(q\) (finite field size). This section estimates the time complexity of these operations.
Encoding Complexity
Encoding a secret involves multiplying the generator matrix \(G\) of the LCD code by the secret vector \(S\), given by:
$$Y = G.{S^T},$$
where
-
\(G\) is a \([2n,n]\) generator matrix.
-
S is an \(n\)-dimensional secret vector over \({\mathbb{F}_q}\).
Since matrix-vector multiplication requires \(O({n^2})\) operations in general, the encoding complexity is \(O({n^2})\) over \({\mathbb{F}_q}\).
Decoding Complexity
Reconstructing the secret requires solving a linear system
$$G.{S^T} = {Y^T}$$
If \(G\) is invertible (as ensured by LCD code properties), the secret can be retrieved by computing
$${S^T} = {G^{ - 1}}.{Y^T}$$
Matrix inversion generally requires \(O({n^3})\) operations using Gaussian elimination. However, since \(G\) has a structured form derived from weighing orthogonal matrices, faster inversion techniques (e.g., LU decomposition) may reduce this to operations using Gaussian elimination. However, since \(O({n^2})\) in specific cases.
Impact of Finite Field Size \(q\)
-
For small \(q\), arithmetic operations in \({\mathbb{F}_q}\) are efficient, making encoding and decoding feasible for large \(n\).
-
For large \(q\), finite field operations (multiplication, inversion) become computationally expensive, increasing runtime. Efficient field arithmetic (e.g., lookup tables, fast modular reduction) can mitigate this.
Overall Complexity Table 2 shows the computational complexity of encryption and decryption operations. Encoding has a complexity of \(O({n^2})\), while decoding can have \(O({n^3})\) or \(O({n^2})\) complexity depending on optimizations. For practical applications, choosing moderate values of \(n\) and optimizing finite field operations can balance security and efficiency. Future work could explore hardware-accelerated implementations or optimized decoding algorithms for faster reconstruction.
Table 2
Complexity
Operation | Complexity |
|---|---|
Encoding (Matrix-Vector Multiplication) | \(O({n^2})\) |
Decoding (Solving Linear System) | \(O({n^3})\) (or \(O({n^2})\) with optimizations) |
4.7 Security against potential attacks
While the proposed multisecret-sharing scheme leverages LCD codes and weighing orthogonal matrices to ensure security, it is important to analyze its resistance to various cryptographic attacks. Below, we discuss potential threats and how the scheme mitigates them.
Interpolation Attacks
Attack Description:
Interpolation attacks attempt to reconstruct the secret by solving for unknowns using collected shares. If an attacker gains access to multiple shares, they could attempt to solve for the secret using polynomial interpolation or linear algebra techniques.
Resistance:
-
The scheme requires at least \(n\) linearly independent shares to reconstruct the secret, meaning that an attacker must obtain a full basis of the LCD code to succeed.
-
Since LCD codes are designed to have complementary dual properties, unauthorized subsets of shares do not provide useful partial information about the secret.
-
Choosing a large \(q\) and \(n\) increases the search space, making brute-force interpolation infeasible.
Attacks Based on Code Structure
Attack description:
If an adversary can exploit structural weaknesses in the LCD code, they might reduce the complexity of recovering the secret. For example, if the generator matrix \(G\) has patterns that reveal linear dependencies, an attacker could use them to infer missing shares.
Resistance:
-
LCD codes are carefully chosen to eliminate self-duality (\(C \cap {C^ \bot } = \{ 0\} \)), ensuring that minimal information is leaked through codeword structure.
-
The use of weighing orthogonal matrices ensures that the code structure remains unpredictable, reducing the effectiveness of such attacks.
-
Randomization techniques, such as adding noise or randomly permuting shares, could further enhance security against structure-based attacks.
Brute-Force Attacks
Attack Description:
An adversary could attempt an exhaustive search over all possible secrets and check which one satisfies the given shares.
Resistance:
-
The search space grows exponentially with \({q^n}\), making brute-force attacks computationally infeasible for large \(n\) and \(q\).
-
The structure of LCD codes ensures that only valid coalitions can reconstruct the secret, meaning that randomly guessing shares does not provide meaningful information.
Collusion attacks
Attack description:
In a collusion attack, multiple unauthorized participants combine their shares to attempt partial reconstruction of the secret.
Resistance:
-
The ramp secret sharing structure ensures that unauthorized coalitions below a certain threshold learn little or no information about the secret.
-
Increasing \(n\) and ensuring that minimal coalitions are strictly required for reconstruction further mitigates the risk of collusion.
4.7.1 Conclusion
The proposed scheme is designed to be resilient against common cryptographic attacks, leveraging the properties of LCD codes and weighing orthogonal matrices. However, further research could analyze its security under quantum attacks or explore adaptive adversary models.
4.8 Potential extensions
In this study, LCD codes and weighing orthogonal matrices were used to design multisecret-sharing schemes. However, other matrix-based approaches could also be explored to develop secure and efficient cryptographic systems:
-
Hadamard Matrices: Hadamard matrices, known for their strong orthogonality properties and high error tolerance, are widely used in encryption schemes and error-correcting codes. Utilizing Hadamard-based codes in secret sharing schemes could enhance security.
-
Circulant Matrices: Due to their recursive structure, circulant matrices offer low computational complexity. Their applications in encryption and data integrity verification make them a promising candidate for efficient secret sharing mechanisms.
-
Toeplitz Matrices: Toeplitz matrices are commonly used in linear prediction methods and fast signal processing algorithms. Incorporating them into multisecret-sharing schemes could support efficient secret distribution and reconstruction processes.
Exploring these alternative matrix structures in future research could lead to more secure and computationally efficient secret sharing schemes.
5 Performance evaluation
To measure the efficiency of the LCD-based scheme, we implemented a proof-of-concept in Python.
Metrics Evaluated:
1. Encryption Time: Time taken to generate and distribute secret shares.
2. Decryption Time: Time required to reconstruct the original secret from shares.
3. Memory Usage: The total memory consumed during encryption and decryption.
We conducted tests for different secret sizes (8‒bit, 32-bit, 128-bit, 256-bit, and 512-bit) to analyze the scalability of the proposed method.
5.1 Implementation details
To conduct the performance evalution, we implemented the following Python script:
Code 1 Python Code for LCD-Based Secret Sharing and Performance Measurement
import numpy as np
import galois
import time
import memory_profiler
import tracemalloc
def generate_lcd_code_gfq(k, n, field):
“““Generate an LCD generator matrix G in GF(q)”““
assert k < n, “k must be less than n for a valid code”
q = field.characteristic
while True:
W = field(np.random.randint(0, q, size = (k, n‒k)))
I_k = field(np.eye(k, dtype = int))
G=np.hstack((W, I_k))
GG_T = G @ G.T
det = np.linalg.det(GG_T)
if det! = 0:
return G
def generate_parity_check_matrix_gfq(G, k, n, field):
W=G[:,: n‒k]
I_nk = field(np.eye(n‒k, dtype = int))
H=np.hstack((-I_nk, W.T))
return H
# Function to generate secret shares
def distribute_secret(secret, G):
shares = secret @ G.T
print(f”G = {G.T.shape}, secret = {secret.shape}, shared = {shares.shape}”)
return shares
# Function to reconstruct the secret
def reconstruct_secret(shares, G, H, k, n, GF):
try:
zeros = GF(np.zeros(H.shape[0], dtype = np.int32)).reshape((1, H.shape[0])) y=np.hstack((shares, zeros))
GH=np.vstack((G, H))
GH_inv = np.linalg.inv(GH)
recovered_secret = GH_inv @ y.T
return recovered_secret.T
except np.linalg.LinAlgError:
return None
# Performance Testing Function
def benchmark_lcd_secret_sharing(n, GF):
q=GF.characteristic
# Measure Encryption (Sharing) Time & Memory
tracemalloc.start()
current, peak = tracemalloc.get_traced_memory()
start_time = time.time()
G = generate_lcd_code_gfq(n, 2*n, GF)
choose = GF(np.random.randint(0, q, size = (n, 1)))
secret = choose.T @ G # Random secret from codeword C
shares = distribute_secret(secret, G)
encryption_time = (time.time()‒start_time) * 1000
current_after, peak_after = tracemalloc.get_traced_memory()
encryption_peak_memory = peak_after/(1024 * 1024)
encryption_memory = encryption_peak_memory
tracemalloc.stop()
# Measure Decryption (Reconstruction) Time & Memory
tracemalloc.start()
current, peak = tracemalloc.get_traced_memory()
start_time = time.time()
H = generate_parity_check_matrix_gfq(G, n, 2*n, GF)
assert np.all(G @ H.T = = 0)
recovered_secret = reconstruct_secret(shares, G, H, n, 2*n, GF)
decryption_time = (time.time()‒start_time) * 1000
current_after, peak_after = tracemalloc.get_traced_memory()
decryption_peak_memory = peak_after/(1024 * 1024)
decryption_memory = decryption_peak_memory
tracemalloc.stop()
assert np.array_equal(secret, recovered_secret)
return encryption_time, decryption_time, \
encryption_memory, decryption_memory
q = 2
GF = galois.GF(q)
# Run the benchmark for different secret sizes
secret_sizes = [8, 32, 128, 256, 512]
results = {}
for secret_size in secret_sizes:
encryption_time, decryption_time, enc_mem, dec_mem = \
benchmark_lcd_secret_sharing(n = secret_size, GF=GF)
results[secret_size] = {
“Encryption Time (ms)”: encryption_time,
“Decryption Time (ms)”: decryption_time,
“Encryption Memory (MB)”: enc_mem,
“Decryption Memory (MB)”: dec_mem
}
# Print results
print(“\n = = = LCD-Based Secret Sharing Performance Results = = = “)
for size, metrics in results.items():
print(f”\nSecret Size: {size} bits”)
print(f”Encryption Time: {metrics[’Encryption Time (ms)’]:.2 f} ms”)
print(f”Decryption Time: {metrics[’Decryption Time (ms)’]:.2 f} ms”)
print(f”Encryption Memory Usage: {metrics[’Encryption Memory (MB)’]:.4 f} MB”)
print(f”Decryption Memory Usage: {metrics[’Decryption Memory (MB)’]:.4 f} MB”)
5.2 Benchmark results
The following tables summarize the encryption and decryption times (in milliseconds) and memory consumption (in megabytes).
Table 3 compares encryption and decryption times (in milliseconds) for different secret sizes. Smaller sizes result in lower times, while larger sizes increase processing time. The LCD-based scheme demonstrates low encryption and decryption times, making it computationally efficient.
Table 3
Encryption time comparison
Secret size (bits) | Encryption time (ms) | Decryption time (ms) |
|---|---|---|
8 | 214.90 | 7.45 |
32 | 58.03 | 34.04 |
128 | 258.40 | 114.88 |
256 | 251.97 | 353.12 |
512 | 863.65 | 1420.66 |
Table 4 compares memory usage, showing encryption and decryption memory consumption (in MB). The memory usage remains low, ensuring feasibility in resource-constrained environments.
Table 4
Memory usage comparison
Secret size (bits) | Encryption memory (MB) | Decryption memory (MB) |
|---|---|---|
8 | 1.1865 | 0.0129 |
32 | 0.0248 | 0.0565 |
128 | 0.2741 | 0.6408 |
256 | 1.0723 | 2.5344 |
256 | 4.2596 | 9.8307 |
5.3 Analysis and insights
1. Efficiency in Encryption and Decryption
-
The LCD-based method exhibits fast encryption and decryption times across all tested secret sizes.
-
It outperforms many polynomial-based secret sharing techniques in terms of speed.
2. Low Memory Usage
The scheme efficiently handles memory, making it suitable for embedded systems and IoT applications.
3. Scalability
As the secret size increases, the LCD-based method scales better than traditional schemes, maintaining a low computational overhead.
5.4 Conclusion
The experimental results demonstrate that the proposed LCD-based multisecret-sharing scheme:
-
Achieves fast encryption and decryption times for different secret sizes.
-
Consumes minimal memory, making it efficient for low-power environments.
-
Scales well with increasing secret sizes, proving its applicability in real-world cryptographic systems.
Future work
-
Extending the benchmarking to real-world cryptographic applications such as secure cloud storage and blockchain.
-
Comparing against Shamir’s Secret Sharing and other quantum-resistant secret sharing techniques.
6 Conclusion
In this paper, we proposed novel multisecret-sharing schemes based on LCD codes derived from weighing orthogonal matrices. We reviewed the fundamental concepts of linear codes, secret sharing schemes, and ramp secret sharing schemes, providing the necessary theoretical background for our constructions.
We introduced two new multisecret-sharing schemes:
1.
A scheme based on Euclidean LCD codes derived from weighing orthogonal matrices.
2.
A scheme based on LCD codes from skew-weighing orthogonal matrices.
For both schemes, we analyzed access structures, coalition statistics, security properties, and information-theoretic efficiency. Our results show that the proposed schemes:
-
Support a larger number of participants compared to existing schemes.
-
Have a higher number of minimal coalitions, enhancing security.
-
Achieve an information rate close to 1, making them nearly ideal.
A detailed comparison with existing schemes demonstrated that our methods provide superior security and efficiency while maintaining computational feasibility. The security of the proposed schemes depends on the parameters \(n\) and \(q\), where larger values enhance security but may increase computational costs.
The findings in this study highlight the practical applications of weighing orthogonal matrices in cryptographic protocols. Future research could focus on:
-
Optimizing computational efficiency for large-scale implementations.
-
Exploring alternative matrix constructions for improved security.
-
Applying these schemes in real-world cryptographic systems such as blockchain and secure cloud storage.
Additionally, we implemented a proof-of-concept in Python, benchmarking encryption time, decryption time, and memory usage. Our results confirmed the feasibility of LCD-based secret sharing for practical cryptographic use cases. Overall, the proposed schemes offer a promising approach to secure multisecret-sharing, leveraging LCD codes and weighing orthogonal matrices to achieve high security, efficiency, and scalability.
Declarations
Conflict of interest
The authors declare no conflict of interest.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
