基于LCD码的可验证多秘密共享方案

Verifiable Multi-Secret Sharing Scheme Based on LCD Code

摘要: 为了解决基于线性码的秘密共享在区块链数据隐私保护中容易受到Tompa-Woll攻击以及子秘密只能单次使用的问题，本文提出了一种基于LCD码的可验证多秘密共享方案。该方案旨在应对不诚实用户通过提供错误子秘密而导致诚实用户无法获取秘密的情况。考虑到秘密重构函数的线性特性和其易受Tompa-Woll攻击的特点，本文采用双变量单向函数进行验证，从而有效抵御不诚实用户的恶意行为，并实现子秘密的多次使用。与其他方案的比较结果表明，该方案在性能上优于现有解决方案。

Abstract: To address the vulnerability of linear code-based secret sharing in blockchain data privacy protection-specifically its susceptibility to Tompa-Woll attacks and the single-use limitation of sub-secrets-this paper proposes a verifiable multi-secret sharing scheme based on LCD codes. The scheme targets the issue where dishonest users can cheat by submitting incorrect sub-secrets, preventing honest users from successfully reconstructing the secret. Given the linear nature of the secret creconstruction function and its vulnerability to Tompa-Woll attacks, this paper utilizes a two-variable one-way function for verification, effectively countering malicious behavior from dishonest users. Additionally, the use of the two-variable one-way function enables the reuse of sub-secrets. Comparative results show that this scheme outperforms existing solutions in terms of performance.

1. 引言

秘密共享作为保护重要信息的工具，有广泛应用如：门限数字签名、安全多方计算、密钥协商和安全组播等。秘密共享最早由Shamir [1]和Blakley [2]在1979年分别基于拉格朗日插值多项式和超平面的点构造提出，基本思想为：将要共享的秘密通过分发算法将子秘密或份额分发给一组用户，当一定数量的诚实用户提交子秘密通过重构算法恢复秘密。所有能够恢复秘密的用户的集合称为访问结构。Asmuth等[3]基于中国剩余定理提出了门限秘密共享方案，该方案重构复杂度优于Shamir方案；Chien等[4]基于线性分组码、双变量单向函数提出多秘密共享方案，实现用户子秘密可多次使用；信息率也是秘密共享的一个重要概念，实质上是秘密的大小与用户子秘密大小的比例。当秘密的大小与用户子秘密大小相等时，称此方案是理想的。基于线性码的秘密共享方案其重构函数是线性易受Tompa-Woll攻击[5]。

本文基于LCD码和双变量单向函数，提出了一个可验证多秘密共享方案。本方案实现用户的子秘密可多次使用，减少计算与通信成本。

本文主要贡献如下所示：

1) 通过利用双变量单向函数，该方案具备了可验证性，使得用户能够有效识别接收到的子秘密的真实性，从而有效抵抗Tompa-Woll攻击。

2) 通过与现有的方案对比显示，该方案是理想的，能够同时具备可验证性、子秘密多次使用的功能。

本文相关工作：1981年McEliece等[6]发现秘密共享方案与Reed-Solomon码的关系。1993年Massey [7]基于线性码提出了完备的秘密共享方案并说明其访问结构的特征，访问结构与其对偶码的极小码字一一对应。2013年宋云等[8]基于极小线性码提出秘密共享方案；同年Tentu等[9]利用MDS码和单向函数提出了合取分成访问结构的秘密共享方案，其方案是理想的、计算上完备的。2020年Alahmadi等[10]利用LCD码的性质，即LCD码与其对偶码的交为零向量，提出了多秘密共享方案。Ghosh等[11]基于Alahmadi的方案进行改进，其共享的秘密与LCD码的码长相等。2024年伍高飞和张玉清[12]给出两类最优五元循环码，并基于五元循环码提出秘密共享方案。抵抗Tompa-Woll攻击有两种主要方法：第一类是在线性码的秘密共享方案的基础上添加可验证的功能；第二类是将线性码通过映射变成非线性码，基于非线性码提出秘密共享方案。2010年郭玉娟等[13]利用极小线性码链、离散对数和大素数分解提出动态可验证秘密共享方案，其计算开销大。2019年李富林等[14]利用Hamming 码和双变量单向函数提出了可验证多秘密共享方案，实现用户子秘密可重复使用。2020年Agrawal等[15]基于非线性码提出秘密共享方案，并给出基于非线性Nordstrom-Robinson码的秘密共享访问结构。2022年Agrawal等[16]利用Gray映射将$Z_4$ 环上的线性码映射成$F_2$ 上的非线性码，使用非线性码构造秘密共享方案。同年，Hossain等[17]利用循环码和双变量单向函数给出可验证多秘密共享方案。

本文结构：第1节介绍预备知识，第2节给出可验证多秘密共享方案的具体构造，第3节对提出的可验证多秘密共享方案进行安全分析，第4节是与相关工作进行对比分析，第5节对文章进行总结。

2. 预备知识

本节分别对秘密共享方案，LCD码，双变量单向函数，Tompa-Woll攻击进行简单的介绍。

2.1. 秘密共享方案

秘密共享方案由分发阶段和重构阶段构成。在分发阶段，诚实分发者dealer 执行分发算法将秘密s拆分成k个子秘密$s_1,s_2,\cdots ,s_k$ ,并将子秘密$s_i$ 共享给用户$P_i$ $\left(i=1,2,\cdots ,n\right)$ 。在重构阶段，任意大于等于k个用户可以用户重构秘密s，任意小于k个用户无法获得秘密的任何信息，其中任意大于等于k个用户构成的集合称为授权集，任意小于k个用户构成的集合称为非授权集。所有的授权集构成的集合称为访问结构$\Gamma$ ，如下所示：

$\Gamma =\left\{A|A\subseteq P,\left|A\right|\ge k\right\}。$

定义1 (完备的秘密共享方案[18])在n个用户集合中，共享秘密s，其访问结构为$\Gamma$ 。满足以下两个条件的秘密共享方案称为完备的秘密共享方案：

1) 正确性：对于任意授权子集$\gamma \in \Gamma$ ，$\gamma$ 中用户合作可以恢复秘密s。

2) 安全性：对于任意非授权子集$\eta \notin \Gamma$ ，$\eta$ 中用户合作得不到秘密s的任何信息。

2.2. LCD码

定义2 (线性码[19])设$F_q^n$ 是有限域$F_q$ 上n维向量空间。$\left(n,k\right)$ 码C是$F_q$ 上大小为k的子集。$\left(n,k\right)$ 码C是线性码当且仅当码C是$F_q$ 上k维线性子空间记作$\left[n,k\right]$ 。将$\left(c_n,c_1,\cdots ,c_{n-1}\right)\in F_q^n$ 称为码C的码字。

线性码有两种表达方式$C=\left\{\overrightarrow{v}G|\forall \overrightarrow{v}\in F_q^k\right\}=\left\{c\in F_q^n|H{c}^{\perp }=0\right\}$ ，其中G是线性码的生成矩阵，H是线性码的校验矩阵。

码C的对偶码$C^{\perp }$ 表示为$C^{\perp }=\left\{\overrightarrow{x}\in F_q^n|\overrightarrow{x}c=0,\forall c\in C\right\}$ 。当$C\subseteq C^{\perp }$ 成立时，称码C自正交。当$C=C^{\perp }$ 成立时，称码C自对偶。当$C\cap C^{\perp }=\left\{0\right\}$ 成立时，称码C为线性互补对偶码即LCD码。

定义3 (LCD码[20])令C为$\left[n,k\right]$ 线性码，G是其生成矩阵、H是其校验矩阵。码C为LCD码当且

仅当矩阵$G{G}^{\perp }$ 非奇异，当且仅当矩阵$\left(\begin{array}{l}G\\ H\end{array}\right)$ 非奇异。

2.3. 双变量单向函数

定义4 (双变量单向函数[18])。$f\left(x,y\right)$ 表示一个有两个变量的单向函数，能够将任意的x和y映射到固定的函数值。该函数有以下性质：

1) 已知x和y，$f\left(x,y\right)$ 易于计算。

2) 已知y和$f\left(x,y\right)$ ，求x在计算上是不可行的。

3) 在y未知的情况下，对于任意的x，难以计算$f\left(x,y\right)$ 。

4) 已知y的情况下，找到不同的$x_1$ 和$x_2$ 满足$f\left(x_1,y\right)=f\left(x_2,y\right)$ 是不可行的。

5) 已知x和$f\left(x,y\right)$ ，求y在计算上是不可行的。

6) 已知任意多的$\left(x_i,f\left(x_i,y\right)\right)$ 对，求$f\left(x^{\prime },y\right)$ 是不可行的，其中$x^{\prime }\ne x_i$ 。

2.4. Tompa-Woll攻击

以Shamir的门限秘密共享方案为例，假设分发者有多项式$f\left(x\right)=13+10x+2x^2$ ，其中秘密为$s=13$ 。假设有三个用户$\left\{P_1,P_2,P_3\right\}$ ，用户$P_1$ 得到的子秘密为$f\left(x_1\right)=f\left(1\right)=25$ ，用户$P_2$ 得到的子秘密为$f\left(x_2\right)=f\left(2\right)=41$ ，用户$P_3$ 得到的子秘密为$f\left(x_3\right)=f\left(3\right)=61$ 。则秘密s恢复如下：

$s=3f\left(x_1\right)-3f\left(x_2\right)+f\left(x_3\right)$ 。

秘密s恢复函数是用户$P_1,P_2,P_3$ 子秘密的线性组合。若用户$P_1$ 发起Tompa-Woll攻击，即用户$P_1$ 提交的子秘密为$f\left(x_1\right)+\epsilon$ ，其中$\epsilon$ 是只有用户$P_1$ 已知。则恢复的秘密s如下

$s^{\prime }=3\left(f\left(x_1\right)+\epsilon \right)-3f\left(x_2\right)+f\left(x_3\right)=s+3\epsilon$ 。

用户$P_1,P_2,P_3$ 分别拿到秘密$s^{\prime }$ 由于用户$P_1$ 已知$\epsilon$ ，于是用户$P_1$ 可以恢复的真正秘密s。

3. 方案构造

本文利用LCD码其性质和双变量单向函数给出一个可验证门限多秘密共享方案，其中本方案实现用户的子秘密可多次使用。本方案主要由初始化、子秘密生成、重构、验证、子秘密多次使用算法构成，具体实现过程如下所示：

算法1 初始化算法

1) 诚实分发者dealer，随机选取$F_q$ 上长为n的LCD码，其生成矩阵为G。随机选取r和双变量单向函数$f\left(x,y\right)$ ，公开$f\left(r,y\right)$ 。n个用户集为$\left\{P_1,P_2,\cdots ,P_n\right\}$ 。

2) 诚实分发者dealer设置k个秘密分别为$S=\left(s_1,s_2,\cdots ,s_k\right)$ 。

算法2 子秘密生成算法

1) 用户$P_i$ 选择一个$1\times k$ 的向量${\overrightarrow{l}}_i=\left(c_{i1},c_{i2},\cdots ,c_{ik}\right)$ ，利用公开的双变量单向函数计算 $\left(f\left(r,c_{i1}\right),f\left(r,c_{i2}\right),\cdots ,f\left(r,c_{ik}\right)\right)$ ，将$\left(f\left(r,c_{i1}\right),f\left(r,c_{i2}\right),\cdots ,f\left(r,c_{ik}\right)\right)$ 记为$f\left(r,{\overrightarrow{l}}_i\right)$ 。

2) 用户$P_i$ 将$f\left(r,{\overrightarrow{l}}_i\right)$ 发给诚实分发者dealer。记$G{G}^{\text{T}}{S}^{\text{T}}=\overrightarrow{y}$，诚实分发者将$\overrightarrow{y}$ 公开。

算法3 秘密重构与验证算法

1) 假设任意k个用户集为$\left\{P_{v_1},P_{v_2},\cdots ,P_{v_k}\right\}$ 合作恢复秘密，诚实分发者公开

$\overrightarrow{X}=f\left(r,{\overrightarrow{l}}_{v_1}\right)+f\left(r,{\overrightarrow{l}}_{v_2}\right)+\cdots +f\left(r,{\overrightarrow{l}}_{v_k}\right)$ 。

2) 用户$P_{v_i}$ 给用户$P_{v_j}$ 自己的伪子秘密$f\left(r,{\overrightarrow{l}}_{v_i}\right)$ ，合作恢复秘密的用户将伪子秘密相加${\overrightarrow{X}}^{\prime }={\displaystyle \sum _{i=1}^{k}f\left(r,{\overrightarrow{l}}_{v_i}\right)}$ ，

验证$\overrightarrow{X}={\overrightarrow{X}}^{\prime }$ 等式是否成立。若等式不成立停止协议。若等式成立继续执行协议。

3) 用户$P_{v_i}$ 利用公开的$\overrightarrow{y}$ 与收集到的伪子秘密$f\left(r,{\overrightarrow{l}}_{v_i}\right)$ ，计算$f\left(r,{\overrightarrow{l}}_{v_i}\right)\overrightarrow{y}=x_{v_i}$ ，$\left(1\le i\le k\right)$ 。

4) 考虑线性方程组$f\left(r,{\overrightarrow{l}}_{v_i}\right)G{G}^{\text{T}}{S}^{\text{T}}=x_{v_i}$，由于$G{G}^{\text{T}}$ 是非奇异且秩为k。线性方程组有唯一解，因此秘密$S=\left(s_1,s_2,\cdots ,s_k\right)$ 被恢复。

算法4 子秘密多使用性算法

当秘密$S=\left(s_1,s_2,\cdots ,s_k\right)$ 从更新为$S^{\prime }=\left({s^{\prime }}_1,{s^{\prime }}_2,\cdots ,{s^{\prime }}_k\right)$ ，分发者重新公开$G{G}^{\text{T}}{S^{\prime }}^{\text{T}}={\overrightarrow{y}}^{\prime }$用户$P_{v_i}$ 利用公开的${\overrightarrow{y}}^{\prime }$ 与收集到的伪子秘密$f\left(r,{\overrightarrow{l}}_{v_i}\right)$ $\left(1\le i\le k\right)$ ，计算$f\left(r,{\overrightarrow{l}}_{v_i}\right){\overrightarrow{y}}^{\prime }={x^{\prime }}_{v_i}$ 。考虑新的线性方程组$f\left(r,{\overrightarrow{l}}_{v_i}\right)G{G}^{\text{T}}{S^{\prime }}^{\text{T}}={x^{\prime }}_{v_i}$，由于$G{G}^{\text{T}}$ 是非奇异且秩为k。线性方程组有唯一解，因此秘密$S^{\prime }=\left({s^{\prime }}_1,{s^{\prime }}_2,\cdots ,{s^{\prime }}_k\right)$ 被恢复。实现用户的子秘密可多次使用。

4. 安全分析

本节通过定理1与定理2证明所提出的动态可验证多秘密关系方案，满足正确性与安全性。

定理1 (正确性分析) 设$\left\{P_1,P_2,\cdots ,P_n\right\}$ 是用户集合，任意k个用户可以恢复秘密。

证明：任意k个诚实用户利用公开的$\overrightarrow{y}$ 与收集到的伪子秘密$f\left(r,{\overrightarrow{l}}_{v_i}\right)$ $\left(1\le i\le k\right)$ ，计算$f\left(r,{\overrightarrow{l}}_{v_i}\right)\overrightarrow{y}=x_{v_i}$ 。由于矩阵G是LCD码的生成矩阵，于是$G{G}^{\text{T}}$ 是非奇异且秩为k。线性方程组$f\left(r,{\overrightarrow{l}}_{v_i}\right)G{G}^{\text{T}}{S}^{\text{T}}=x_{v_i}$有唯一

解，因此秘密$S=\left(s_1,s_2,\cdots ,s_k\right)$ 被恢复。于是任意k个用户合作可以恢复秘密。

定理2 (安全性分析) 设$\left\{P_1,P_2,\cdots ,P_n\right\}$ 是用户集合，任意$k-1$ 个用户得不到秘密的任何信息。

证明：任意$k-1$ 个用户利用公开的$\overrightarrow{y}$ 与收集到的伪子秘密$f\left(r,{\overrightarrow{l}}_{v_i}\right)$ $\left(1\le i\le k-1\right)$ ，计算$f\left(r,{\overrightarrow{l}}_{v_i}\right)\overrightarrow{y}=x_{v_i}$ 。由于矩阵G是LCD码的生成矩阵，于是$G{G}^{\text{T}}$ 是非奇异且秩为k。线性方程组$f\left(r,{\overrightarrow{l}}_{v_i}\right)G{G}^{\text{T}}{S}^{\text{T}}=x_{v_i}$有无穷

多解。于是任意$k-1$ 个用户合作得不到秘密的任何信息。

抵抗Tompa-Woll攻击：

若用户$P_{v_i}$ 发起Tompa-Woll攻击，提交伪子秘密为$f\left(r,{\overrightarrow{l}}_{v_i}\right)+\epsilon$ ，其中$\epsilon$ 是用户$P_{v_i}$ 已知。在重构阶段参与重构的用户将伪子秘密相加得${\overrightarrow{X}}^{\prime }=\overrightarrow{X}+\epsilon$ 与分发者公开的$\overrightarrow{X}$ 不相等，则用户集$\left\{P_{v_1},P_{v_2},\cdots ,P_{v_k}\right\}$ 有人提交假的子秘密，停止协议。可以抵抗用户$P_{v_i}$ 发起的Tompa-Woll攻击。

5. 方案对比

本文利用LCD码和双变量单向函数提出一个可验证多秘密共享方案。该方案是理想的且能有效抵抗Tompa-Woll攻击，实现用户子秘密的多次使用。当秘密向量更新时，分发者只需要重新公开新的$\overrightarrow{y}$ 即可。表1给出了基于LCD码多秘密共享方案的功能性比较。

表1给出Alahmadi和Ghosh方案与本文方案功能性比较。文献[10]将码字作为要共享的秘密，利用LCD码生成矩阵的性质解线性方程组。此方案不能实现用户子秘密多使用性，且不能验证用户是否诚实提交子秘密。文献[11]基于LCD码构造的方案适用于有限域$F_q$ 与局部环R上，共享的秘密与码字等长。此方案是完备的，但不能实现用户子秘密多使用性，且不能验证用户是否诚实提交子秘密。

表1分别通过与Alahmadi和Ghosh方案的比较，说明了本方案在，用户子秘密多使用性，验证性等方面性能优势。

Table 1. Functional comparison of multi secret sharing schemes based on LCD codes

表1. 基于LCD码多秘密共享方案功能性比较

方案	子秘密多使用	可验证
Alahmadi [10]	×	×
Ghosh [11]	×	×
本文方案	√	√

符号说明：√表示具备性质；×表示不具备性质。

6. 总结

本文利用LCD码和双变量单向函数提出一个可验证多秘密的秘密共享方案，该方案是理想的且能有效抵抗Tompa-Woll攻击，实现用户子秘密的多次使用。与其他方案相比，该方案加强功能以及降低计算开销。

基金项目

福建省高校产学合作科技计划项目(2023H6012)。

NOTES

^*通讯作者。