基于 LCD 子空间码的多秘密共享方案

《Discrete Mathematics》：Multisecret-sharing scheme using LCD subspace codes

　　

摘要
2023 年，作者引入了 LCD 子空间码，推广了 LCD 码的概念。最近，在 2025 年，?alkavur 和 Solé 提出了基于 LCD 码的多重秘密共享方案。在本文中，我们设计了一种使用 LCD 子空间码的多重秘密共享方案。所提出的方案是一种匿名的 (k,k)-阈值方案，并继承了底层 LCD 子空间码的纠错能力。我们分析了方案的安全性，包括其抵抗联盟攻击和暴力攻击的能力，并讨论了其计算复杂度。与现有的基于码的多重秘密共享方案相比，所提出的方案实现了显著更大的秘密空间和更高的信息率。提供了一个 F3 上的例子来说明构造。

1. 引言
多重秘密共享方案是一种技术，用于将 n 个秘密 ??1,??2,...,???? 分配给一组参与者，允许同时分配和重构多个秘密。这是分发者在参与者中分发秘密份额的框架的自然且重要的推广，使得只有某些授权的参与者子集才能重构原始秘密。秘密共享方案的概念由 Blakley [3] 和 Shamir [14] 于 1979 年提出，如今，秘密共享方案在现代密码学中起着重要作用。
线性码已被证明是构建秘密共享方案的有力工具。在 [13] 中，Massey 给出了线性码与秘密共享之间的联系，表明秘密共享方案的访问结构由对偶码的最小码字决定。在此基础上，文献中提出了几种基于码的多重秘密共享方案。2017 年，?alkavur 和 Solé ([6]) 利用线性码的有界距离译码构造了多重秘密共享方案。在 [2] 中，Alahmadi 等人提出了一种基于 LCD 码的多重秘密共享方案，分析了其访问结构和联盟统计信息。最近，?alkavur 和 Solé 提出了基于线性互补对偶码的多重秘密共享方案，即通过使用权重矩阵获得的 LCD 码（见 [5]），提供了详细的安全性和性能分析。
线性互补对偶码，称为 LCD 码，由 Massey [13] 引入，由于其在水密码学、数据存储和通信系统中的应用而引起了广泛关注。如果 ?? ∩??⊥= {0}，其中 ??⊥ 表示 C 的对偶码，则线性码 C 称为 LCD 码。这种结构特性确保了高效的编码和译码，同时提供对某些类型攻击的鲁棒性，使 LCD 码特别适合密码学应用。
2000 年，Ahlswede、Cai、Li 和 Yeung 引入了网络编码（见 [1]）。网络被建模为由源顶点、内部（中间）顶点和汇顶点组成的有向多重图。与传统编码不同，网络编码允许在中间顶点混合数据。当数据表示为有限域上的向量且混合操作限制为线性变换时，产生了一类特别重要的网络编码。这个框架被称为线性网络编码。2008 年，K?tter 和 Kschischang 提出了进一步的信息传输，通过考虑传输向量张成的向量子空间而不是向量本身来进行信息传输（见 [12]）。由此产生的码被称为子空间码。
在 [8] 中，作者引入了 LCD 子空间码，并展示了使用关联方案的公平划分构造 LCD 子空间码的方法。此外，在 [8] 中，作者展示了使用相互无偏称量矩阵构造 LCD 子空间码的方法，在 [7] 中，作者使用相互准无偏称量矩阵、对称设计的关联系统、对称群可分设计的关联系统、Deza 图及其公平划分。
在本文中，我们设计了一种基于 LCD 子空间码的多重秘密共享方案。本文组织如下。在第 2 节中，我们给出相关的背景信息。在第 3 节中，我们呈现基于 LCD 子空间码的多重秘密共享方案。安全性和性能分析分别在第 4 节和第 5 节中给出。在第 6 节中提供了一个数值例子，并在第 7 节中给出了与现有方案的比较。在第 8 节中，我们给出了结论。

2. 预备知识
我们简要回顾本工作所需的符号和基本概念。编码理论的标准参考书目包括 [11]，而关于子空间编码最新发展的概述可在 [9], [10] 中找到。全文中，???? 表示阶为 q 的有限域，其中 q 是一个素数幂。

2.1. 线性码和 LCD 码
设 n 和 k 为正整数。???? 上长度为 n 维数为 k 的线性码 C 定义为 ?????? 的一个 k 维向量子空间。如果 C 的不同码字之间的最小汉明距离等于 d，则 C 被称为 [??,??,??]?? 线性码。
行构成 C 的基的矩阵 ?? ∈????×???? 称为 C 的生成矩阵。C 的对偶码由 ??⊥={??∈??????|〈??,??〉=0 对于所有 ??∈??} 给出，其中 〈??,??〉= ∑????=1????????? 表示 ?????? 上的标准欧几里得内积。
如果 ?? ∩??⊥= {0}，则线性码 C 被称为线性互补对偶码，或者是 LCD 码。这类码由 Massey 在 [13] 中引入，随后在密码学和信息安全等领域找到了应用。设 G 为 C 的生成矩阵。当且仅当矩阵 ?????? 在 ???? 上非奇异时，即当且仅当 ???? 中 det?(??????) ≠0 时，码 C 才是 LCD 码。

2.2. 子空间码
子空间码 ?? 是 ?????? 的子集的非空集。在这个框架中，每个码字本身就是一个线性码。子空间码最常用的距离度量是子空间距离，对于 ??,?? ∈?? 定义为
(1)?????(??,??)=dim?(??+??)?dim?(??∩??).
然后 ?? 的最小距离由 ???(??)=min?{?????(??,??)|??,??∈??,??≠??} 给出。
如果包含在 ?????? 中的码字的子空间码 ?? 的最小距离等于 d，且其码字的维数集合包含在 ?? ?{0,1,…,??} 中，则称该码具有参数 (??,|??|,??;??)??。当 ??= {??} 时，码 ?? 称为恒定维数码，记为 (??,|??|,??;??)??。否则，?? 被称为混合维数码，有时简写为 (??,|??|,??)??。恒定维数码可被视为经典恒定重量码的 q-模拟，并已得到广泛研究。

2.3. LCD 子空间码
LCD 子空间码的概念在 [8] 中引入。如果对于所有 ????,????∈?? 有 ????∩??⊥??={0}，则子空间码 ?? 被称为 LCD 子空间码。特别是，LCD 子空间码的每个码字本身就是一个 LCD 线性码。
设 ??= {??1,??2,…,????} 为 (??,??,??;??)?? 子空间码，并设 ???? 为 1 ≤?? ≤?? 的 ???? 的生成矩阵。如果矩阵 ?????????? 在 ???? 上对于所有 1 ≤??,?? ≤?? 均非奇异，则 ?? 是一个 LCD 子空间码。此类码的显式例子和构造可在 [7], [8] 中找到。

2.4. 秘密共享方案
秘密共享是密码学中用于将机密信息分配给一组参与者的技术术语，使得只有授权组能够恢复秘密。它通常包括一个要保护的秘密、一个生成和分配份额的分发者、持有这些份额的一组参与者，以及指定哪些参与者子集被授权重构秘密的访问结构。
(??,??)-阈值方案指的是一种秘密共享方案，其中任何至少包含 t 个参与者的子集都可以恢复秘密，而任何少于 t 个参与者的子集都不会透露任何信息。
多重秘密共享方案通过允许在同一组参与者之间同时共享多个秘密来推广这种设置，可能是在不同的访问结构下。

3. 基于 LCD 子空间码的多重秘密共享方案
在本节中，我们描述了一种由恒定维数 LCD 子空间码构造的多重秘密共享方案。该方案利用 LCD 子空间的代数性质实现多个秘密的安全分配和重构。
设 ?? 为 ???? 上具有参数 (??,|??|,??;??)?? 的恒定维数 LCD 子空间码。?? 的每个码字都是 ?????? 的 k 维线性子空间，并满足 LCD 性质。
秘密空间定义为 ???? 上所有秩为 k 的 ?? ×?? 矩阵的集合。一个秘密等同于 ?????? 中属于 LCD 子空间码 C 的 k 维子空间的一个无序基。
选择一个秘密 G，它是子空间码 ?? 的某个码字 C 的生成矩阵。设 ??1,??2,…,???? 为矩阵 G 的行，即生成线性码 C 的向量。秘密是一个无序基 {??1,??2,…,????}，即可以通过置换 G 的行获得的任何矩阵。此外，设 H 为 C 的校验矩阵。
为了分配份额，分发者随机选择一个码字 ??1 ∈?? 以及一个生成矩阵 ??1 ∈????×????。对于每个 ?? ∈{1,2,…,??}，分配给第 i 个参与者的份额是定义在 ?????? 中的向量 ????
?????=??1??????.
秘密 ???? ??= 1,2,…,?? 通过求解方程组恢复
??1???????=??????,
?????????=0.
由于 ?? 是一个 LCD 子空间码，[??1??] 是一个可逆矩阵，确保秘密 ????, ??= 1,2,…,?? 可以被唯一重构。整个系统可以表示如下
??1?????=????,
???????=0,
其中 Y 是 ?? ×?? 矩阵，其第 ?? 行为 ????。

3.1. LCD 子空间码的构造
可用于本文所述多重秘密共享方案的 LCD 子空间码的例子可在 [7], [8] 中找到。定理 1，定理 2 给出了一种从满足某些条件的整数方阵构造 LCD 子空间码的一般方法（见 [7]）。

定理 1[7] 设 ??= {??1,??2,…,????} 为一组整数 ?? ×?? 矩阵，并设 p 为整除 ?????????? 的任意 ??,?? ∈{1,2,…,??} 的项的素数。此外，设 ???? 为特征为 p 的阶为 q 的有限域。那么矩阵 ????,??= [?????????], ?? ∈???? ?{0} 的行空间集合，其中 X 是由矩阵 ????, ??= 1,2,…,?? 张成的线性空间的非零元素，是 LCD 子空间码 ?? ???2?????。

设 A 为 ?? ×?? 实矩阵，其行和列由集合 ??= {1,2,…,??} 索引，并设 Π= {??1,??2,…,????} 为 X 的划分。我们根据 Π 将矩阵 A 划分为块 ??= [???????]，对于 1 ≤??,?? ≤??，其中 ??????? 是由 ???? 中的行和 ???? 中的列索引的子矩阵。设 ??????? 表示块 ??????? 的平均行和。矩阵 ??= [???????] 称为 A 的商矩阵。如果每个块 ??????? 具有常数行和，则划分 Π 称为行公平的；如果每个块 ??????? 具有常数块和，则称为列公平的。如果 Π 既是行公平又是列公平，则 Π 称为公平划分。

以下定理给出了从整数方阵的公平划分构造 LCD 子空间码的方法。

定理 2[7] 设 ??= {??1,??2,…,????} 为一组整数 ?? ×?? 矩阵，并设 p 为整除 ?????????? 的任意 ??,?? ∈{1,2,…,??} 的项的素数。此外，设 Π 为集合 S 的一个公平划分，具有 t 个相同长度 ???? 的单元，并设 ??′?? 表示相对于 Π 的 ???? 的对应商矩阵，??= 1,2,…,??。设 ???? 为特征为 p 的阶为 q 的有限域。那么矩阵 ????,??= [?????????], ?? ∈???? ?{0} 的行空间集合，其中 X 是由矩阵 ??′1,??′2,…,??′?? 张成的线性空间的非零元素，是 LCD 子空间码 ?? ???2?????。

4. 安全性分析
在本节中，我们分析本文介绍的多重秘密共享方案的安全性属性。

4.1. 阈值安全性
描述的方案是一种 (??,??)-阈值多重秘密共享方案，因为只有当知道矩阵 G 的所有 k 行（即来自码字 C 的基的向量）时，秘密才能被恢复。如果我们取 G 的行的向量为 C 的向量，使得任何 k-行子集都是 C 的基，我们可以产生一个 (??,??)-阈值多重秘密共享方案，对于 ?? ≤?? ≤??。

4.2.

对联盟攻击的抵抗力

让我们考虑一个问题，其中由 c 个参与者组成的联盟（其中 c < k）试图重构秘密。这 c 个参与者可以揭示向量子空间（码字）C 的 c 个生成元 ??1,??2,…,????。此外，如果我们计算集合 {??1,??2,…,????} 可以扩展为 C 的基的方式的数量，我们得到以下结果：
Π???1??=0?(?????????)(?????)!Π???1??=0?(?????????)。
因此，由 c 个参与者（?? ≤ ??）组成的联盟能够重构秘密的概率为
(?????)!Π???1??=0?(?????????)Π???1??=0?(?????????)。
因此，方案的安全性取决于 n、k 和 q 的选择。较大的 n 和 q 会增加安全性，但也会增加计算复杂性。较大的 k 会影响访问结构，即增加了能够重构秘密的最小联盟规模。

4.3. 对暴力攻击的抵抗力

设 ?? 为参数为 (??,#??,??;??)?? 的 LCD 子空间码。码字 ?? ∈?? 中所有可能秘密的数量，即 C 中基的数量为
(?????1)?(???????)…(??????????1)??!。
因此，?? 中所有可能秘密的数量（直到行置换）为
#???(?????1)?(???????)…(??????????1)??!。
随着 q 和 k 的增加，可能基的数量（即秘密的候选者）迅速增长，从而扩大了搜索空间，使攻击者越来越难以恢复秘密。潜在秘密数量的这种增长，直接增强了方案的安全性。

4.4. 匿名性

如果秘密可以在不知道哪个参与者持有哪些份额的情况下被重构，则称该秘密共享方案是匿名的（见 [4]）。由于秘密是一个无序基 {??1,??2,…,????}，即矩阵 G 直到行置换，本文介绍的方案是匿名的。

4.5. 容错性

在多秘密共享方案中，秘密的重构是通过合并参与者持有的份额来完成的。在实际环境中，由于传输错误或恶意干扰，其中一些份额可能被破坏。通过采用具有适当纠错能力的 LCD 子空间码，可以在重构阶段之前检测并纠正这些错误。只要受损份额的数量不超过底层 LCD 子空间码的纠错能力，原始秘密就可以被唯一恢复，从而保持方案的完整性。

5. 性能分析

在本节中，我们从信息率和计算复杂性的角度分析所提出的多秘密共享方案的效率。

5.1. 信息率

秘密共享方案的信息率定义为秘密的大小与单个参与者份额大小之比。在上述方案中，信息率为 n，因为秘密是一个 ?? ×?? 矩阵，表示向量空间 ?????? 中 k 维子空间 C 的基，而单个参与者的份额是向量空间 ?????? 中的一个向量。

5.2. 计算复杂性

方案中的两个主要操作是份额生成和秘密重构。
为每个参与者 ?? ∈{1,…,??} 计算份额 ?????= ??1?????? 需要将一个 ?? ×?? 矩阵与一个长度为 n 的向量进行矩阵 - 向量乘法，这在 ???? 中需要 ???(?????) 次操作。由于有 k 个参与者，份额生成的总成本为 ???(??2???)。
恢复每个秘密向量 ???? 需要求解 ?? ×?? 线性系统????????=[?????0]，其中 ??= [??1??] 是一个 ?? ×?? 矩阵。由于 M 在 ???? 上可逆，该系统可以使用高斯消元法在 ???(??3) 次操作中求解，或者如果预计算了 ???1 并复用于所有 k 个秘密，则可以在 ???(??2) 次操作中求解。因此，整体重构成本为 ???(??3)，或者在预计算的情况下为 ???(?????2)。
参数 n、k 和 q 的选择平衡了安全性和效率。较大的值增强了安全性，但增加了计算成本。

6. 示例

在本节中，我们用有限域 ??3 上的一个小示例来说明该方案。设 ?? 为 ??3 上参数为 (4,|??|,??;2)3 的恒定维数 LCD 子空间码。假设交易商选择了一个码字 ?? ∈??，其生成矩阵为
??=[00111111]。
两个行向量
??1=(0,0,1,1),??2=(1,1,1,1)
构成了 C 的基，秘密是无序基 {??1,??2}。C 的校验矩阵（即 ??⊥ 的生成矩阵）由
??=[00121212] 给出。
有 ??= 2 个参与者。交易商随机选择第二个码字 ??1 ∈??，其生成矩阵为
??1=[00111112]。
由于 ?? 是一个 LCD 子空间码，矩阵 ??1???? 必须是非奇异的：
??1????≡[2202]?(mod?3)，
行列式为 2 ?2? 2?0= 4 ≡1 ?0 ?(mod ?3)。
参与者 i (??= 1,2) 的份额是向量 ?????= ??1??????∈??23：
???1=??1????1=[00111112]??? ? ? ??0011?? ? ? ??=[20]?(mod?3)，
???2=??1????2=[00111112]??? ? ? ??1111?? ? ? ??=[22]?(mod?3)。
因此，参与者 1 持有份额 ??1= (2,0)，参与者 2 持有 ??2= (2,2)，两者均为 ??23 中的向量。为了恢复秘密向量 ????，参与者将他们的份额 ???? 与公开信息 ??1 和 H 结合，以求解线性系统
[??1??]??????=[?????0]。
组合后的 4 ×4 系数矩阵为
??=[??1??]=?? ? ? ??0011111200121212?? ? ? ??，
det?(??) ≡2 ?(mod ?3) ≠0，因此 M 在 ??3 上可逆。它在 ??3 上的逆矩阵为
???1=?? ? ? ??0222020120202010?? ? ? ??。
将 ???1 应用于每个右端项可以唯一地恢复秘密：
???1=???1?(2,0,0,0)?≡(0,0,1,1)?，
???2=???1?(2,2,0,0)?≡(1,1,1,1)?。
这两个向量与原始秘密完全匹配。

7. 与其他方案的比较

在本节中，我们将本文介绍的多秘密共享方案与一些现有的基于码的秘密共享方法进行比较。我们从参与者数量、秘密大小、联盟数量和信息率方面对它们进行比较。比较结果见表 1。

表 1. 与其他方案的比较。

| 方案 | 参与者数量 | 秘密大小 | 联盟数量 | 信息率 |
| :--- | :--- | :--- | :--- | :--- |
| Massey, [13] | n ? 1 | q^n | (?? ??) | 1 |
| ?alkavur, Solé [6] | n | q^k | ≥ (?? ?????) | 1 |
| Alahmadi et al. [2] | q^k | q^n | ∏???1??=0(?????????)??! | ????+1 |
| ?alkavur, Solé [5] | q^n | q^(2n) | ∏???1??=0(?????????)??! | ????+1 |
| Crnkovi? and ?vob, 2026 | k | q^(kn) | #?? ? ∏???1??=0(?????????)??! | n |

本文介绍的方案与其他方案之间的根本区别在于用作底层码的代数对象，因为本文介绍的泛化提供了更丰富的代数设置。
由于 LCD 子空间码自然地源于线性网络编码 [8]，我们的方案继承了在网络编码环境中的自然解释，其中信息作为子空间而不是固定向量传输。份额和秘密可以在网络上传输，而不需要指定的源到汇信道，使得该方案适用于分布式网络场景。
此外，所提出的方案只需要 k 个参与者，而诸如 [5] 等方案最多需要 ???? 个。大小为 ??????? 的秘密空间比所有比较的方案都要大得多，增强了对暴力攻击的抵抗力。最小联盟的数量获得了额外的 #?? 因子，反映了底层子空间码结构的丰富性，这是任何经典的基于 LCD 码的方案所不具备的。最后，信息率等于 n，这显著高于所有比较的方案，使得所提出的方案在少量参与者之间共享大秘密时特别高效。

8. 结论

在本文中，我们使用 LCD 子空间码构建了一个多秘密共享方案。该方案是一个 (??,??)-阈值多秘密共享方案，具有匿名性，继承了底层 LCD 子空间码的纠错能力，并能抵抗联盟和暴力攻击，其安全性由参数 n、k 和 q 控制。与现有的基于码的方案相比，它只需要 k 个参与者，同时实现了更大的秘密空间 (???????) 和更高的信息率 (n)，使得它在小组中共享大秘密时特别高效。

资助

本工作得到了克罗地亚科学基金会在项目编号 HRZZ-IP-2022-10-4571 下的支持，以及欧盟 - 下一代欧盟的支持，项目编号 uniri-iz-25-46-KonGeoGraGru。

Dean Crnkovi?|Andrea ?vob