🔢 mathematics

Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

本文针对现有基于中国剩余定理的层次化秘密共享方案存在的安全缺陷或信息率低于 1/2 的问题，提出了一种利用整数环中国剩余定理和单向函数构建的析取与合取层次化秘密共享方案，并证明了这两种方案均具有渐近理想性和安全性。

原作者： Jian Ding, Cheng Wang, Hongju Li, Cheng Shu, Haifeng Yu

发布于 2026-03-24

📖 1 分钟阅读🧠 深度阅读

原作者： Jian Ding, Cheng Wang, Hongju Li, Cheng Shu, Haifeng Yu

原始论文根据 CC0 1.0（http://creativecommons.org/publicdomain/zero/1.0/）发布到公有领域。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文提出了一种更聪明、更安全、更高效的“秘密分享”新方法。为了让你轻松理解，我们可以把这项技术想象成管理一座拥有不同权限等级的“数字金库”。

1. 背景：为什么我们需要“分级”？

想象你是一家大公司的老板，手里有一个绝密配方（秘密）。

传统方法（Shamir 方案）： 你把配方切成很多块，发给 10 个员工。规则是：只要凑齐任意 5 个人，就能拼回配方。
- 缺点： 这太死板了。在现实中，CEO 的权限应该比实习生大。如果 CEO 一个人就能决定，或者需要"CEO + 2 个高管”才能决定，传统方法就搞不定了。
分级秘密分享（HSS）： 为了解决这个问题，人们设计了“分级”系统。把员工分成不同的小组（比如：高管组、经理组、普通员工组），每个组有不同的“门槛”。
- 或门逻辑（DHSS）： 只要满足任意一个组的门槛（比如：要么 CEO 一个人，要么 3 个经理），就能打开金库。
- 与门逻辑（CHSS）： 必须同时满足所有组的门槛（比如：必须有 CEO，且必须有 2 个经理，且必须有 5 个员工），才能打开金库。

2. 过去的难题：要么不安全，要么太“胖”

以前的分级方案主要有两个毛病：

不安全： 有些方案像纸糊的，坏人稍微算一下就能猜出秘密。
效率低（信息率低）： 想象你要送一份秘密文件。
- 理想情况： 秘密文件是 1 页纸，你发给每个人的“碎片”也是 1 页纸。这叫“完美效率”。
- 旧方案的问题： 为了安全，你不得不把秘密文件切成 1 页，但发给每个人的碎片却变成了 10 页（里面全是废话）。这就叫“信息率低”，传输和存储成本太高。

3. 这篇论文的“魔法”：两个核心工具

作者用了两个数学工具来解决上述问题：

工具一：中国剩余定理（CRT）—— “拼图大师”

想象你有一个大拼图（秘密）。

CRT 就像是一个神奇的规则：如果你知道这个拼图在几个不同颜色的框里分别长什么样（比如模 3 余 1，模 5 余 2），你就能唯一地还原出整个拼图。
好处： 它可以灵活地给不同的人分配不同大小的“碎片”（比如给 CEO 的碎片小一点，给普通员工的碎片大一点），非常灵活。

工具二：单向函数 —— “单向旋转门”

想象一个只能进不能出的旋转门。你可以轻松地把秘密“转”进去变成乱码，但如果没有钥匙，没人能把乱码“转”回秘密。
作用： 用来防止坏人通过观察碎片来反推秘密，增加安全性。

4. 他们的创新方案：像“乐高”一样完美

作者结合这两个工具，设计了两种新方案（对应上面的“或门”和“与门”）：

方案 A：灵活拼凑（Disjunctive / DHSS）

场景： 只要满足任意一条规则就能开门。
比喻： 就像金库有两条路：
- 路 1：需要 3 个经理。
- 路 2：需要 1 个 CEO。
- 只要走通其中一条路，门就开了。
创新点： 以前的方案要么不安全，要么碎片太大。作者利用“互质数序列”（一种特殊的数字排列，像乐高积木一样严丝合缝），让碎片的大小几乎和秘密本身一样大（信息率接近 1），而且随着秘密变大，安全性越来越完美。

方案 B：层层关卡（Conjunctive / CHSS）

场景： 必须同时满足所有规则才能开门。
比喻： 金库有层层关卡：
- 第一关：必须有 CEO。
- 第二关：必须有 3 个经理。
- 第三关：必须有 5 个员工。
- 只有集齐所有关卡的钥匙，门才开。
创新点： 同样实现了“碎片大小几乎等于秘密大小”，且非常安全。

5. 为什么这很重要？（总结）

这篇论文就像是在说：“我们终于造出了一把万能钥匙，它既安全（坏人打不开），又轻便（每个人背的碎片都很小，不占地方），还能灵活适应各种复杂的权限管理需求。”

以前： 想要安全，就得背很重的包袱（碎片大）；想要轻便，就得冒风险（不安全）。
现在： 作者证明了，我们可以同时拥有高安全性和高效率。

一句话总结：
作者用数学上的“拼图技巧”和“单向锁”，设计了一套新的秘密分享系统，让不同级别的人能灵活、安全、且低成本地共同守护一个秘密，解决了过去“要么不安全，要么太笨重”的难题。

这是一份关于论文《基于整数环中国剩余定理的渐近理想分层秘密共享》（Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring）的详细技术总结。

1. 研究背景与问题 (Problem)

背景：
秘密共享（Secret Sharing, SS）是一种将秘密分配给一组参与者的方法，只有授权的子集才能重构秘密。在传统的 $(t, n)$ 门限方案中，所有参与者拥有平等的权限。然而，在实际应用场景（如公司管理层、多部门协作）中，不同参与者往往拥有不同的权限等级。为此，分层秘密共享（Hierarchical Secret Sharing, HSS） 应运而生，它将参与者划分为多个子集，并赋予不同的权限级别。

现有问题：
现有的基于中国剩余定理（CRT）的 HSS 方案存在以下主要缺陷：

安全性漏洞： 部分方案（如 Harn 等人提出的方案）已被证明存在安全缺陷。
信息率低： 许多方案的信息率（Information Rate, $\rho$ ）小于 $1/2$ ，意味着分发的份额大小远大于秘密本身，效率低下。
非理想性： 虽然 Tiplea 等人提出了渐近理想的方案，但 Yang 等人基于多项式环的理想方案以及部分 CRT 方案已被证明不安全。
计算复杂度高： 基于 Birkhoff 插值或拟阵（Polymatroids）的理想方案需要经销商进行指数级时间的计算或矩阵验证。

核心目标：
设计一种安全、渐近理想（信息率趋近于 1）、支持灵活份额大小且计算高效（多项式时间）的分层秘密共享方案，涵盖**析取（Disjunctive, DHSS）和合取（Conjunctive, CHSS）**两种访问结构。

2. 方法论 (Methodology)

本文提出了一种结合**整数环上的中国剩余定理（CRT）与单向函数（One-way Functions）**的新构造方法。

2.1 核心数学工具

k-紧凑互质序列（k-compact sequences of co-primes）： 利用参考文献 [9] 中的概念，生成满足特定增长条件的互质整数序列 $L = \{m_0, m_1, \dots, m_n\}$ $L = {m_{0}, m_{1}, \dots, m_{n}}$ 。
- 条件： $m_0 < m_1 < \dots < m_n$ ，且 $km_0 < m_i < km_0 + m_0^\theta$ （其中 $k \ge 1, \theta \in (0, 1)$ ）。
- 作用：这种序列结构确保了 Asmuth-Bloom 约束在 $m_0$ 足够大时成立，从而保证方案的渐近完美性（Asymptotic Perfectness）和高信息率。
单向函数（One-way Functions）： 引入公开的一向函数 $h_\ell(\cdot)$ 来混淆份额，防止未授权集合通过公开信息反推秘密。

2.2 方案构造

论文分别构建了两种方案：

A. 析取分层秘密共享 (DHSS) 方案

访问结构： 只要某个子集 $A$ 在任意层级 $\ell$ 的累积参与者数量达到阈值 $t_\ell$ ，即可重构秘密（ $\exists \ell, |A \cap \bigcup_{w=1}^\ell P_w| \ge t_\ell$ ）。
份额生成：
1. 经销商生成互质序列 $L$ 。
2. 对于秘密 $s$ ，生成随机整数 $\alpha_\ell$ 和 $y_\ell = s + \alpha_\ell m_0$ 。
3. 利用单向函数 $h_\ell$ 和公开值 $w_i^{(\ell)}$ 对份额进行掩码处理。
4. 部分参与者直接获得 $y_m \pmod{m_i}$ ，部分获得随机值 $c_i$ 配合掩码。
重构： 授权子集利用 CRT 恢复 $y_\ell$ ，进而通过 $s = y_\ell \pmod{m_0}$ 得到秘密。

B. 合取分层秘密共享 (CHSS) 方案

访问结构： 子集 $A$ 必须在所有层级 $\ell$ 都满足阈值要求（ $\forall \ell, |A \cap \bigcup_{w=1}^\ell P_w| \ge t_\ell$ ）。
构造差异：
1. 秘密 $s$ 被拆分为 $m$ 个随机分量 $\delta_1, \dots, \delta_m$ ，满足 $\sum \delta_i \equiv s \pmod{m_0}$ 。
2. 每个层级 $\ell$ 独立生成一个 $y_\ell$ ，其模 $m_0$ 的余数为 $\delta_\ell$ 。
3. 重构时，先恢复所有 $\delta_\ell$ ，最后求和得到 $s$ 。

3. 关键贡献 (Key Contributions)

首个安全的渐近理想 CRT 基 DHSS 方案：
- 解决了 Harn、Ersoy、Tiplea 等前人方案中存在的“不安全”或“信息率低”的问题。
- 相比 Tassa 和 Cheng 基于 Birkhoff 插值的理想方案，本方案支持灵活的份额大小（Flexible Share Sizes），且无需复杂的矩阵非奇异性验证。
首个安全的渐近理想 CRT 基 CHSS 方案：
- 填补了基于 CRT 的合取分层方案在安全性与理想性之间的空白。
- 相比 Yuan 等人的方案（非理想），本方案实现了信息率趋近于 1。
理论证明：
- 正确性： 证明了授权子集能唯一重构秘密。
- 渐近完美性（Asymptotic Perfectness）： 利用熵理论证明，当秘密空间大小 $|S|$ （即 $m_0$ ）趋于无穷大时，未授权子集获得的信息量趋于 0。
- 渐近理想性（Asymptotic Idealness）： 证明了在基于 1-紧凑序列时，信息率 $\rho \to 1$ 。
计算效率：
- 方案仅需多项式时间，避免了指数级复杂度的参数搜索或矩阵运算。

4. 主要结果 (Results)

安全性： 方案被证明是安全的，未授权子集无法获得关于秘密的任何信息（在渐近意义上）。
信息率： 信息率 $\rho$ $ρ$ 随着秘密大小 $m_0$ $m_{0}$ 的增加而趋近于 1。
- 公式： $\rho = \frac{\log_2 m_0}{\log_2 (m_0 + m_0^\theta)} \to 1$ （当 $m_0 \to \infty$ ）。
灵活性： 允许为不同层级的参与者分配不同大小的份额（基于不同的模数 $m_i$ ）。
对比优势：
- 相比 [4], [5]：支持灵活份额大小。
- 相比 [7], [8], [9], [10]：解决了安全性问题，且信息率更高（趋近 1）。
- 相比 [6]：实现了理想性（信息率=1 的渐近形式）。

5. 意义与影响 (Significance)

理论突破： 该工作成功将 CRT 方法在分层秘密共享中的应用推向了“安全且渐近理想”的新高度，解决了长期存在的安全性与效率之间的权衡难题。
实用价值：
- 高效性： 适用于大规模分布式系统，计算开销低。
- 灵活性： 能够适应不同权限等级的组织需求（如董事会、部门经理、普通员工），且无需为低权限者分发过大的份额。
- 安全性保障： 为需要高安全等级且不同权限管理的场景（如金融密钥管理、政府多级授权）提供了可靠的密码学原语。
未来方向： 该研究为构建更复杂的访问结构（如广义分层结构）提供了新的数学工具和构造思路，特别是 k-紧凑序列与单向函数的结合使用具有推广潜力。

总结： 本文通过巧妙结合整数环 CRT、k-紧凑互质序列和单向函数，提出了一套既安全又高效的分层秘密共享方案，显著提升了现有 CRT 基方案的理论上限和实际应用价值。