基于多项式插值的多部门限秘密共享方案 Multipartie Threshold Secret Sharing Scheme Based on Polynomial Interpolation

doi:10.12677/PM.2022.1212228

Pure Mathematics
Vol. 12 No. 12 ( 2022 ), Article ID: 59744 , 9 pages
10.12677/PM.2022.1212228

基于多项式插值的多部门限秘密共享方案

林苇婷，林昌露

●How to Cite this Article

福建师范大学数学与统计学院，福建福州

收稿日期：2022年11月23日；录用日期：2022年12月22日；发布日期：2022年12月29日

摘要

在门限秘密共享方案中，一个参与者集合是否能恢复主秘密，取决于参与重构的参与者数量。在某种情况下，仅由一组参与者就能恢复主秘密，权限会相对过于集中。为了避免该问题，本文将一个大集合的参与者划分为几个不相交分区，每个分区都有一个独立部分访问结构；只有满足所有部分访问结构的参与者集合，才能恢复主秘密，否则得不到主秘密的任何信息。基于Shamir门限秘密共享方案和自由群中短词排序，本文构造了新的多部门限秘密共享方案，该方案可实现主秘密的动态更新，避免主秘密改变时分发阶段的通信需求，使整个方案在更新主秘密时更加高效。

关键词

门限秘密共享，自由群，信息熵，短词排序，主秘密更新，多项式插值

Multipartie Threshold Secret Sharing Scheme Based on Polynomial Interpolation

Weiting Lin, Changlu Lin

College of Mathematics and Statistics, Fujian Normal University, Fuzhou Fujian

Received: Nov. 23^rd, 2022; accepted: Dec. 22^nd, 2022; published: Dec. 29^th, 2022

ABSTRACT

In the threshold secret sharing scheme, whether a set of participants can recover the secret depends on the number of participants participating in the reconstruction. In some cases, only one group of participants can recover the secret, and the authority will be relatively centralized. To avoid this problem, the participants of a large set are divided into several disjoint partitions, each partition has an independent part access structure; only the set of participants meeting all partial access structures can recover the secret, otherwise no information of the secret can be obtained. Based on Shamir threshold secret sharing scheme and shortlex order in the free group, this paper constructs a new multipart threshold secret sharing scheme. This scheme can realize the dynamic update of the secret, avoid the communication requirements of the time transmission phase when the secret changes, and make the whole scheme more efficient when updating the main secret.

Keywords:Threshold Secret Sharing, Free Group, Information Entropy, Shortlex Order, Secret Updating, Polynomial Interpolation

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

信息技术日新月异，密码学成为网络空间安全的重要技术之一；秘密共享作为密码学领域最重要的内容之一，受到广泛的关注和研究。1979年，Shamir [1] 和Blakley [2] 分别基于有限域上的多项式和超几何平面的射影定理构造了两种门限秘密共享方案，对于现代密码学的研究具有重要作用。一般地，秘密共享方案分为两个算法：分发算法和重构算法。在分发算法中，分发者将主秘密分成若干个份额，并通过安全信道分发给参与者。在重构算法中，若干参与者将各自份额发送给重构者即可恢复主秘密；这些参与者的集合称为授权集，所有授权集的集合称为访问结构。

秘密共享方案可分为多种类型，如门限秘密共享方案 [1] [2]，多部秘密共享方案 [3] [4] [5] [6] 和门限可变秘密共享方案 [7] [8]，等等。在多部秘密共享方案中，参与者被划分为几个不相交的分区，每个分区都有一个部分访问结构。若一个参与者集合满足所有的部分访问结构，则该参与者集合就可以恢复主秘密；但只要存在一个或多个分区不满足其相应的部分访问结构，则该参与者集合就不能获得正确的主秘密。多部访问结构在秘密共享方案的研究中备受关注，它是门限秘密共享的自然推广；它并不是对给定子集中的参与者数量设置一个门限条件，而是对每个分区子集中的参与者数量施加一个更小的门限条件 [9]。因为参与者众多且分在不同的分区，故多部秘密共享方案在主秘密分发过程需要较大的通信量。分层秘密共享方案是多部秘密共享方案的一种特殊情形。后者的每个访问结构都具备相同的权限和等级；前者的不同分区也是表示不同访问结构，但是它们之间的优先级不相同。

1988年，Simmons等 [10] 最先提出了多部访问结构，给出了相应访问结构和分层访问结构的定义，并分析两者定义的异同点。同年，Brickell等 [11] 提出了一种构建理想的多部秘密共享方案方法，实现了分层和多部的访问结构；因为需要指数运算得到非奇异矩阵，故该方案效率低下。2007年，Tassa等 [12] 基于Birkhoff插值设计了分层门限访问结构，其中插值矩阵必须满足Polya条件。然而，Polya条件只是一个必要条件，而不是一个充分条件；当分配身份和份额给参与者时，分发者必须执行指数级运算验证插值矩阵是否满足Polya条件，其效率较低。同年，Farras等 [9] 对理想的多部访问结构给出了全面描述，但他们没有设计一个理想的秘密共享方案来实现其多部访问结构。Farras等提出一个公开问题：是否存在有效的方法从多部拟阵表示中实现理想的多部秘密共享方案。2014年，Hsu等 [13] 基于中国剩余定理设计了一个多部访问结构方案，但是该方案不是理想的多部访问结构，且无法实现主秘密的更新。2016年，Harsha等 [14] 利用背包和问题中的超递增序列实现了可更新主秘密的多部门限秘密共享方案构造，但是由于该方案是基于整数规划求解问题，所以它仅是可计算安全。2019年，Chen等 [15] 构建了理想的线性多部秘密共享方案，利用文献 [9] 中提出的基于多拟阵的方法和Gabidulin编码实现多部访问结构。2021年，Chen等 [16] 利用线性代数技术提出了一种分区访问结构方案，但该方案需要检查较多矩阵的非奇异性，故其效率也较低。同年，Xu等 [17] 提出了具有分层访问结构的多阶段秘密共享方案，但该方案仅是可计算安全。Miao等 [3] 基于多项式插值和中国剩余定理提出了多部门限秘密共享方案，其缺点是无法实现主秘密的更新。上述这些方案，有的不满足理想的秘密共享方案特性或子秘密不具有重复使用的性质；有的更新主秘密导致分发算法的通信量较大。

本文基于多项式插值和短词排序技术提出了一类子秘密可重复使用的多部秘密共享方案，主要构造思路是将自由群中的有限表现集分发给对应的每一个层级参与者，利用既约字和短词排序将函数值转换成字集形式，再将字集进行公开；参与重构的参与者们使用持有的份额重构出自由群，并用自由群和短词排序恢复函数值，再用多项式插值公式重构出主秘密的值。

本文方案在不改变部分访问结构的参与者子秘密情况下实现在线更新主秘密，并且具有信息论意义下的安全性。每当分发者改变主秘密时，分发者会根据部分访问结构的份额更新新公开值，然后根据新公开值和部分访问结构重构新主秘密。对于每个主秘密的变化，每个部分访问结构需和当前的公开值一起参与重构秘密，因为之前的公开值不再有效。分发者可在有需要的情况下改变主秘密，避免分发算法的通信复杂度。

本文架构如下：第1节介绍本文研究背景以及相关研究工作；第2节简要说明一些预备知识；包含本文所需的数学理论基础；第3节描述本文方案具体构造；第4节给出方案详细分析；第5节对本文作出总结。

2. 预备知识

2.1. 秘密共享方案

秘密共享方案主要包括分发者D，参与者 $P = {P_{1}, P_{2}, \dots, P_{n}}$ ，重构者C，共享的主秘密以及秘密分发算法和秘密重构算法。分发者D根据分发算法将主秘密值转换为多个份额，并将所对应产生的份额安全地分发给相应的参与者；秘密重构时，重构者C根据重构算法将多个参与者的份额转化为主秘密值。

为了方便阐述，本文将秘密共享方案分为3个过程：

· 参数选取：分发者D根据方案需要选取合适的参数。

· 秘密分发：分发者D根据方案分发算法将主秘密值分成多个份额，并通过安全信道分发给对应的参与者。

· 秘密重构：任意的访问结构中的参与者集根据重构算法进行主秘密重构。

2.2. Shamir $(t, n)$ 门限秘密共享方案

在 $(t, n)$ 门限秘密共享方案中，分发者将主秘密分成n个份额，使得任意不少于t个参与者合作正确地重构出主秘密s，而小于门限值t个的参与者合作无法获得有关主秘密的任何信息。当门限秘密共享方案同时满足以下两个性质，可称该方案是完善的 $(t, n)$ 门限秘密共享方案：1) 正确性：任意的大于或者等于t个参与者合作可以正确地恢复出主秘密；2) 安全性：任意的少于t个参与者合作无法得到主秘密的任何信息。

Shamir方案 [1] 是基于有限域上多项式插值方法构造的一类 $(t, n)$ 门限秘密共享方案。分发者构造次数不大于 $t - 1$ 次多项式 $f (x)$ ，将主秘密 $s \in F_{p}$ (p为大素数， $p > n$ )作为多项式常数项，并且多项式系数为随机生成数值，将多项式在各个点处的函数值 $f (x)$ 安全地分发给n个参与者 $P = {P_{1}, P_{2}, \dots, P_{n}}$ 作为各自的份额。该方案参数选取、分发过程和重构过程具体构造如下：

· 参数选取：

1) 分发者D选取整数n和大素数p，其中n为参与者人数且 $p > n$ ；

2) 分发者再选取 $x_{i} \in F_{p}$ ，将所有 $x_{i}$ 公开，其中 $i = 1, \dots, n$ 。

· 秘密分发：

1) 分发者D随机选取 $a_{0}, a_{1}, \dots, a_{t - 1} \in F_{p}$ 并构造多项式 $f (x) = a_{0} + a_{1} x + \dots + a_{t - 1} x^{t - 1} (\mod p)$ ，其中常数项 $a_{0} = s$ 为主秘密值；

2) 分发者D计算每个函数值 $f (x_{i}) (i = 1, \dots, n)$ ，作为第i个参与者 $P_{i}$ 的份额；

3) 分发者D通过安全信道把这些份额分发给参与者 $P_{i}$ ，其中 $i = 1, \dots, n$ 。

· 秘密重构：设有t个参与者 $P_{1}, P_{2}, \dots, P_{t}$ 欲恢复主秘密，他们各自提供其持有的秘密份额，利用Lagrange多项式插值公式重构得到主秘密，具体计算方法如下：

$s = \sum_{i = 1}^{t} f (x_{i}) \prod_{x_{j} = 1, x_{j} \neq x_{i}}^{t} \frac{x_{j}}{x_{j} - x_{i}} (\mod p) .$

2.3. 信息熵

Shannon [18] 提出信息熵刻画描述信息的不确定程度，通过随机变量的概率分布函数给出度量信息熵的数学表达式。为了便于本文描述，下文给出信息熵和条件熵的定义。

定义1 [18] 离散随机变量V由有限集合 $υ$ 和定义在 $υ$ 上的概率分布组成，设离散随机变量V的概率分布函数为 $p (v) = \Pr {V = v} (v \in υ)$ ，则随机变量V的信息熵定义为

$H (v) = - \sum_{v \in υ} p (v) \log p (v) .$

定义2 [18] 设随机变量 $V, Y$ 对应的有限集合分别为 $υ, γ$ ，则联合分布为 $p (v, y)$ 的离散随机变量对的条件熵为

$H (Y | V) = \sum_{v \in υ} p (v) H (Y | V = v) = - \sum_{v \in υ} p (v, y) \log (y | v) .$

通过条件熵 $H (V | Y)$ ，定义信息熵的链式法则为： $H (V | Y) = H (V) + H (Y | V)$ 。

定义3 (完善的秘密共享方案 [19])当秘密共享方案同时满足如下两个条件，则称该方案为完善的秘密共享方案：

正确性：对于授权集A，A中参与者将持有的份额联合起来，可正确恢复主秘密s，即 $H (s | s_{A}) = 0$ ， $s_{A}$ 表示集合A中参与者的份额集；

安全性：对于非授权集B，B中参与者将持有的份额联合起来，得不到关于主秘密s的任何信息，即 $H (s | s_{B}) = H (s)$ ， $s_{B}$ 表示集合B中参与者的份额集。

利用信息熵的相关性质将证明了本文方案是完善安全的。

2.4. 自由群

设X是群G的一个生成元集，对于X中的任意元素 $e_{1}, e_{2}, \dots, e_{k}$ ，如果 $e_{i} \neq e_{i + 1} (1 \leq i < k)$ ，并且 $m_{1}, m_{2}, \dots, m_{k}$ 全不为0，则 $e_{1}^{m_{1}} e_{2}^{m_{2}} \dots e_{k}^{m_{k}} \neq G^{1}$ ，其中 $G^{1}$ 为G中的单位元，那么称X是群G的一个自由生成元集。如果群G有一个自由生成元集，则称G是自由群。例整数加群 $ℤ$ 是自由群。因为 $ℤ$ 有一个自由生成元集 ${1}$ ，所以 $ℤ$ 是由一个元素生成的自由群。本文把一个非空集合X称为字母表。

定义4 [20] 设X为字母表且 $e_{1}, e_{2}, \dots, e_{k} \in X$ ， $m_{i} \in ℤ, 1 \leq i \leq k$ ，称 $e_{1}^{m_{1}} e_{2}^{m_{2}} \dots e_{k}^{m_{k}}$ 为一个字。

定义5 [20] 如果 $e_{i} \neq e_{i + 1}, 1 \leq i < k$ ，并且所有 $m_{i} \neq 0, 1 \leq i \leq k$ ，称字 $e_{1}^{m_{1}} e_{2}^{m_{2}} \dots e_{k}^{m_{k}}$ 是既约的。特别地，把 $e_{i}^{0}$ 也称为既约字。

每一个字都可按照下述规则化简成既约字：1) 如果相邻的两个字母相同，则可合并写成一个字母的方幂，将指数的和作为指数；2) 零次幂省略不写。因此字母表X形成的所有既约字组成的集合 $F (X)$ 构成一个群。容易看出，X是群 $F (X)$ 的一个自由生成元集。故 $F (X)$ 是自由群，称它是由X生成的自由群。

定义6 [20] 设X是非空集合，R是自由群 $F (X)$ 的非空子集，用N表示R生成的正规子群(即为 $F (X)$ 中包含R的正规子群的交)，则商群 $F (X) / N$ 称为是由生成元集X和定义关系集R决定的群。如果群G同构于 $F (X) / N$ ，则 $X, R$ 称为G的一个表现，记作 $G \equiv {X | R}$ 。特别地，若 $X = {e_{1}, e_{2}, \dots, e_{k}}$ ，且 $R = {ω_{1}, \dots, ω_{t}}$ ，那么就称G是有限表现的。

定理1 [20] 每一个字能化简成唯一的既约字。

定义7 [21] 设 $X = {e_{1}, e_{2}, \dots, e_{m}}$ 是一个字母表，群G由X所生成，记为 $G = 〈 X 〉$ ，那么群 $G = 〈 X 〉$ 的一种短词排序定义如下；给定既约字 $ω = e_{i_{1}} \dots e_{i_{p}}$ 以及 $l = e_{j_{1}} \dots e_{j_{k}}$ ，其中 $ω \neq l$ ，且 $| ω |$ 表示的是 $ω$ 的长度， $| l |$ 表示的是l的长度，如果满足以下条件之一：

1) $| ω | < | l |$ ；

2) 若 $p = k$ ，且 $e_{i_{a}} < e_{j_{a}}$ ，其中 $a = {min}_{α} {e_{i_{a}} \neq e_{j_{a}}}$ ；

则称 $ω$ 和l为序关系，记为 $ω < l$ 。

例如，若 $X = {x, y}$ ，且给定 $X^{\pm 1}$ 的词序为 $x < x^{- 1} < y < y^{- 1}$ ，可推断出一些词序为：

$\begin{array}{l} e < x < x^{- 1} < y < y^{- 1} < x^{2} < x y < x y^{- 1} < x^{- 2} < x^{- 1} y < x^{- 1} y^{- 1} < y x < y x^{- 1} < y^{2} < y^{- 1} x < y^{- 1} x^{- 1} \\ < y^{- 2} < x^{3} < x^{3} < x^{2} y < x^{2} y^{- 1} < x y x < x y x^{- 1} < \dots \end{array}$ 。

根据每一个短词的位置，相应可将词序转化为整数值： $x^{- 1}$ 可对应出词序位置为3；根据词序位置的整数值，可相应的对应出既约短词：词序位置为10，相应可对应出短词为 $x^{- 1} y$ 。

3. 本文方案

本节基于自由群中的短词排序与Shamir $(t, n)$ 门限秘密共享方案设计了子秘密可重复使用的多部门限秘密共享方案；其构造思路是：每个部分访问结构门限值是 $t_{i}$ ，通过给每个部分访问结构分发不同自由群的定义关系集，根据定义关系集和函数值生成函数值对应的公开字集，将每个人的身份标识，以及公开字集作为公开信息。具体方案构造如下：

· 参数选取：

1) 分发者D选取 $P = {P_{1}, \dots, P_{n}}$ 作为n个参与者的集合，然后将P又分成m个部分访问结构 $P = {U_{1}, U_{2}, \dots, U_{m}}$ ，每个部分访问结构 $U_{i}$ 中有 $n_{i}$ 名参与者，每个参与者只属于其中一个部分访问结构中，即有 $U_{i} \cap U_{j} = \emptyset (i \neq j)$ 和 $n = n_{1} + n_{2} + \dots + n_{m}$ 。

2) 分发者D随机选取 $x_{i} \in F_{p}$ ，将 $x_{i}$ 对应地分发给层级 $U_{i}$ ，作为层级 $U_{i}$ 公开值。

· 秘密分发：

1) 分发者D为层级 $U_{i}$ ， $i = 1, 2, \dots, m$ 选取一个有限表现群 $G_{i} = 〈 e_{i 1}, e_{i 2}, \dots, e_{i k} | r_{i 1}, r_{i 2}, \dots, r_{i u_{i}} 〉$ ，其中 $e_{i j}$ 为群 $G_{i}$ 的生成元， $r_{i j}$ 为群 $G_{i}$ 的定义关系元， $u_{i} = C_{n_{i}}^{t_{i} - 1}$ 。

2) 分发者D首先选定 $A_{1}, \dots, A_{m_{i}}$ 为集合 ${1, 2, \dots, n_{i}}$ 中任意 $(t_{i} - 1)$ 个元素的子集，并确定 ${R_{i 1}, R_{i 2}, \dots, R_{i n_{i}}}$ 为 $R_{i} = {r_{i 1}, r_{i 2}, \dots, r_{i u_{i}}}$ 的 $n_{i}$ 个子集，其中 $r_{i j} \in R_{i j}$ 当且仅当 $i \notin A_{j}, j = 1, 2, \dots, u_{i}; i = 1, 2, \dots, n_{i}$ ；随后将字集 $R_{i j}$ 作为秘密份额对应地分发给参与者 $P_{i j}$ 。

3) 分发者D随机选取 $a_{0}, a_{1}, \dots, a_{m - 1} \in F_{p}$ ，构造次数不大于 $(m - 1)$ 次多项式 $f (x) = a_{0} + a_{1} x + \dots + a_{m - 1} x^{m - 1} (\mod p)$ ，其中常数项 $a_{0} = s$ 为主秘密值。

4) 分发者公开短词排序，根据短词与位置整数值的一一对应关系， $f (x_{i})$ 的值可对应短词排序中第 $f (x_{i})$ 个位置的短词，利用函数值对应的短词和 $G_{i}$ 中的定义关系集，可根据短词既约运算生成公开值 $ω_{i}$ ，使得 $ω_{i}$ 可以在 $G_{i}$ 的定义关系集下既约对应于第 $f (x_{i})$ 个词序位置。

· 秘密重构：

1) 每个层级 $U_{i}$ 集合中任意 $t_{i}$ 个及以上参与者合作可恢复定义关系集 $R_{i} = {r_{i 1}, r_{i 2}, \dots, r_{i u_{i}}}$ ，进而可恢复有限表现群 $G_{i}$ 。

2) 根据群 $G_{i}$ 的定义关系集，可将公开字集 $ω_{i}$ 既约为短词排序的第 $f (x_{i})$ 个词序位置，m个部分访问结构共恢复m个函数值，然后根据利用Lagrange多项式插值公式计算得到主秘密：

$s = \sum_{i = 1}^{m} f (x_{i}) \prod_{x_{j} = 1, x_{j} \neq x_{i}}^{m} \frac{x_{j}}{x_{j} - x_{i}} (\mod p)$ 。

上述方案流程图可如图1所示：

Figure 1. The diagram of scheme

图1. 方案示意图

4. 方案分析

根据定义3，本节给出本文方案正确性和安全性分析。正确性分析主要是分析根据方案重构算法是否可以正确地恢复主秘密；安全性证明包括两个部分：一部分是层级 $U_{i}$ 内小于门限 $t_{i}$ 的参与者合作得不到主秘密的任何信息，另一部分是任意 $m - 1$ 个层级合作得不到主秘密的任何信息。

定理2 本文方案是完善的多部秘密共享方案。

证明：正确性：假设 $U_{i}$ 中的 $t_{i}$ 个参与者 $P_{i 1}, P_{i 2}, \dots, P_{i t_{i}}$ 需要恢复出份额 $f (x_{i})$ ，这时参与者们利用持有的字集可以恢复出自由群 $G_{i}$ ，那么根据自由群 $G_{i}$ 的定义关系集，将公开字集 $ω_{i}$ 既约为词序中的第 $f (x_{i})$ 个位置，得出 $f (x_{i})$ 的函数值. 那么m个部分访问结构一共有m个 $f (x_{i})$ 的值，因此可以根据Lagrange多项式插值公式求解出主秘密s。

安全性：1) 以下证明任意的 $t_{i} - 1$ 个参与者得不到第 $t_{i}$ 个 $R_{i t_{i}}$ 的信息。根据信息熵相关定义证明，因为分发者分发给部分访问结构中的每个参与者的字集不同，所以

$\begin{array}{l} H (R_{i t_{i}} | R_{i 1} R_{i 2} \dots R_{i t_{i} - 1}) = - \sum_{b_{i t_{i}} \in R_{i t_{i}}} \sum_{y \in Y} p (y) p (b_{i t_{i}} | y) \log p (b_{i t_{i}} | y) \\ = - \sum_{b_{t_{i}} \in R_{t_{i}}} \sum_{b_{1_{i}} b_{2_{i}} \dots b_{t_{i} - 1} \in R_{1_{i}} R_{2_{i}} \dots R_{t_{i} - 1}} p (b_{i 1} b_{i 2} \dots b_{i t_{i} - 1}) p (b_{i t_{i}} | b_{i 1} b_{i 2} \dots b_{i t_{i} - 1}) \log p (b_{i t_{i}} | b_{i 1} b_{i 2} \dots b_{i t_{i} - 1}) \\ = - \sum_{b_{i t_{i}} \in R_{i t_{i}}} \sum_{b_{i 1} b_{2 i} \dots b_{i t_{i} - 1} \in R_{i 1} R_{i 2} \dots R_{i t_{i} - 1}} p (b_{i 1} b_{i 2} \dots b_{i t_{i} - 1}) p (\frac{b_{i 1} b_{i 2} \dots b_{i t_{i} - 1} b_{i t_{i}}}{b_{i 1} b_{i 2} \dots b_{i t_{i} - 1}}) \log p (\frac{b_{i 1} b_{i 2} \dots b_{i t_{i} - 1} b_{i t_{i}}}{b_{i 1} b_{i 2} \dots b_{i t_{i} - 1}}) \\ = - \sum_{b_{i t_{i}} \in R_{i t_{i}}} p (b_{i t_{i}}) \log p (b_{i t_{i}}) \\ = H (R_{i t_{i}}) \end{array}$

其中 $y = b_{i 1} b_{i 2} \dots b_{i t_{i} - 1}$ 为 $Y = R_{i 1} R_{i 2} \dots R_{i t_{i} - 1}$ 的一个子集，故 $t_{i} - 1$ 个参与者得不到第 $t_{i}$ 个参与者的信息。

以上证明式子第三步至第四步是因为分发者分发给每个参与者的字集 $R_{i 1}, R_{i 2}, \dots, R_{i t_{i} - 1}$ 不同，因此对于 $R_{i 1}, R_{i 2}, \dots, R_{i t_{i} - 1}$ 的任意子集，有 $p (b_{i}) = p (b_{j})$ ，其中 $i, j \in i 1, i 2, \dots, i t_{i}$ 。最后可以得到 $p (\frac{b_{i 1} b_{i 2} \dots b_{i t_{i} - 1} b_{i t_{i}}}{b_{i 1} b_{i 2} \dots b_{i t_{i} - 1}}) = p (b_{i 1}) p (b_{i 2}) \dots p (b_{i t_{i} - 1}) p (b_{i t_{i}}) / (p (b_{i 1}) p (b_{i 2}) \dots p (b_{i t_{i} - 1})) = p (b_{i t_{i}})$ 。

假设 $t_{i} - 1$ 个参与者 $P_{i 1}, P_{i 2}, \dots, P_{i t_{i} - 1}$ 尝试直接恢复主秘密，那么每个参与者对应地拿出自己手中拥有的定义关系集的子集 $R_{i j}$ 去恢复自由群 $G_{i}$ 。因为分发者给每个部分访问结构中的参与者分发自由群 $G_{i}$ 中的定义关系集不一致，所以 $t_{i} - 1$ 个参与者只能得到部分但不是全部的 $r_{1}, r_{2}, \dots, r_{u_{i}}$ ，这时参与重构的参与者们会就此生成一个自由群 $G^{'} = 〈 x_{1}, x_{2}, \dots, x_{k} | {r^{'}}_{1}, {r^{'}}_{2}, \dots, {r^{'}}_{g} 〉$ ，其中 $g < u_{i}$ 。那么参与者们并没有恢复完整的群 $G_{i}$ 的定义关系集合，所以 $G_{i}$ 和 ${G^{'}}_{i}$ 的单位元会有所不同，有 $G_{i} \neq {G^{'}}_{i}$ ，根据 ${G^{'}}_{i}$ 去既约公开字集 $ω_{i}$ 会得到错误的 $f (x_{i})$ ，错误的 $f (x_{i})$ 不能恢复正确的主秘密s。

2) 任意两个部分访问结构 $U_{i}$ 和 $U_{j}$ 的参与者互相得不到对方的子秘密值，这是因为分发给每个部分访问结构的参与者们是不同的自由群，即有 $G_{i} \neq G_{j}$ ，自由群不同，通过自由群的定义关系集求解出的短词也是不同的，只有对应的访问结构的自由群才能正确求解出既约的短词，进而对应的求解出函数值。因此 $m - 1$ 个层级合作只能获取 $m - 1$ 个函数值，只能列出 $m - 1$ 个线性方程组，求解不出m个未知数，所以基于Shamir方案易知 $m - 1$ 个层级合作得不到主秘密的任何信息。 □

本文方案可以实现主秘密更新功能。分发者需要更新主秘密时，只需要更新多项式的函数值对应的公开字集 $ω_{i}$ 。当公开字集改变，部分访问结构中的参与者利用同一个自由群既约公开字集，既约出的短词对应不同的词序位置，即新的函数值位置，最后根据Lagrange多项式插值公式求解出更新之后的主秘密。

5. 方案比较

本文的多部门限秘密共享方案能够通过参与者子秘密的动态使用，进行主秘密的更新，避免更改主秘密时分发阶段中的通信需求。对于多部秘密共享方案中，因为访问结构较多，分发算法尤其繁杂，所以若主秘密能够实现动态更新，效率会得到了较大的提升。本文方案可动态实现主秘密更新，于分发算法效率上要优于文献 [3] [13]。与文献 [14] 相比较：因为文献 [14] 是基于整数规划的NP问题，所以该方案是可计算安全的；本文方案不基于任何困难问题假设，所以本文方案具有较高的安全性。本文方案与其他多部门限秘密共享方案的对比如表1所示。

Table 1. Performance comparison of multipartie threshold secret sharing schemes

表1. 多部门限秘密共享方案性能比较

注：信息率是指主秘密大小与子秘密大小的比值。

6. 总结

本文基于Shamir $(t, n)$ 门限秘密共享方案，以自由群的短词排序为工具构造了一个主秘密可以多次更新的多部门限秘密共享方案。该方案通过分发自由群中定义关系集的子集作为参与者的份额；参与者们通过恢复自由群的定义关系集，利用短词排序方法恢复函数值，Lagrange多项式插值公式重构主秘密。本文方案具有动态更新主秘密的优点，避免了主秘密更新时分发阶段的再次通信。未来的研究工作可经过扩展到构造子秘密可重复使用门限多秘密共享方案以及门限可变的多部秘密共享方案等。

文章引用

林苇婷,林昌露. 基于多项式插值的多部门限秘密共享方案
Multipartie Threshold Secret Sharing Scheme Based on Polynomial Interpolation[J]. 理论数学, 2022, 12(12): 2124-2132. https://doi.org/10.12677/PM.2022.1212228

参考文献

1. Shamir, A. (1979) How to Share a Secret. Communications of the ACM, 22, 612-613. https://doi.org/10.1145/359168.359176

2. Blakley, G.R. (1979) Safeguarding Cryptographic Keys. International Workshop on Managing Requirements Knowledge, New York, 4-7 June 1979, 313-313. https://doi.org/10.1109/MARK.1979.8817296

3. Miao, F., Yu, Y., Meng, K., et al. (2021) Grouped Secret Sharing Schemes Based on Lagrange Interpolation Polynomials and Chinese Remainder Theorem. Security and Com-munication Networks, 2021, Article ID: 6678345. https://doi.org/10.1155/2021/6678345

4. Subrahmanyam, R., Rukma Rekha, N. and Subba Rao, Y.V. (2022) Multipartite Verifiable Secret Sharing Based on CRT. In: Smys, S., et al., Eds., Computer Networks and Inventive Communication Technologies, Springer, Singapore, 233-245. https://doi.org/10.1007/978-981-16-3728-5_17

5. Shima, K. and Doi, H. (2018) A Hierarchical Secret Sharing Scheme Based on Information Dispersal Techniques. In: Lee, K., Ed., International Conference on Information Security and Cryptology-ICISC 2018, Springer, Cham, 217-232. https://doi.org/10.1007/978-3-030-12146-4_14

6. Tochikubo, K. (2019) General Secret Sharing Schemes Using Hierarchical Threshold Scheme. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 102, 1037-1047. https://doi.org/10.1587/transfun.E102.A.1037

7. Ding, J., Lin, C. and Lin, F. (2020) Optimal Threshold Changeable Secret Sharing with New Threshold Change Range. In: Nguyen, K., et al., Eds., International Conference on Provable Security 2020, Springer, Cham, 361-378. https://doi.org/10.1007/978-3-030-62576-4_18

8. Harn, L., Hsu, C. and Xia, Z. (2022) A Novel Threshold Changeable Secret Sharing Scheme. Frontiers of Computer Science, 16, Article ID: 161807. https://doi.org/10.1007/s11704-020-0300-x

9. Farràs, O., Martí-Farré, J. and Padró, C. (2012) Ideal Multipartite Secret Sharing Schemes. Journal of Cryptology, 25, 434-463. https://doi.org/10.1007/s00145-011-9101-6

10. Simmons, G.J. (1988) How to (Really) Share a Secret. In: Goldwasser, S., Ed., Advances in Cryptology—CRYPTO’88, Springer, Cham, 390-448. https://doi.org/10.1007/0-387-34799-2_30

11. Brickell, E.F. (1989) Some Ideal Secret Sharing Schemes. In: Quisquater, J.-J. and Vandewalle, J., Eds., Advances in Cryptology—EUROCRYPT ’89, Springer, Cham , 468-475. https://doi.org/10.1007/3-540-46885-4_45

12. Tassa, T. (2007) Hierarchical Threshold Secret Sharing. Journal of Cryptology, 20, 237-264. https://doi.org/10.1007/s00145-006-0334-8

13. Hsu, C.F. and Harn, L. (2014) Multipartite Secret Sharing Based on CRT. Wireless Personal Communications, 78, 271-282. https://doi.org/10.1007/s11277-014-1751-x

14. Harsha, P., Chanakya, P. and Vadlamudi, C.V. (2018) A Reusa-ble Multipartite Secret Sharing Scheme Based on Super Increasing Sequence. International Journal of Network Security, 20, 527-535.

15. Chen, Q., Tang, C. and Lin, Z. (2019) Efficient Explicit Constructions of Compartmented Secret Sharing Schemes. Designs, Codes and Cryptography, 87, 2913-2940. https://doi.org/10.1007/s10623-019-00657-2

16. Chen, Q., Tang, C. and Lin, Z. (2021) Efficient Explicit Con-structions of Multipartite Secret Sharing Schemes. IEEE Transactions on Information Theory, 68, 601-631. https://doi.org/10.1109/TIT.2021.3123102

17. Xu, G., Yuan, J., Xu, G., et al. (2021) A New Multi-Stage Secret Sharing Scheme for Hierarchical Access Structure with Existential Quantifier. Information Technology and Control, 50, 236-246. https://doi.org/10.5755/j01.itc.50.2.27789

18. Shannon, C.E. (1948) A Mathematical Theory of Communication. The Bell System Technical Journal, 27, 379-423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

19. Cohen, H. (1993) A Course in Computational Algebraic Number Theory. Springer, Berlin. https://doi.org/10.1007/978-3-662-02945-9

20. 丘维声. 抽象代数基础[M]. 第2版. 北京: 高等教育出版社, 2015: 75-81.

21. Cavallo, B. and Kahrobaei, D. (2015) Secret Sharing Using Non-Commutative Groups and the Shortlex Order. Contemporary Mathematics, 633, 1-8. https://doi.org/10.1090/conm/633/12646

期刊菜单