💻 computer science

Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

本文通过利用一个固定有理函数的迭代来取代 $n$ 个独立的随机点，实现了对复合阶域上抗泄漏 Shamir 秘密共享评估点的部分去随机化，从而在特定参数范围内，将所需的随机性从 $nd \log p$ 比特降低至 $d \log p$ 比特，同时实现了针对单块泄漏的完美安全性。

原作者： S. Venkitesh

发布于 2026-08-03

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： S. Venkitesh

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正试图守护一个秘密，比如一张藏宝图或是一个密码，但你必须把它拆分成若干碎片，并将每一块分给你的每一位朋友。这就是**秘密分享（Secret Sharing）**的世界。由数学家沙米尔（Shamir）发明的经典方法就像一个神奇的拼图：如果足够多的朋友（比如 5 个朋友中的 3 个）把他们的碎片凑在一起，拼图就会自动解开并揭示出宝藏。但如果朋友的数量不够，这些碎片看起来就像是随机的乱码，秘密依然是安全的。

然而，现实生活是混乱的。一个狡猾的小偷可能无法偷走整个拼图碎片，但他可以同时从每个朋友的碎片中窥视到极其微小的信息。也许他能看到计算机芯片上的某个特定指示灯是亮还是灭，或者听到极其细微的电流嗡鸣声。这被称为物理比特泄漏（physical bit leakage）。这就像一个小偷无法偷走钥匙的整体，但他能感觉到一串钥匙中每一把钥匙齿痕的形状，一次只能感觉到一个微小的凸起。如果拼图碎片的排列方式不够小心，这些微小的窥视累积起来就可能揭开整个秘密。

长期以来，阻止这种小偷的最佳方法是完全随机地选择拼图碎片。这就像通过掷骰子来决定隐藏位置。这种方法效果很好，但它有一个问题：你每次设置系统时都需要一个“信任的掷骰者”（一个完美的随机源）。如果掷骰者被操纵了，或者小偷可以影响掷骰的结果，整个系统就可能崩溃。科学家们想要找到一种方法，不再使用随机骰子，而是使用一个简单的、固定的规则来选择这些隐藏位置，从而让系统无论在谁的注视下都是安全的。

这篇论文正是针对这一问题展开研究的。作者基于最近的一项发现——即在面对这些微小窥视时，秘密分享要么是绝对安全的，要么是彻底崩溃的——提出了一种新的选择隐藏位置的方法。他们不再为每一个朋友都去掷一次骰子，而是使用一种巧妙的、循环往复的数学模式。他们选取一个起始数字，然后通过不断重复应用一个简单的公式来生成所有其他的隐藏位置，就像一场连锁反应。

作者证明了这种方法的效果极其出色。他们展示了对于特定范围的群体规模，这种结构化的模式能使秘密分享方案达到完美安全（perfectly secure）。这意味着泄露信息与实际秘密之间的统计距离恰好为零；小偷无法学到任何东西，甚至连一点点优势都无法获得。他们还提供了一个测试，用来检查起始数字是“好的”（安全的）还是“坏的”（不安全的），并证明了寻找好的起始数字是很容易的。虽然这种方法适用的朋友数量比随机骰子法略少，但它不再需要一个信任的掷骰者，使得系统更加实用且更具抗操纵性。论文明确排除了使用一种更简单、更明显的模式（仅仅是通过一个数进行乘法运算），并指出由于该模式缺乏他们新公式中所包含的特定数学“扭转”，因此无法提供这种安全性。

技术摘要：复合阶域上泄漏弹性 Shamir 秘密共享的偏向性去随机化

1. 问题陈述

本文研究了在复合阶域（ $\mathbb{F}_{p^d}$ ，其中 $d \ge 2$ ）上构建针对物理比特泄漏（physical-bit leakage）具有抗性的 Shamir 秘密共享（SSS）显式评估点（evaluation places）构造问题。

在标准的 SSS 中，一个秘密被分享给 $n$ 个参与方，使得任意 $k$ 个参与方可以重建该秘密。虽然随机化构造（均匀随机选择评估点）已知在统计安全性方面能够抵抗局部泄漏，但它们需要受信任的公共随机性。在实践中，攻击者可能会影响随机种子，从而将方案引导至脆弱的评估点。

前人的工作确立了以下结论：

在素域（ $\mathbb{F}_p$ ）上，随机评估点以高概率实现泄漏弹性。
在复合域（ $\mathbb{F}_{p^d}$ ）上，Nguyen (EUROCRYPT 2025) 确立了一个完美的二分性（perfect dichotomy）：任何基于线性码的秘密共享方案要么是完美安全的（统计距离为 0），要么在面对物理比特泄漏时是完全不安全的。
然而，对于复合域，目前尚不知道适用于 $k > 2$ 或一般块级泄漏（block-leakage）场景的显式确定性评估点族。现有的针对素域的显式构造依赖于非线性比特提取性质，而这些性质并不适用于复合域的线性坐标映射。

核心挑战在于如何去随机化（derandomize）评估点的选择（即减少指定这些点所需的熵），同时在复合域环境下保持针对物理比特泄漏的完美安全性。

2. 方法论与构造

作者提出了一种偏向性去随机化（partial derandomization）策略。他们并非选择 $n$ 个独立的随机评估点，而是将评估点构造为作用于随机选择的基点 $x_0$ 的单个有理函数 $\Phi$ 的迭代。

构造过程：

域设置： 令 $\mathbb{F} = \mathbb{F}_{p^d}$ ， $\alpha$ 为其本原元。
步进算子： 定义 Möbius 变换 $\Phi(x) = \frac{\alpha x}{x + 1}$ 。
评估点： $n$ 个评估点定义为 $x_j = \Phi^j(x_0)$ ，其中 $j = 0, \dots, n-1$ ，且 $x_0 \in \mathbb{F}^*$ 是一个随机选择的基点。
熵减缩： 指定该方案仅需 $d \log p$ 比特（用于选择 $x_0$ ），相比于 $n$ 个独立随机点所需的 $nd \log p$ 比特，实现了显著降低。

关键结构洞察：
其安全性分析依赖于 $\Phi^j$ 的不同极点（distinct poles）。

$\Phi^0(x) = x$ 在 $\infty$ 处有一个极点。
对于 $j \ge 1$ ， $\Phi^j(x)$ 在 $\mathbb{F}^*$ 中一个不同的有限点处有一个极点。
这种“极点差异性”（pole-distinctness）至关重要。作者将此与候选函数 $\Psi(x) = \alpha x$ （纯扩张）进行了对比，后者所有的迭代都在 $\infty$ 处共享同一个极点，导致安全性论证失效。

3. 技术方法

证明过程分为三个阶段，利用了 Nguyen (2025) 建立的完美二分性：

完美二分性（阶段 1）：
本文利用了在 $\mathbb{F}_{p^d}$ 中的坐标提取是 $\mathbb{F}_p$ 线性的这一事实。因此，泄漏映射是线性的。这意味着不同秘密之间的泄漏分布的统计距离要么是 0，要么是 1。当且仅当测试矩阵 $\Theta_{\vec{i}}$ （由评估点和泄漏模式导出）在 $\mathbb{F}_p$ 上具有满列秩时，实现完美安全性。
部分分式非退化性（阶段 2）：
为了证明测试矩阵具有满秩，作者必须证明评估点幂次的非平凡线性组合不会消失。他们定义了一个有理函数 $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$ 。
通过部分分式分解，他们利用了 $\Phi^j$ 具有不同极点的特性。由于极点是互异的，因此 $G_\ell$ 在任何特定极点处的留数（residue）仅由求和中的单项决定。如果 $G_\ell$ 恒等于零，则所有系数都必须为零。这种“非退化性”论证限制了导致秩条件失效的“坏”基点 $x_0$ 的数量。
多块扩展（阶段 3）：
该论证被扩展到多块泄漏（即每个份额泄露多个坐标）。作者处理了来自份额内线性组合的域系数，证明只要泄漏模式是“可容纳的”（admissible，即每个份额的块位置不同），部分分式论证仍然有效。

4. 关键结果

定理 1.1（针对单块泄漏的完美安全性）：
对于参数 $n = O(d / \log_p d)$ 且对于任何阈值 $k \ge 2$ ，存在一个“坏”基点集合 $Bad \subset \mathbb{F}^*$ ，其大小满足 $|Bad| \le n + n(dp)^n$ 。对于任何 $x_0 \notin Bad$ ，使用评估点 $x_j = \Phi^j(x_0)$ 的方案针对任何单块泄漏模式都是完美安全的（统计距离恰好为 0）。

这意味着对于任何素数 $p$ ，该方案对每个份额的单物理比特泄漏具有完美安全性。
当 $d > n(1 + \log_p d) + \log_p(2n)$ 时，保证存在一个好的 $x_0$ 。

定理 1.2（多块泄漏）：
对于一个固定的可容纳泄漏模式，假设泄露了 $M$ 个总块，坏集合的大小被限制在 $n + n \cdot p^M$ 。当 $M < d - \log_p(2n)$ 时，存在一个好的 $x_0$ 。

对于针对所有 $\le M$ 个块的模式的通用安全性，坏集合界限为 $|Bad| \le n + n(dpe)^M$ ，当 $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$ 时保证存在。

分类器：
本文提供了一个显式分类器（算法 1），给定一个候选 $x_0$ ，它可以验证所有泄漏模式下的满秩条件。这作为一个可靠的测试，用以认证该结构化构造的安全性。

5. 意义与比较

本文声称的主要贡献与区别如下：

完美安全性 vs. 统计安全性： 不同于以往在复合域上提供统计安全性（ $\epsilon = 2^{-\Omega(d)}$ ）的随机化构造，本构造在特定的参数范围内实现了完美安全性（统计距离为 0）。
去随机化： 通过将评估点限制在一个单参数族（ $\Phi$ 的轨道）内，将指定方案所需的随机性从 $nd \log p$ 比特降低到了 $d \log p$ 比特。
显式构造： 本文提供了第一个针对 $k > 2$ 且在复合域上能抵抗物理比特泄漏的显式评估点族，超越了“随机评估点”的范式。
局限性与权衡：
- 参与方数量 $n$ 被限制在 $O(d / \log_p d)$ ，而随机化构造支持 $O(dk / \log_p d)$ 。作者推测这种因子 $k$ 的损失是单参数构造所固有的。
- 多块通用性目前受限于模式枚举的瓶颈，导致在 $M$ 上的坏集合界限呈指数级增长。
- 该构造依赖于 Möbius 变换 $\Phi(x) = \alpha x / (x+1)$ 的特定代数结构；另一种选择——纯扩张 $\alpha x$ 则无法提供安全性。

这项工作并不声称解决了所有参数范围下的去随机化问题，也没有提供关于多块通用性的多项式规模坏集合界限，而是将这些识别为开放问题。其主要贡献是在一个特定的、具有实际意义的参数范围内，通过利用有理迭代的不同极点，实现了严谨的偏向性去随机化并达到了完美安全性。