1. 项目概述在分布式计算和存储系统中如何让多个用户安全地存储和共享各自的秘密信息同时确保每个用户只能访问自己的秘密而无法窥探他人的数据是一个经典且具有挑战性的问题。这就是分布式多用户秘密共享Distributed Multi-User Secret Sharing, DMUSS的核心目标。想象一下一个公司有多个部门每个部门都有自己敏感的预算数据他们希望将这些数据加密后分散存储在公司内部的多个服务器上。任何单个服务器都无法获取完整的预算信息但每个部门的授权人员可以仅从他们被允许访问的服务器子集中恢复出自己部门的完整数据并且无法计算出其他部门的任何信息。这就是DMUSS要解决的现实场景。传统的秘密共享方案如经典的Shamir门限方案主要针对单个秘密在多个参与者之间的分割。而DMUSS将其扩展到了一个更复杂的网络模型一个由用户U和存储节点V组成的二分图。每个用户连接着多个存储节点其“邻居”节点。一个可信的“分发者”将每个用户的秘密信息可能长度不同与一些随机噪声一起进行全局编码生成与存储节点数量相等的份额并分发到各个节点。系统需要满足两个核心要求正确性每个用户能从其邻居节点的份额中解码出自己的秘密和弱隐私性任何用户从其邻居节点的份额中无法获得关于其他用户秘密的任何信息论意义上的信息。Khalesi等人在2021年从信息论角度完整刻画了弱隐私和正确性约束下的容量区域Capacity Region即所有可实现的用户速率秘密信息大小与节点存储大小的比值的集合。然而他们的编码方案依赖于一个随机化的蒙特卡洛过程其成功概率取决于一个非常大的有限域的选择。这在实际应用中带来了两个主要问题1.随机性失败风险算法可能因随机种子不佳而失败2.实现复杂度高需要非常大的有限域这在硬件实现如嵌入式系统、专用集成电路中效率低下因为大域上的算术运算如乘法、求逆非常昂贵。我们的工作正是为了弥合这一理论与实现之间的鸿沟。我们提出了一种完全确定性的、多项式时间的算法能够在硬件友好的小有限域仅需域的大小大于最大用户度数Δ上实现容量区域内所有整数速率点。我们的算法在渐进复杂度上显著优于单次蒙特卡洛运行并首次为已知的容量区域提供了明确的确定性构造为分布式秘密共享的算法基础迈出了坚实的一步。2. 系统模型与核心挑战解析2.1 二分图模型与问题形式化我们用一个连通二分图 ( G (U, V; E) ) 来形式化分布式系统。其中( U {0, 1, ..., |U|-1} ) 是用户集合至少2个。( V ) 是存储节点集合至少2个且假设大小相同。( E \subseteq U \times V ) 是边集表示用户与存储节点之间的连接关系。分发者持有 ( |U| ) 个独立的秘密消息每个用户 ( u ) 对应一个其长度为 ( L_u ) 个符号来自有限域 ( \mathbb{F}q )( q ) 为域的大小。定义用户 ( u ) 的速率( r_u L_u / L )其中 ( L ) 是每个存储节点的份额大小也以域符号计。因此一个速率向量 ( \mathbf{r} (r_0, r_1, ..., r{|U|-1}) ) 描述了所有用户秘密的相对大小。分发者的编码函数将 ( \sum_{u \in U} L_u ) 个秘密符号和 ( (|V| - \sum_{u \in U} L_u) ) 个随机噪声符号也来自 ( \mathbb{F}_q )共同编码成 ( |V| ) 个份额每个份额长度为 ( L )并放置到对应的存储节点。用户 ( u ) 的解码函数则仅能访问其邻居节点 ( N(u) ) 上的份额。核心约束正确性对于每个用户 ( u )存在解码函数能够从其邻居节点份额 ( Y_{N(u)} ) 中无误地恢复出其秘密消息 ( W_u )。弱隐私性对于任意两个不同的用户 ( u ) 和 ( u )用户 ( u ) 从其邻居节点份额 ( Y_{N(u)} ) 中关于 ( W_u ) 的条件熵等于其原始熵即 ( H(W_u | Y_{N(u)}) H(W_u) )。这意味着 ( Y_{N(u)} ) 不提供任何关于 ( W_u ) 的信息。2.2 容量区域与现有方案的局限Khalesi等人的工作给出了容量区域的精确信息论刻画。对于速率向量 ( \mathbf{r} )其属于容量区域当且仅当满足以下两个条件私有度约束对于每个用户 ( u )有 ( r_u \leq b_u : \min_{u \neq u} |N(u) \setminus N(u)| )。这保证了每个用户的秘密有足够多的“独家”邻居节点来隐藏信息。共享约束对于用户的任意子集 ( S \subseteq U )有 ( r(S) : \sum_{u \in S} r_u \leq |N(S)| )。这保证了分配给子集 ( S ) 中用户的总信息量不超过其所能访问的存储节点总数。满足共享约束的向量集合在组合优化中被称为横截拟阵。因此容量区域就是这个拟阵被私有度向量 ( \mathbf{b} ) 截断后的部分其所有顶点都是整数值的。尽管这个刻画非常优美但其实现方案存在痛点随机化编码方案依赖于Schwartz-Zippel引理随机选择编码矩阵的系数。单次蒙特卡洛运行的时间复杂度高达 ( O(|U|^3 |V|^3) )。大域要求为确保高成功概率所需有限域的大小 ( q ) 需要远大于边数 ( |E| )而不仅仅是大于最大用户度数 ( \Delta )。这在实践中意味着需要实现 ( \mathbb{F}_{2^{64}} ) 或更大的域其算术运算开销巨大。无多项式时间保证没有理论保证能在多项式次尝试内必然成功。这些局限使得该方案难以应用于对确定性、可复现性、计算效率和硬件友好性有高要求的场景。2.3 确定性算法的核心思路我们的目标是为容量区域内的任意整数速率向量 ( \mathbf{r} )即每个 ( r_u ) 为整数构造一个确定性的编码解码方案。核心思路是将编码过程分解为三个逻辑清晰的阶段并引入两个关键的算法原语来高效解决其中的组合与代数问题完美r-星匹配我们将“共享约束”这一抽象的组合条件转化为在二分图中寻找一个特定的子图结构——完美r-星匹配。这相当于为每个用户的 ( r_u ) 个秘密符号分配 ( r_u ) 条专属的“星边”连接到不同的存储节点并且所有用户的星边覆盖所有存储节点。这个匹配的存在性等价于速率向量满足共享约束。我们将展示如何用最大流算法在 ( O(\min{|U|, r(U)^{1/2}} |E|) ) 时间内找到这样的匹配。对角参数矩阵求逆编码过程最终会归结为求解一个线性系统 ( A(\boldsymbol{\lambda}) \mathbf{Y} B \mathbf{X} )其中 ( A(\boldsymbol{\lambda}) ) 是一个对角线上元素为参数 ( \lambda_v \in {\pm 1} ) 的矩阵( B ) 是常数矩阵( \mathbf{X} ) 是秘密和噪声符号向量( \mathbf{Y} ) 是待求的份额向量。我们需要确定性地选择 ( \boldsymbol{\lambda} ) 使得 ( A(\boldsymbol{\lambda}) ) 可逆并计算其逆。我们提出了两种算法增量求逆法( O(n^3) )和分治求逆法( O(n^\omega) )( \omega \approx 2.371 ) 是矩阵乘法指数后者具有更优的渐进复杂。通过结合快速多项式多点求值/插值、基于最大流的匹配算法以及确定性的矩阵求逆我们最终得到一个总时间复杂度为 ( O(\min{|U|, r(U)^{1/2}} |E| |V|^\omega) ) 的确定性算法并且仅要求有限域大小 ( q \Delta )。3. 核心算法原语完美r-星匹配3.1 从组合约束到流网络“完美r-星匹配”是一个直观的图论概念。在一个二分图 ( G(U, V; E) ) 中一个边集 ( M \subseteq E ) 称为星匹配如果 ( V ) 中的每个节点至多与 ( M ) 中的一条边相关联。一个r-星匹配要求每个用户节点 ( u ) 至多与 ( M ) 中的 ( r_u ) 条边相关联。如果每个用户 ( u ) 恰好关联 ( r_u ) 条边并且覆盖了所有存储节点即 ( |M| \sum_u r_u |V| )则称之为完美的。定理1存在完美r-星匹配当且仅当速率向量 ( \mathbf{r} ) 满足共享约束 ( r(S) \leq |N(S)|, \forall S \subseteq U )。因此验证 ( \mathbf{r} ) 是否在容量区域内并满足私有度约束等价于寻找一个完美r-星匹配。我们通过将其转化为最大流问题来高效求解。我们构造一个流网络 ( D )源点 ( s ) 连接到每个用户 ( u )容量为 ( r_u )。每个用户 ( u ) 连接到其所有邻居存储节点 ( v \in N(u) )容量设为无穷大或一个足够大的数如 ( 2|V| )。每个存储节点 ( v ) 连接到汇点 ( t )容量为1。在这个网络中一个整数值的 ( s-t ) 流 ( f ) 直接对应一个r-星匹配 ( M_f )如果边 ( (u, v) ) 上承载了1单位的流则 ( (u, v) \in M_f )。流的值 ( val(f) ) 就等于匹配 ( M_f ) 的大小。因此寻找最大r-星匹配等价于在 ( D ) 中寻找最大流。3.2 高效的最大流算法实现直接应用经典的Hopcroft-Karp算法针对二分图匹配或Even-Tarjan算法针对边不相交路径无法达到我们目标的时间复杂度 ( O(\min{|U|, \phi^{1/2}} |E|) )其中 ( \phi ) 是最大匹配的大小。我们采用Dinic阻塞流算法的一个特化版本。我们首先将网络 ( D ) 中所有从用户到存储节点的边容量设为1“瘦身”变体这不会改变最大整数值流的存在性。Dinic算法的核心是反复在层次图由最短增广路径构成的子图中寻找阻塞流即发送尽可能多的流使得发送后层次图中不再存在 ( s-t ) 路径。每次阻塞流增广后( s-t ) 的最短距离严格增加。我们的特化在于高效实现每次阻塞流查找。在层次图 ( L_f ) 中我们将每条边 ( (s, u) ) 替换为 ( c_f(u) r_u - f(u) ) 条平行边得到图 ( L_f^ )。在 ( L_f^ ) 中寻找一个极大的边不相交 ( s-t ) 路径集合这可以在 ( O(|E|) ) 时间内通过深度优先搜索完成因为 ( L_f^ ) 是无环的。因此每次迭代构建层次图、寻找阻塞流、增广的时间为 ( O(|E|) )。迭代次数上界由于每次增广后最短距离至少增加2因为层次图是二分图且边容量为1而最短距离不超过 ( 2|U|1 )所以迭代次数为 ( O(|U|) )。通过分析最优性间隙 ( \phi - |M_f| ) 的下降速度我们可以证明迭代次数也为 ( O(\phi^{1/2}) )。具体来说经过 ( k ) 次迭代后有 ( \phi - |M_f| \leq \phi / (k1) )。因此在 ( \lceil \phi^{1/2} \rceil ) 次迭代后间隙最多为 ( \phi^{1/2} )再经过最多 ( \lceil \phi^{1/2} \rceil ) 次迭代即可达到最大流。因此总时间复杂度为 ( O(\min{|U|, \phi^{1/2}} |E|) )。当 ( \mathbf{r} ) 满足共享约束时( \phi r(U) )我们就能在 ( O(\min{|U|, r(U)^{1/2}} |E|) ) 时间内找到一个完美r-星匹配。实操心得在实际编码中我们通常使用高度优化的最大流库如Python的networkx或C的Boost.Graph。但理解这个特化版本的原理很重要因为它解释了为什么我们的算法比通用最大流算法更适合这个问题。对于中等规模的图|U|, |V|在几百量级Dinic算法已经非常高效。当 ( r(U) ) 较小时( O(r(U)^{1/2} |E|) ) 的界尤其有利。4. 核心算法原语对角参数矩阵求逆4.1 问题定义与重要性在编码的第三阶段我们会得到一个形如 ( A(\boldsymbol{\lambda}) \mathbf{Y} B \mathbf{X} ) 的线性系统其中 ( A(\boldsymbol{\lambda}) \text{diag}(\boldsymbol{\lambda}) C )( C ) 是一个常数矩阵( \boldsymbol{\lambda} (\lambda_0, ..., \lambda_{n-1})^T )( n |V| )并且我们需要选择 ( \lambda_v \in {\pm 1} \subset \mathbb{F}_q ) 使得 ( A(\boldsymbol{\lambda}) ) 可逆。这里的 ( \lambda_v ) 代表了存储节点 ( v ) 的“缩放因子”。为什么是 ±1首先( \det(A(\boldsymbol{\lambda})) ) 是关于 ( \boldsymbol{\lambda} ) 的多项式其最高次项 ( \lambda_0 \lambda_1 ... \lambda_{n-1} ) 的系数为1因为来自对角矩阵。根据组合零化引理对于一个至少包含3个元素的有限域 ( \mathbb{F}_q )该多项式不可能在集合 ( {\pm 1}^n ) 的所有点上为零除非是零多项式但最高次项系数为1保证了它不是。因此我们总能从 ( {\pm 1}^n ) 中找到一个赋值使得矩阵可逆。选择 ±1 极大地简化了计算因为它们在小域如 ( \mathbb{F}_q )( q ) 为奇素数中通常是简单的元素乘法就是取负号。4.2 增量求逆法这是一种直观且易于实现的方法适合小规模问题( n ) 较小。算法步骤 令 ( A_i ) 为 ( A ) 的 ( i ) 阶前主子矩阵即由前 ( i1 ) 行和列组成的子矩阵。我们从 ( i0 ) 开始迭代到 ( in-1 )。初始化对于 ( A_0 [\lambda_0 c_{0,0}] )选择 ( \lambda_0 ) 使得该标量非零若 ( c_{0,0} -1 )则令 ( \lambda_0 1 )否则令 ( \lambda_0 -1 )。计算 ( A_0^{-1} [(\lambda_0 c_{0,0})^{-1}] )。迭代假设我们已经确定了 ( \lambda_0, ..., \lambda_{i-1} ) 并计算出了 ( A_{i-1}^{-1} )。将 ( A_i ) 分块为 [ A_i \begin{pmatrix} A_{i-1} \mathbf{v} \ \mathbf{u}^T \lambda_i c_{i,i} \end{pmatrix} ] 其舒尔补为 ( S \lambda_i c_{i,i} - \mathbf{u}^T A_{i-1}^{-1} \mathbf{v} )。选择( \lambda_i )计算标量 ( t \mathbf{u}^T A_{i-1}^{-1} \mathbf{v} - c_{i,i} )。若 ( t 1 )则令 ( \lambda_i -1 )否则令 ( \lambda_i 1 )。这保证了 ( S \neq 0 )。更新逆矩阵利用分块求逆公式计算 ( A_i^{-1} ) [ \theta S^{-1}, \quad A_i^{-1} \begin{pmatrix} A_{i-1}^{-1} \theta (A_{i-1}^{-1} \mathbf{v} \mathbf{u}^T A_{i-1}^{-1}) -\theta A_{i-1}^{-1} \mathbf{v} \ -\theta \mathbf{u}^T A_{i-1}^{-1} \theta \end{pmatrix} ]时间复杂度每次迭代需要计算 ( A_{i-1}^{-1} \mathbf{v} )、( \mathbf{u}^T A_{i-1}^{-1} ) 和 ( \mathbf{u}^T A_{i-1}^{-1} \mathbf{v} )这需要 ( O(i^2) ) 时间。因此总时间为 ( \sum_{i1}^{n-1} O(i^2) O(n^3) )。注意事项增量法虽然简单但每次迭代都需更新整个逆矩阵即使矩阵 ( C ) 是稀疏的其逆矩阵 ( A^{-1} ) 也可能是稠密的。因此对于 ( n ) 较大的情况例如几百以上立方复杂度将成为瓶颈。4.3 分治求逆法为了获得更优的渐进复杂度我们借鉴Strassen矩阵求逆的思想采用分治策略并利用快速矩阵乘法。算法步骤假设 ( n ) 是2的幂非2的幂可通过填充虚拟变量处理分治将矩阵 ( A ) 划分为四个 ( n/2 \times n/2 ) 的块 [ A \begin{pmatrix} A_{11} A_{12} \ A_{21} A_{22} \end{pmatrix} ] 其中 ( A_{11} \text{diag}(\boldsymbol{\lambda}1) C{11} )( A_{22} \text{diag}(\boldsymbol{\lambda}2) C{22} )。递归求逆( A_{11} )递归调用分治算法得到 ( \boldsymbol{\lambda}1 ) 的赋值和 ( A{11}^{-1} )。计算舒尔补计算 ( S A/A_{11} A_{22} - A_{21} A_{11}^{-1} A_{12} )。关键点在于( A_{21} )、( A_{12} ) 和 ( A_{11}^{-1} ) 现在都是常数矩阵因为 ( \boldsymbol{\lambda}_1 ) 已确定所以 ( S ) 仍然是一个对角参数矩阵形式为 ( \text{diag}(\boldsymbol{\lambda}_2) C )。递归求逆舒尔补递归调用分治算法求 ( S^{-1} )并得到 ( \boldsymbol{\lambda}_2 ) 的赋值。合并结果利用分块求逆公式计算 ( A^{-1} ) [ A^{-1} \begin{pmatrix} A_{11}^{-1} A_{11}^{-1} A_{12} S^{-1} A_{21} A_{11}^{-1} -A_{11}^{-1} A_{12} S^{-1} \ -S^{-1} A_{21} A_{11}^{-1} S^{-1} \end{pmatrix} ]时间复杂度分析设 ( T(n) ) 为处理 ( n \times n ) 矩阵的时间。我们有递归式 [ T(n) \leq 2T(n/2) O(n^\omega) ] 其中 ( O(n^\omega) ) 来自步骤3和5中的矩阵乘法共6次 ( n/2 \times n/2 ) 矩阵乘。根据主定理( T(n) O(n^\omega) )。当使用目前最好的矩阵乘法算法( \omega \approx 2.371 )时这显著优于立方时间。实操心得分治法的优势在于其渐进效率。然而对于中小规模的 ( n )比如 ( n 100 )由于递归开销和常数因子较大增量法可能更快。在实际实现中可以设置一个阈值例如 ( n \leq 64 )当问题规模小于阈值时切换到增量法。此外步骤3和5中的矩阵乘法可以调用高度优化的库如BLAS、Strassen算法实现。5. 确定性编码与解码方案构建有了完美r-星匹配和对角参数矩阵求逆这两个核心工具我们现在可以按三阶段构建完整的编码解码方案。假设我们已有一个整数速率向量 ( \mathbf{r} ) 满足容量区域条件并已选定一个有限域 ( \mathbb{F}_q ) 且 ( q \Delta )最大用户度数。5.1 阶段一节点与边枚举此阶段的目标是为后续的局部解码和全局编码建立一致的编号系统。计算完美r-星匹配使用第3节的算法找到完美r-星匹配 ( M )。然后将 ( M ) 扩展为一个最大星匹配 ( M^* )使得 ( |M^| |V| )为未被 ( M ) 覆盖的存储节点任意分配一条边。( M^) 中的边称为星边其余边称为非星边。对于用户 ( u )令 ( r_u^* ) 为关联到它的星边数( N^*(u) ) 为这些星边连接的存储节点集合。全局重编号存储节点按照用户端点的升序用户相同时任意枚举所有星边。相应地对存储节点重新编号使得第 ( j ) 条星边的存储端点获得新编号 ( j )。这样存储节点编号 ( 0 ) 到 ( |V|-1 ) 与星边一一对应。局部枚举邻居边对每个用户 ( u )将其关联的边排序先排所有 ( |N(u)| - r_u^* ) 条非星边按存储节点编号升序再排所有 ( r_u^* ) 条星边按存储节点编号升序。记 ( \pi_u(i) ) 为用户 ( u ) 的第 ( i ) 条边连接的存储节点编号。这个枚举过程确保了逻辑的一致性星边对应的存储节点具有连续的编号0到|V|-1并且每个用户都知道其邻居节点在本地列表中的顺序。5.2 阶段二局部解码设计此阶段为每个用户定义其解码过程基于多点多项式插值。构造局部插值多项式每个用户 ( u ) 将获得 ( |N(u)| ) 个符号用于构造一个次数小于 ( |N(u)| ) 的多项式 ( q_u(x) )( r_u^* - r_u ) 个噪声符号仅用于混淆( r_u ) 个秘密符号用户自己的数据( |N(u)| - r_u^* ) 个虚拟符号将在全局编码中被消去 令 ( \mathbf{X}_u ) 为噪声和秘密符号组成的向量先噪声后秘密( \mathbf{Z}u ) 为虚拟符号向量。则 [ q_u(x) p{\mathbf{Z}u}(x) x^{|N(u)| - r_u^*} p{\mathbf{X}u}(x) ] 其中 ( p{\mathbf{a}}(x) \sum_i a_i x^i )。指定插值点对每个用户 ( u ) 的每条边 ( (u, v) ) 对应一个插值点对 ( (\alpha, \beta) )插值点( \alpha )固定为有限域本原元 ( \gamma ) 的幂即对于用户 ( u ) 的第 ( i ) 条边( \alpha \gamma^i )。插值值( \beta )等于存储节点 ( v ) 上的份额 ( Y_v ) 乘以该边的缩放因子( \lambda_v )。 缩放因子规则非星边的缩放因子固定为1星边 ( (u, v) ) 的缩放因子 ( \lambda_v \in {\pm 1} ) 是一个待定的参数每个存储节点 ( v ) 对应一个唯一的 ( \lambda_v )。建立局部插值方程对于用户 ( u ) 的第 ( i ) 条边其连接的存储节点为 ( v \pi_u(i) )建立方程若 ( i |N(u)| - r_u^* )对应非星边或虚拟符号部分( q_u(\gamma^i) Y_v )。若 ( i \geq |N(u)| - r_u^* )对应星边或秘密/噪声部分( q_u(\gamma^i) \lambda_v Y_v )。 这样用户 ( u ) 就得到了 ( |N(u)| ) 个方程未知数是其 ( |N(u)| ) 个本地符号( \mathbf{Z}_u ) 和 ( \mathbf{X}_u )。给定份额向量 ( \mathbf{Y} ) 和缩放因子向量 ( \boldsymbol{\lambda} )用户 ( u ) 可以通过 ( O(|N(u)| \log^2 |N(u)|) ) 时间的快速多点插值算法恢复出其秘密符号 ( \mathbf{X}_u )。5.3 阶段三全局编码实现此阶段的目标是确定缩放因子 ( \boldsymbol{\lambda} ) 并计算份额 ( \mathbf{Y} )。将所有用户的秘密和噪声符号堆叠成向量 ( \mathbf{X} )长度为 ( |V| )。消去虚拟变量形成核心方程将每个用户 ( u ) 的 ( |N(u)| ) 个局部方程写成矩阵形式。利用快速傅里叶矩阵的块LU分解和高斯消去可以消去所有虚拟变量 ( \mathbf{Z}u )为每个用户 ( u ) 得到 ( r_u^* ) 个只包含份额 ( Y ) 和缩放因子 ( \lambda ) 的方程。将所有用户的这些方程组合起来得到一个 ( |V| \times |V| ) 的线性系统 [ A(\boldsymbol{\lambda}) \mathbf{Y} B \mathbf{X} ] 其中 ( A(\boldsymbol{\lambda}) \text{diag}(\boldsymbol{\lambda}) C ) 是一个对角参数矩阵( B ) 是一个由舒尔补 ( F/F{11} ) 组成的块对角常数矩阵且可逆。求解线性系统使用第4节的分治求逆算法确定性地选择 ( \boldsymbol{\lambda} \in {\pm 1}^{|V|} ) 使得 ( A(\boldsymbol{\lambda}) ) 可逆并计算 ( A^{-1} )。关键优化我们不显式计算矩阵乘积 ( A^{-1}B )这需要 ( O(|V|^\omega) ) 时间且 ( \omega 2 )。相反对于给定的秘密/噪声向量 ( \mathbf{X} )编码过程分两步计算 ( \mathbf{Y} ) a. 计算 ( \mathbf{b} B \mathbf{X} )。由于 ( B ) 是块对角矩阵且每个块是 ( r_u^* \times r_u^* ) 的矩阵这可以在 ( O(\sum_u (r_u^*)^2) \leq O(|V|^2) ) 时间内完成通常更快因为块可能很小。 b. 计算 ( \mathbf{Y} A^{-1} \mathbf{b} )。利用分治求逆后得到的 ( A^{-1} ) 的表示通常是因子化的形式如LU分解可以在 ( O(|V|^2) ) 时间内求解这个线性系统。 因此每次编码的复杂度为 ( O(|V|^2) )与秘密数量线性相关部分的计算是高效的。整体复杂度阶段一匹配需要 ( O(\min{|U|, r(U)^{1/2}} |E|) ) 时间阶段二无计算成本阶段三中构建矩阵 ( A, B ) 需要 ( O(|V| \Delta \log^2 \Delta |V|^2) ) 时间求逆需要 ( O(|V|^\omega) ) 时间。由于 ( \Delta \leq |V| ) 且 ( \omega 2 )总主导复杂度为 ( O(\min{|U|, r(U)^{1/2}} |E| |V|^\omega) )。5.4 弱隐私性证明简述弱隐私性的证明基于信息论。核心观察是由于我们引入了独立的噪声符号并且编码是线性的且满秩最终的份额向量 ( \mathbf{Y} ) 在 ( \mathbb{F}_q ) 上是均匀分布且各分量相互独立的。对于任意两个不同用户 ( u ) 和 ( u )我们需要证明 ( H(W_u | Y_{N(u)}) H(W_u) )。证明的关键是利用私有度约束( r_u \leq b_u \leq |N(u) \setminus N(u)| )。这意味着用户 ( u ) 至少有 ( r_u ) 个邻居存储节点是 ( u )无法访问的。记这个集合为 ( T )且 ( |T| r_u )。我们可以证明在已知 ( u ) 的秘密 ( W_u ) 和 ( u ) 无法访问的那些份额 ( Y_{V \setminus T} ) 的条件下能够唯一确定 ( u ) 无法访问但 ( u ) 可以访问的份额 ( Y_T )。具体地从用户 ( u ) 的插值方程中利用 ( N(u) \setminus T ) 对应的方程涉及 ( Y_{N(u)\setminus T} )可以解出 ( u ) 所有的虚拟和噪声符号因为对应的范德蒙德子矩阵可逆。再利用 ( T ) 对应的方程结合已解出的虚拟/噪声符号和 ( W_u )可以解出 ( Y_T )。 因此有 ( H(Y_T | W_u, Y_{V\setminus T}) 0 )。由于 ( N(u) \subseteq V \setminus T )并且所有份额相互独立通过一系列信息熵的不等式推导最终可以得出 ( H(W_u | Y_{N(u)}) H(W_u) )。这严格证明了弱隐私性。6. 实现细节、性能对比与扩展讨论6.1 具体实现步骤与示例为了更具体地说明我们用一个简化示例贯穿整个流程。假设系统如图6所示有4个用户U0-U3和8个存储节点V0-V7连接关系如图。速率向量为 ( \mathbf{r} [2, 1, 2, 1]^T )。有限域取 ( \mathbb{F}_7 )本原元 ( \gamma 3 )。阶段一匹配与枚举算法找到一个完美r-星匹配 ( M )例如边集{(U0,V0), (U0,V1), (U1,V2), (U2,V4), (U2,V5), (U3,V7)}再补充两条边得到最大星匹配 ( M^* ) 覆盖所有节点。根据 ( M^* ) 对存储节点重编号使得星边对应的节点获得编号0-7。为每个用户生成本地邻居列表 ( \pi_u )。例如用户1的列表可能是[V0, V6, V2, V3]前两个是非星边后两个是星边。阶段二局部多项式设计用户0有 ( r_0^*2 ) 条星边( r_02 ) 个秘密。假设其获得噪声符号 ( X_{0,0}^n ) 和秘密符号 ( X_{0,0}^s, X_{0,1}^s )虚拟符号 ( Z_{0,0}, Z_{0,1} )。则其多项式为 [ q_0(x) (Z_{0,0} Z_{0,1}x) x^2 (X_{0,0}^n X_{0,0}^s x X_{0,1}^s x^2) ] 注意这里为了清晰区分了噪声和秘密实际编码中它们被连续放置到 ( \mathbf{X}_0 ) 中。其插值点对为( (1, Y_2), (3, Y_7), (3^2, \lambda_0 Y_0), (3^3, \lambda_1 Y_1) )。阶段三全局编码对所有用户执行类似操作消去虚拟变量后得到形如 ( A\mathbf{Y} B\mathbf{X} ) 的8个方程。其中 ( A ) 是一个 ( 8\times8 ) 的对角参数矩阵如正文公式(5)所示。使用分治求逆法确定 ( \lambda_0,...,\lambda_7 ) 的赋值例如全为1除了 ( \lambda_7 -1 )并得到 ( A^{-1} )。对于给定的秘密向量 ( \mathbf{X} )计算 ( \mathbf{b} B\mathbf{X} )再求解 ( \mathbf{Y} A^{-1}\mathbf{b} )即得到最终的8个份额。6.2 与随机化方案的性能对比特性Khalesi等人 (2021) 随机化方案本文确定性方案算法性质随机化蒙特卡洛完全确定性成功保证概率性依赖大域绝对成功只要 ( q \Delta )有限域大小要求( q \ggE单次编码复杂度( O(U渐进优势-显著更优尤其是当 (可复现性否依赖随机种子是相同输入总是相同输出硬件友好性差需要大域运算好支持小域如 ( \mathbb{F}{31}, \mathbb{F}{127} )我们的方案在渐进复杂度上具有明显优势。例如在一个密集图中( |E| \approx |U| |V| )随机化方案单次运行复杂度为 ( O(|U|^3 |V|^3) )而我们的方案为 ( O(\min{|U|, |V|^{1/2}} |U| |V| |V|^\omega) )。当 ( |U| ) 和 ( |V| ) 增长时我们的方案要快得多。6.3 实际部署考量与优化建议有限域选择方案仅要求 ( q \Delta ) 且为奇素数或素数幂。为了硬件效率应选择支持快速运算的域。例如( \mathbb{F}_{2^m} )特征为2在硬件中加法是XOR乘法有专用优化。但需注意 ( q 2^m \Delta )。小奇素数域 ( \mathbb{F}_p )如 ( p31, 127 )运算简单适合软件实现。应避免选择过大的域因为域上乘法和求逆是主要开销。匹配算法选择对于非常稀疏的图( |E| \ll |U| |V| )简单的增广路径算法可能就足够了。对于稠密图我们的特化Dinic算法或成熟的Push-Relabel算法都是好选择。可以优先使用现成的最大流库进行性能测试。矩阵求逆的阈值在实现分治求逆时如6.3节所述应设置一个递归基阈值。当子问题规模小于阈值如32或64时切换到增量法或直接使用高斯消去以避免递归开销。预计算与存储编码矩阵 ( A^{-1}B )或更准确地说求解 ( A^{-1}\mathbf{b} ) 的因子化表示仅依赖于图拓扑和速率向量 ( \mathbf{r} )而与具体的秘密值无关。因此在系统初始化阶段可以预计算并存储这些信息。之后每次编码只需进行 ( O(|V|^2) ) 的矩阵向量乘法这对于流式秘密共享是高效的。解码优化每个用户 ( u ) 的解码复杂度为 ( O(|N(u)| \log^2 |N(u)|) )这得益于快速傅里叶变换FFT在有限域上的变体如数论变换NTT。对于邻居数较多的用户这是显著的优化。6.4 局限性与未来方向尽管我们的工作取得了理论上的突破但在走向实际应用时仍需考虑以下方面非整数速率我们的算法目前只处理整数速率向量 ( \mathbf{r} )。对于容量区域内的非整数点需要通过时间共享或空间共享将秘密符号分组对不同组应用不同的整数速率方案来逼近。一个有趣的开放问题是如何高效地将一个非整数速率向量分解为少数几个整数速率向量的凸组合即Carathéodory定理的算法版本我们初步认为基于本文建立的完美星匹配与网络流的等价关系可以利用多商品流或子模优化技术来设计高效分解算法。速率分配优化在实际系统中用户的速率需求可能不同。如何根据应用目标如最大最小公平性、比例公平性、总吞吐量最大化在容量区域内进行最优速率分配是一个自然的凸优化问题。由于容量区域由指数数量的共享约束定义直接求解可能困难。未来研究可以探索如何利用横截拟阵的性质设计更高效的专用优化算法。数值稳定性虽然我们在有限域上工作避免了浮点误差但当域大小 ( q ) 接近 ( \Delta ) 时矩阵 ( A(\boldsymbol{\lambda}) ) 可能接近奇异尽管理论上存在可逆的 ( \boldsymbol{\lambda} )求逆过程可能对计算误差更敏感。在实际编码中需要确保使用精确的有限域运算库。实验验证本文侧重于理论算法设计。未来的工作需要在真实数据集和不同规模的图上进行广泛的性能基准测试比较确定性算法与随机化算法在运行时间、内存消耗和通信开销上的实际表现特别是在分布式存储系统原型中的集成测试。我们的确定性算法为分布式多用户秘密共享提供了一个高效、可靠、可复现的构建模块。它降低了实现门槛使得在资源受限的环境如物联网设备、边缘计算节点中部署信息论安全的分布式存储和计算成为可能。通过将复杂的容量区域理论转化为具体的图匹配和矩阵求逆算法我们为后续的研究和工程实践奠定了坚实的基础。
分布式多用户秘密共享：确定性算法实现与硬件友好编码
发布时间：2026/5/27 19:28:08
1. 项目概述在分布式计算和存储系统中如何让多个用户安全地存储和共享各自的秘密信息同时确保每个用户只能访问自己的秘密而无法窥探他人的数据是一个经典且具有挑战性的问题。这就是分布式多用户秘密共享Distributed Multi-User Secret Sharing, DMUSS的核心目标。想象一下一个公司有多个部门每个部门都有自己敏感的预算数据他们希望将这些数据加密后分散存储在公司内部的多个服务器上。任何单个服务器都无法获取完整的预算信息但每个部门的授权人员可以仅从他们被允许访问的服务器子集中恢复出自己部门的完整数据并且无法计算出其他部门的任何信息。这就是DMUSS要解决的现实场景。传统的秘密共享方案如经典的Shamir门限方案主要针对单个秘密在多个参与者之间的分割。而DMUSS将其扩展到了一个更复杂的网络模型一个由用户U和存储节点V组成的二分图。每个用户连接着多个存储节点其“邻居”节点。一个可信的“分发者”将每个用户的秘密信息可能长度不同与一些随机噪声一起进行全局编码生成与存储节点数量相等的份额并分发到各个节点。系统需要满足两个核心要求正确性每个用户能从其邻居节点的份额中解码出自己的秘密和弱隐私性任何用户从其邻居节点的份额中无法获得关于其他用户秘密的任何信息论意义上的信息。Khalesi等人在2021年从信息论角度完整刻画了弱隐私和正确性约束下的容量区域Capacity Region即所有可实现的用户速率秘密信息大小与节点存储大小的比值的集合。然而他们的编码方案依赖于一个随机化的蒙特卡洛过程其成功概率取决于一个非常大的有限域的选择。这在实际应用中带来了两个主要问题1.随机性失败风险算法可能因随机种子不佳而失败2.实现复杂度高需要非常大的有限域这在硬件实现如嵌入式系统、专用集成电路中效率低下因为大域上的算术运算如乘法、求逆非常昂贵。我们的工作正是为了弥合这一理论与实现之间的鸿沟。我们提出了一种完全确定性的、多项式时间的算法能够在硬件友好的小有限域仅需域的大小大于最大用户度数Δ上实现容量区域内所有整数速率点。我们的算法在渐进复杂度上显著优于单次蒙特卡洛运行并首次为已知的容量区域提供了明确的确定性构造为分布式秘密共享的算法基础迈出了坚实的一步。2. 系统模型与核心挑战解析2.1 二分图模型与问题形式化我们用一个连通二分图 ( G (U, V; E) ) 来形式化分布式系统。其中( U {0, 1, ..., |U|-1} ) 是用户集合至少2个。( V ) 是存储节点集合至少2个且假设大小相同。( E \subseteq U \times V ) 是边集表示用户与存储节点之间的连接关系。分发者持有 ( |U| ) 个独立的秘密消息每个用户 ( u ) 对应一个其长度为 ( L_u ) 个符号来自有限域 ( \mathbb{F}q )( q ) 为域的大小。定义用户 ( u ) 的速率( r_u L_u / L )其中 ( L ) 是每个存储节点的份额大小也以域符号计。因此一个速率向量 ( \mathbf{r} (r_0, r_1, ..., r{|U|-1}) ) 描述了所有用户秘密的相对大小。分发者的编码函数将 ( \sum_{u \in U} L_u ) 个秘密符号和 ( (|V| - \sum_{u \in U} L_u) ) 个随机噪声符号也来自 ( \mathbb{F}_q )共同编码成 ( |V| ) 个份额每个份额长度为 ( L )并放置到对应的存储节点。用户 ( u ) 的解码函数则仅能访问其邻居节点 ( N(u) ) 上的份额。核心约束正确性对于每个用户 ( u )存在解码函数能够从其邻居节点份额 ( Y_{N(u)} ) 中无误地恢复出其秘密消息 ( W_u )。弱隐私性对于任意两个不同的用户 ( u ) 和 ( u )用户 ( u ) 从其邻居节点份额 ( Y_{N(u)} ) 中关于 ( W_u ) 的条件熵等于其原始熵即 ( H(W_u | Y_{N(u)}) H(W_u) )。这意味着 ( Y_{N(u)} ) 不提供任何关于 ( W_u ) 的信息。2.2 容量区域与现有方案的局限Khalesi等人的工作给出了容量区域的精确信息论刻画。对于速率向量 ( \mathbf{r} )其属于容量区域当且仅当满足以下两个条件私有度约束对于每个用户 ( u )有 ( r_u \leq b_u : \min_{u \neq u} |N(u) \setminus N(u)| )。这保证了每个用户的秘密有足够多的“独家”邻居节点来隐藏信息。共享约束对于用户的任意子集 ( S \subseteq U )有 ( r(S) : \sum_{u \in S} r_u \leq |N(S)| )。这保证了分配给子集 ( S ) 中用户的总信息量不超过其所能访问的存储节点总数。满足共享约束的向量集合在组合优化中被称为横截拟阵。因此容量区域就是这个拟阵被私有度向量 ( \mathbf{b} ) 截断后的部分其所有顶点都是整数值的。尽管这个刻画非常优美但其实现方案存在痛点随机化编码方案依赖于Schwartz-Zippel引理随机选择编码矩阵的系数。单次蒙特卡洛运行的时间复杂度高达 ( O(|U|^3 |V|^3) )。大域要求为确保高成功概率所需有限域的大小 ( q ) 需要远大于边数 ( |E| )而不仅仅是大于最大用户度数 ( \Delta )。这在实践中意味着需要实现 ( \mathbb{F}_{2^{64}} ) 或更大的域其算术运算开销巨大。无多项式时间保证没有理论保证能在多项式次尝试内必然成功。这些局限使得该方案难以应用于对确定性、可复现性、计算效率和硬件友好性有高要求的场景。2.3 确定性算法的核心思路我们的目标是为容量区域内的任意整数速率向量 ( \mathbf{r} )即每个 ( r_u ) 为整数构造一个确定性的编码解码方案。核心思路是将编码过程分解为三个逻辑清晰的阶段并引入两个关键的算法原语来高效解决其中的组合与代数问题完美r-星匹配我们将“共享约束”这一抽象的组合条件转化为在二分图中寻找一个特定的子图结构——完美r-星匹配。这相当于为每个用户的 ( r_u ) 个秘密符号分配 ( r_u ) 条专属的“星边”连接到不同的存储节点并且所有用户的星边覆盖所有存储节点。这个匹配的存在性等价于速率向量满足共享约束。我们将展示如何用最大流算法在 ( O(\min{|U|, r(U)^{1/2}} |E|) ) 时间内找到这样的匹配。对角参数矩阵求逆编码过程最终会归结为求解一个线性系统 ( A(\boldsymbol{\lambda}) \mathbf{Y} B \mathbf{X} )其中 ( A(\boldsymbol{\lambda}) ) 是一个对角线上元素为参数 ( \lambda_v \in {\pm 1} ) 的矩阵( B ) 是常数矩阵( \mathbf{X} ) 是秘密和噪声符号向量( \mathbf{Y} ) 是待求的份额向量。我们需要确定性地选择 ( \boldsymbol{\lambda} ) 使得 ( A(\boldsymbol{\lambda}) ) 可逆并计算其逆。我们提出了两种算法增量求逆法( O(n^3) )和分治求逆法( O(n^\omega) )( \omega \approx 2.371 ) 是矩阵乘法指数后者具有更优的渐进复杂。通过结合快速多项式多点求值/插值、基于最大流的匹配算法以及确定性的矩阵求逆我们最终得到一个总时间复杂度为 ( O(\min{|U|, r(U)^{1/2}} |E| |V|^\omega) ) 的确定性算法并且仅要求有限域大小 ( q \Delta )。3. 核心算法原语完美r-星匹配3.1 从组合约束到流网络“完美r-星匹配”是一个直观的图论概念。在一个二分图 ( G(U, V; E) ) 中一个边集 ( M \subseteq E ) 称为星匹配如果 ( V ) 中的每个节点至多与 ( M ) 中的一条边相关联。一个r-星匹配要求每个用户节点 ( u ) 至多与 ( M ) 中的 ( r_u ) 条边相关联。如果每个用户 ( u ) 恰好关联 ( r_u ) 条边并且覆盖了所有存储节点即 ( |M| \sum_u r_u |V| )则称之为完美的。定理1存在完美r-星匹配当且仅当速率向量 ( \mathbf{r} ) 满足共享约束 ( r(S) \leq |N(S)|, \forall S \subseteq U )。因此验证 ( \mathbf{r} ) 是否在容量区域内并满足私有度约束等价于寻找一个完美r-星匹配。我们通过将其转化为最大流问题来高效求解。我们构造一个流网络 ( D )源点 ( s ) 连接到每个用户 ( u )容量为 ( r_u )。每个用户 ( u ) 连接到其所有邻居存储节点 ( v \in N(u) )容量设为无穷大或一个足够大的数如 ( 2|V| )。每个存储节点 ( v ) 连接到汇点 ( t )容量为1。在这个网络中一个整数值的 ( s-t ) 流 ( f ) 直接对应一个r-星匹配 ( M_f )如果边 ( (u, v) ) 上承载了1单位的流则 ( (u, v) \in M_f )。流的值 ( val(f) ) 就等于匹配 ( M_f ) 的大小。因此寻找最大r-星匹配等价于在 ( D ) 中寻找最大流。3.2 高效的最大流算法实现直接应用经典的Hopcroft-Karp算法针对二分图匹配或Even-Tarjan算法针对边不相交路径无法达到我们目标的时间复杂度 ( O(\min{|U|, \phi^{1/2}} |E|) )其中 ( \phi ) 是最大匹配的大小。我们采用Dinic阻塞流算法的一个特化版本。我们首先将网络 ( D ) 中所有从用户到存储节点的边容量设为1“瘦身”变体这不会改变最大整数值流的存在性。Dinic算法的核心是反复在层次图由最短增广路径构成的子图中寻找阻塞流即发送尽可能多的流使得发送后层次图中不再存在 ( s-t ) 路径。每次阻塞流增广后( s-t ) 的最短距离严格增加。我们的特化在于高效实现每次阻塞流查找。在层次图 ( L_f ) 中我们将每条边 ( (s, u) ) 替换为 ( c_f(u) r_u - f(u) ) 条平行边得到图 ( L_f^ )。在 ( L_f^ ) 中寻找一个极大的边不相交 ( s-t ) 路径集合这可以在 ( O(|E|) ) 时间内通过深度优先搜索完成因为 ( L_f^ ) 是无环的。因此每次迭代构建层次图、寻找阻塞流、增广的时间为 ( O(|E|) )。迭代次数上界由于每次增广后最短距离至少增加2因为层次图是二分图且边容量为1而最短距离不超过 ( 2|U|1 )所以迭代次数为 ( O(|U|) )。通过分析最优性间隙 ( \phi - |M_f| ) 的下降速度我们可以证明迭代次数也为 ( O(\phi^{1/2}) )。具体来说经过 ( k ) 次迭代后有 ( \phi - |M_f| \leq \phi / (k1) )。因此在 ( \lceil \phi^{1/2} \rceil ) 次迭代后间隙最多为 ( \phi^{1/2} )再经过最多 ( \lceil \phi^{1/2} \rceil ) 次迭代即可达到最大流。因此总时间复杂度为 ( O(\min{|U|, \phi^{1/2}} |E|) )。当 ( \mathbf{r} ) 满足共享约束时( \phi r(U) )我们就能在 ( O(\min{|U|, r(U)^{1/2}} |E|) ) 时间内找到一个完美r-星匹配。实操心得在实际编码中我们通常使用高度优化的最大流库如Python的networkx或C的Boost.Graph。但理解这个特化版本的原理很重要因为它解释了为什么我们的算法比通用最大流算法更适合这个问题。对于中等规模的图|U|, |V|在几百量级Dinic算法已经非常高效。当 ( r(U) ) 较小时( O(r(U)^{1/2} |E|) ) 的界尤其有利。4. 核心算法原语对角参数矩阵求逆4.1 问题定义与重要性在编码的第三阶段我们会得到一个形如 ( A(\boldsymbol{\lambda}) \mathbf{Y} B \mathbf{X} ) 的线性系统其中 ( A(\boldsymbol{\lambda}) \text{diag}(\boldsymbol{\lambda}) C )( C ) 是一个常数矩阵( \boldsymbol{\lambda} (\lambda_0, ..., \lambda_{n-1})^T )( n |V| )并且我们需要选择 ( \lambda_v \in {\pm 1} \subset \mathbb{F}_q ) 使得 ( A(\boldsymbol{\lambda}) ) 可逆。这里的 ( \lambda_v ) 代表了存储节点 ( v ) 的“缩放因子”。为什么是 ±1首先( \det(A(\boldsymbol{\lambda})) ) 是关于 ( \boldsymbol{\lambda} ) 的多项式其最高次项 ( \lambda_0 \lambda_1 ... \lambda_{n-1} ) 的系数为1因为来自对角矩阵。根据组合零化引理对于一个至少包含3个元素的有限域 ( \mathbb{F}_q )该多项式不可能在集合 ( {\pm 1}^n ) 的所有点上为零除非是零多项式但最高次项系数为1保证了它不是。因此我们总能从 ( {\pm 1}^n ) 中找到一个赋值使得矩阵可逆。选择 ±1 极大地简化了计算因为它们在小域如 ( \mathbb{F}_q )( q ) 为奇素数中通常是简单的元素乘法就是取负号。4.2 增量求逆法这是一种直观且易于实现的方法适合小规模问题( n ) 较小。算法步骤 令 ( A_i ) 为 ( A ) 的 ( i ) 阶前主子矩阵即由前 ( i1 ) 行和列组成的子矩阵。我们从 ( i0 ) 开始迭代到 ( in-1 )。初始化对于 ( A_0 [\lambda_0 c_{0,0}] )选择 ( \lambda_0 ) 使得该标量非零若 ( c_{0,0} -1 )则令 ( \lambda_0 1 )否则令 ( \lambda_0 -1 )。计算 ( A_0^{-1} [(\lambda_0 c_{0,0})^{-1}] )。迭代假设我们已经确定了 ( \lambda_0, ..., \lambda_{i-1} ) 并计算出了 ( A_{i-1}^{-1} )。将 ( A_i ) 分块为 [ A_i \begin{pmatrix} A_{i-1} \mathbf{v} \ \mathbf{u}^T \lambda_i c_{i,i} \end{pmatrix} ] 其舒尔补为 ( S \lambda_i c_{i,i} - \mathbf{u}^T A_{i-1}^{-1} \mathbf{v} )。选择( \lambda_i )计算标量 ( t \mathbf{u}^T A_{i-1}^{-1} \mathbf{v} - c_{i,i} )。若 ( t 1 )则令 ( \lambda_i -1 )否则令 ( \lambda_i 1 )。这保证了 ( S \neq 0 )。更新逆矩阵利用分块求逆公式计算 ( A_i^{-1} ) [ \theta S^{-1}, \quad A_i^{-1} \begin{pmatrix} A_{i-1}^{-1} \theta (A_{i-1}^{-1} \mathbf{v} \mathbf{u}^T A_{i-1}^{-1}) -\theta A_{i-1}^{-1} \mathbf{v} \ -\theta \mathbf{u}^T A_{i-1}^{-1} \theta \end{pmatrix} ]时间复杂度每次迭代需要计算 ( A_{i-1}^{-1} \mathbf{v} )、( \mathbf{u}^T A_{i-1}^{-1} ) 和 ( \mathbf{u}^T A_{i-1}^{-1} \mathbf{v} )这需要 ( O(i^2) ) 时间。因此总时间为 ( \sum_{i1}^{n-1} O(i^2) O(n^3) )。注意事项增量法虽然简单但每次迭代都需更新整个逆矩阵即使矩阵 ( C ) 是稀疏的其逆矩阵 ( A^{-1} ) 也可能是稠密的。因此对于 ( n ) 较大的情况例如几百以上立方复杂度将成为瓶颈。4.3 分治求逆法为了获得更优的渐进复杂度我们借鉴Strassen矩阵求逆的思想采用分治策略并利用快速矩阵乘法。算法步骤假设 ( n ) 是2的幂非2的幂可通过填充虚拟变量处理分治将矩阵 ( A ) 划分为四个 ( n/2 \times n/2 ) 的块 [ A \begin{pmatrix} A_{11} A_{12} \ A_{21} A_{22} \end{pmatrix} ] 其中 ( A_{11} \text{diag}(\boldsymbol{\lambda}1) C{11} )( A_{22} \text{diag}(\boldsymbol{\lambda}2) C{22} )。递归求逆( A_{11} )递归调用分治算法得到 ( \boldsymbol{\lambda}1 ) 的赋值和 ( A{11}^{-1} )。计算舒尔补计算 ( S A/A_{11} A_{22} - A_{21} A_{11}^{-1} A_{12} )。关键点在于( A_{21} )、( A_{12} ) 和 ( A_{11}^{-1} ) 现在都是常数矩阵因为 ( \boldsymbol{\lambda}_1 ) 已确定所以 ( S ) 仍然是一个对角参数矩阵形式为 ( \text{diag}(\boldsymbol{\lambda}_2) C )。递归求逆舒尔补递归调用分治算法求 ( S^{-1} )并得到 ( \boldsymbol{\lambda}_2 ) 的赋值。合并结果利用分块求逆公式计算 ( A^{-1} ) [ A^{-1} \begin{pmatrix} A_{11}^{-1} A_{11}^{-1} A_{12} S^{-1} A_{21} A_{11}^{-1} -A_{11}^{-1} A_{12} S^{-1} \ -S^{-1} A_{21} A_{11}^{-1} S^{-1} \end{pmatrix} ]时间复杂度分析设 ( T(n) ) 为处理 ( n \times n ) 矩阵的时间。我们有递归式 [ T(n) \leq 2T(n/2) O(n^\omega) ] 其中 ( O(n^\omega) ) 来自步骤3和5中的矩阵乘法共6次 ( n/2 \times n/2 ) 矩阵乘。根据主定理( T(n) O(n^\omega) )。当使用目前最好的矩阵乘法算法( \omega \approx 2.371 )时这显著优于立方时间。实操心得分治法的优势在于其渐进效率。然而对于中小规模的 ( n )比如 ( n 100 )由于递归开销和常数因子较大增量法可能更快。在实际实现中可以设置一个阈值例如 ( n \leq 64 )当问题规模小于阈值时切换到增量法。此外步骤3和5中的矩阵乘法可以调用高度优化的库如BLAS、Strassen算法实现。5. 确定性编码与解码方案构建有了完美r-星匹配和对角参数矩阵求逆这两个核心工具我们现在可以按三阶段构建完整的编码解码方案。假设我们已有一个整数速率向量 ( \mathbf{r} ) 满足容量区域条件并已选定一个有限域 ( \mathbb{F}_q ) 且 ( q \Delta )最大用户度数。5.1 阶段一节点与边枚举此阶段的目标是为后续的局部解码和全局编码建立一致的编号系统。计算完美r-星匹配使用第3节的算法找到完美r-星匹配 ( M )。然后将 ( M ) 扩展为一个最大星匹配 ( M^* )使得 ( |M^| |V| )为未被 ( M ) 覆盖的存储节点任意分配一条边。( M^) 中的边称为星边其余边称为非星边。对于用户 ( u )令 ( r_u^* ) 为关联到它的星边数( N^*(u) ) 为这些星边连接的存储节点集合。全局重编号存储节点按照用户端点的升序用户相同时任意枚举所有星边。相应地对存储节点重新编号使得第 ( j ) 条星边的存储端点获得新编号 ( j )。这样存储节点编号 ( 0 ) 到 ( |V|-1 ) 与星边一一对应。局部枚举邻居边对每个用户 ( u )将其关联的边排序先排所有 ( |N(u)| - r_u^* ) 条非星边按存储节点编号升序再排所有 ( r_u^* ) 条星边按存储节点编号升序。记 ( \pi_u(i) ) 为用户 ( u ) 的第 ( i ) 条边连接的存储节点编号。这个枚举过程确保了逻辑的一致性星边对应的存储节点具有连续的编号0到|V|-1并且每个用户都知道其邻居节点在本地列表中的顺序。5.2 阶段二局部解码设计此阶段为每个用户定义其解码过程基于多点多项式插值。构造局部插值多项式每个用户 ( u ) 将获得 ( |N(u)| ) 个符号用于构造一个次数小于 ( |N(u)| ) 的多项式 ( q_u(x) )( r_u^* - r_u ) 个噪声符号仅用于混淆( r_u ) 个秘密符号用户自己的数据( |N(u)| - r_u^* ) 个虚拟符号将在全局编码中被消去 令 ( \mathbf{X}_u ) 为噪声和秘密符号组成的向量先噪声后秘密( \mathbf{Z}u ) 为虚拟符号向量。则 [ q_u(x) p{\mathbf{Z}u}(x) x^{|N(u)| - r_u^*} p{\mathbf{X}u}(x) ] 其中 ( p{\mathbf{a}}(x) \sum_i a_i x^i )。指定插值点对每个用户 ( u ) 的每条边 ( (u, v) ) 对应一个插值点对 ( (\alpha, \beta) )插值点( \alpha )固定为有限域本原元 ( \gamma ) 的幂即对于用户 ( u ) 的第 ( i ) 条边( \alpha \gamma^i )。插值值( \beta )等于存储节点 ( v ) 上的份额 ( Y_v ) 乘以该边的缩放因子( \lambda_v )。 缩放因子规则非星边的缩放因子固定为1星边 ( (u, v) ) 的缩放因子 ( \lambda_v \in {\pm 1} ) 是一个待定的参数每个存储节点 ( v ) 对应一个唯一的 ( \lambda_v )。建立局部插值方程对于用户 ( u ) 的第 ( i ) 条边其连接的存储节点为 ( v \pi_u(i) )建立方程若 ( i |N(u)| - r_u^* )对应非星边或虚拟符号部分( q_u(\gamma^i) Y_v )。若 ( i \geq |N(u)| - r_u^* )对应星边或秘密/噪声部分( q_u(\gamma^i) \lambda_v Y_v )。 这样用户 ( u ) 就得到了 ( |N(u)| ) 个方程未知数是其 ( |N(u)| ) 个本地符号( \mathbf{Z}_u ) 和 ( \mathbf{X}_u )。给定份额向量 ( \mathbf{Y} ) 和缩放因子向量 ( \boldsymbol{\lambda} )用户 ( u ) 可以通过 ( O(|N(u)| \log^2 |N(u)|) ) 时间的快速多点插值算法恢复出其秘密符号 ( \mathbf{X}_u )。5.3 阶段三全局编码实现此阶段的目标是确定缩放因子 ( \boldsymbol{\lambda} ) 并计算份额 ( \mathbf{Y} )。将所有用户的秘密和噪声符号堆叠成向量 ( \mathbf{X} )长度为 ( |V| )。消去虚拟变量形成核心方程将每个用户 ( u ) 的 ( |N(u)| ) 个局部方程写成矩阵形式。利用快速傅里叶矩阵的块LU分解和高斯消去可以消去所有虚拟变量 ( \mathbf{Z}u )为每个用户 ( u ) 得到 ( r_u^* ) 个只包含份额 ( Y ) 和缩放因子 ( \lambda ) 的方程。将所有用户的这些方程组合起来得到一个 ( |V| \times |V| ) 的线性系统 [ A(\boldsymbol{\lambda}) \mathbf{Y} B \mathbf{X} ] 其中 ( A(\boldsymbol{\lambda}) \text{diag}(\boldsymbol{\lambda}) C ) 是一个对角参数矩阵( B ) 是一个由舒尔补 ( F/F{11} ) 组成的块对角常数矩阵且可逆。求解线性系统使用第4节的分治求逆算法确定性地选择 ( \boldsymbol{\lambda} \in {\pm 1}^{|V|} ) 使得 ( A(\boldsymbol{\lambda}) ) 可逆并计算 ( A^{-1} )。关键优化我们不显式计算矩阵乘积 ( A^{-1}B )这需要 ( O(|V|^\omega) ) 时间且 ( \omega 2 )。相反对于给定的秘密/噪声向量 ( \mathbf{X} )编码过程分两步计算 ( \mathbf{Y} ) a. 计算 ( \mathbf{b} B \mathbf{X} )。由于 ( B ) 是块对角矩阵且每个块是 ( r_u^* \times r_u^* ) 的矩阵这可以在 ( O(\sum_u (r_u^*)^2) \leq O(|V|^2) ) 时间内完成通常更快因为块可能很小。 b. 计算 ( \mathbf{Y} A^{-1} \mathbf{b} )。利用分治求逆后得到的 ( A^{-1} ) 的表示通常是因子化的形式如LU分解可以在 ( O(|V|^2) ) 时间内求解这个线性系统。 因此每次编码的复杂度为 ( O(|V|^2) )与秘密数量线性相关部分的计算是高效的。整体复杂度阶段一匹配需要 ( O(\min{|U|, r(U)^{1/2}} |E|) ) 时间阶段二无计算成本阶段三中构建矩阵 ( A, B ) 需要 ( O(|V| \Delta \log^2 \Delta |V|^2) ) 时间求逆需要 ( O(|V|^\omega) ) 时间。由于 ( \Delta \leq |V| ) 且 ( \omega 2 )总主导复杂度为 ( O(\min{|U|, r(U)^{1/2}} |E| |V|^\omega) )。5.4 弱隐私性证明简述弱隐私性的证明基于信息论。核心观察是由于我们引入了独立的噪声符号并且编码是线性的且满秩最终的份额向量 ( \mathbf{Y} ) 在 ( \mathbb{F}_q ) 上是均匀分布且各分量相互独立的。对于任意两个不同用户 ( u ) 和 ( u )我们需要证明 ( H(W_u | Y_{N(u)}) H(W_u) )。证明的关键是利用私有度约束( r_u \leq b_u \leq |N(u) \setminus N(u)| )。这意味着用户 ( u ) 至少有 ( r_u ) 个邻居存储节点是 ( u )无法访问的。记这个集合为 ( T )且 ( |T| r_u )。我们可以证明在已知 ( u ) 的秘密 ( W_u ) 和 ( u ) 无法访问的那些份额 ( Y_{V \setminus T} ) 的条件下能够唯一确定 ( u ) 无法访问但 ( u ) 可以访问的份额 ( Y_T )。具体地从用户 ( u ) 的插值方程中利用 ( N(u) \setminus T ) 对应的方程涉及 ( Y_{N(u)\setminus T} )可以解出 ( u ) 所有的虚拟和噪声符号因为对应的范德蒙德子矩阵可逆。再利用 ( T ) 对应的方程结合已解出的虚拟/噪声符号和 ( W_u )可以解出 ( Y_T )。 因此有 ( H(Y_T | W_u, Y_{V\setminus T}) 0 )。由于 ( N(u) \subseteq V \setminus T )并且所有份额相互独立通过一系列信息熵的不等式推导最终可以得出 ( H(W_u | Y_{N(u)}) H(W_u) )。这严格证明了弱隐私性。6. 实现细节、性能对比与扩展讨论6.1 具体实现步骤与示例为了更具体地说明我们用一个简化示例贯穿整个流程。假设系统如图6所示有4个用户U0-U3和8个存储节点V0-V7连接关系如图。速率向量为 ( \mathbf{r} [2, 1, 2, 1]^T )。有限域取 ( \mathbb{F}_7 )本原元 ( \gamma 3 )。阶段一匹配与枚举算法找到一个完美r-星匹配 ( M )例如边集{(U0,V0), (U0,V1), (U1,V2), (U2,V4), (U2,V5), (U3,V7)}再补充两条边得到最大星匹配 ( M^* ) 覆盖所有节点。根据 ( M^* ) 对存储节点重编号使得星边对应的节点获得编号0-7。为每个用户生成本地邻居列表 ( \pi_u )。例如用户1的列表可能是[V0, V6, V2, V3]前两个是非星边后两个是星边。阶段二局部多项式设计用户0有 ( r_0^*2 ) 条星边( r_02 ) 个秘密。假设其获得噪声符号 ( X_{0,0}^n ) 和秘密符号 ( X_{0,0}^s, X_{0,1}^s )虚拟符号 ( Z_{0,0}, Z_{0,1} )。则其多项式为 [ q_0(x) (Z_{0,0} Z_{0,1}x) x^2 (X_{0,0}^n X_{0,0}^s x X_{0,1}^s x^2) ] 注意这里为了清晰区分了噪声和秘密实际编码中它们被连续放置到 ( \mathbf{X}_0 ) 中。其插值点对为( (1, Y_2), (3, Y_7), (3^2, \lambda_0 Y_0), (3^3, \lambda_1 Y_1) )。阶段三全局编码对所有用户执行类似操作消去虚拟变量后得到形如 ( A\mathbf{Y} B\mathbf{X} ) 的8个方程。其中 ( A ) 是一个 ( 8\times8 ) 的对角参数矩阵如正文公式(5)所示。使用分治求逆法确定 ( \lambda_0,...,\lambda_7 ) 的赋值例如全为1除了 ( \lambda_7 -1 )并得到 ( A^{-1} )。对于给定的秘密向量 ( \mathbf{X} )计算 ( \mathbf{b} B\mathbf{X} )再求解 ( \mathbf{Y} A^{-1}\mathbf{b} )即得到最终的8个份额。6.2 与随机化方案的性能对比特性Khalesi等人 (2021) 随机化方案本文确定性方案算法性质随机化蒙特卡洛完全确定性成功保证概率性依赖大域绝对成功只要 ( q \Delta )有限域大小要求( q \ggE单次编码复杂度( O(U渐进优势-显著更优尤其是当 (可复现性否依赖随机种子是相同输入总是相同输出硬件友好性差需要大域运算好支持小域如 ( \mathbb{F}{31}, \mathbb{F}{127} )我们的方案在渐进复杂度上具有明显优势。例如在一个密集图中( |E| \approx |U| |V| )随机化方案单次运行复杂度为 ( O(|U|^3 |V|^3) )而我们的方案为 ( O(\min{|U|, |V|^{1/2}} |U| |V| |V|^\omega) )。当 ( |U| ) 和 ( |V| ) 增长时我们的方案要快得多。6.3 实际部署考量与优化建议有限域选择方案仅要求 ( q \Delta ) 且为奇素数或素数幂。为了硬件效率应选择支持快速运算的域。例如( \mathbb{F}_{2^m} )特征为2在硬件中加法是XOR乘法有专用优化。但需注意 ( q 2^m \Delta )。小奇素数域 ( \mathbb{F}_p )如 ( p31, 127 )运算简单适合软件实现。应避免选择过大的域因为域上乘法和求逆是主要开销。匹配算法选择对于非常稀疏的图( |E| \ll |U| |V| )简单的增广路径算法可能就足够了。对于稠密图我们的特化Dinic算法或成熟的Push-Relabel算法都是好选择。可以优先使用现成的最大流库进行性能测试。矩阵求逆的阈值在实现分治求逆时如6.3节所述应设置一个递归基阈值。当子问题规模小于阈值如32或64时切换到增量法或直接使用高斯消去以避免递归开销。预计算与存储编码矩阵 ( A^{-1}B )或更准确地说求解 ( A^{-1}\mathbf{b} ) 的因子化表示仅依赖于图拓扑和速率向量 ( \mathbf{r} )而与具体的秘密值无关。因此在系统初始化阶段可以预计算并存储这些信息。之后每次编码只需进行 ( O(|V|^2) ) 的矩阵向量乘法这对于流式秘密共享是高效的。解码优化每个用户 ( u ) 的解码复杂度为 ( O(|N(u)| \log^2 |N(u)|) )这得益于快速傅里叶变换FFT在有限域上的变体如数论变换NTT。对于邻居数较多的用户这是显著的优化。6.4 局限性与未来方向尽管我们的工作取得了理论上的突破但在走向实际应用时仍需考虑以下方面非整数速率我们的算法目前只处理整数速率向量 ( \mathbf{r} )。对于容量区域内的非整数点需要通过时间共享或空间共享将秘密符号分组对不同组应用不同的整数速率方案来逼近。一个有趣的开放问题是如何高效地将一个非整数速率向量分解为少数几个整数速率向量的凸组合即Carathéodory定理的算法版本我们初步认为基于本文建立的完美星匹配与网络流的等价关系可以利用多商品流或子模优化技术来设计高效分解算法。速率分配优化在实际系统中用户的速率需求可能不同。如何根据应用目标如最大最小公平性、比例公平性、总吞吐量最大化在容量区域内进行最优速率分配是一个自然的凸优化问题。由于容量区域由指数数量的共享约束定义直接求解可能困难。未来研究可以探索如何利用横截拟阵的性质设计更高效的专用优化算法。数值稳定性虽然我们在有限域上工作避免了浮点误差但当域大小 ( q ) 接近 ( \Delta ) 时矩阵 ( A(\boldsymbol{\lambda}) ) 可能接近奇异尽管理论上存在可逆的 ( \boldsymbol{\lambda} )求逆过程可能对计算误差更敏感。在实际编码中需要确保使用精确的有限域运算库。实验验证本文侧重于理论算法设计。未来的工作需要在真实数据集和不同规模的图上进行广泛的性能基准测试比较确定性算法与随机化算法在运行时间、内存消耗和通信开销上的实际表现特别是在分布式存储系统原型中的集成测试。我们的确定性算法为分布式多用户秘密共享提供了一个高效、可靠、可复现的构建模块。它降低了实现门槛使得在资源受限的环境如物联网设备、边缘计算节点中部署信息论安全的分布式存储和计算成为可能。通过将复杂的容量区域理论转化为具体的图匹配和矩阵求逆算法我们为后续的研究和工程实践奠定了坚实的基础。
