网络中的鲁棒秘密存储

# 网络中秘密信息的稳健存储 来源: https://arxiv.org/html/2606.30261 Vinko Zlatić ###### 摘要 研究了在网络中存储安全信息的问题。提出了分布式秘密存储的形式化框架，并讨论了在技术和社会系统中的可能应用。该问题被表述为鲁棒性泛函的优化，其中需要平衡两个相互竞争的要求：在网络退化过程中的生存能力和抵抗对手入侵的能力。以最小信息携带子图（MICS）的形式导出了生存能力的精确表示，该表示提供了与存储信息相关的重构事件的简化描述。然后利用该表示构建了半局部优化方法，其动态无需全局了解网络结构。最后，证明在极限情况下，鲁棒性泛函可以自然地映射到有效的自旋哈密顿量。 ###### PACS: 89.20.Hh, 89.65.-s, 05.65.+b, 89.75.-k ## I 引言 信息安全通常与加密[aumasson2017serious]联系在一起，但另一种基本策略是将信息拆分并分发给不同的代理。这一思想在秘密共享中得以形式化，其中秘密被分成 N 个份额，只有当指定子集（或至少 m 个份额）同时可用时才能重构。然而，自 Shamir 的开创性工作以来，其实际部署的一个主要障碍是，常规的 m 样本重构策略需要从单点进行协调——一旦该协调节点被入侵，整个秘密就会暴露。此外，对已部署的秘密共享系统的分析往往要么假设独立的节点故障（忽略网络拓扑），要么假设完全静态的拓扑（忽略节点会由于网络退化（例如节点故障或链路中断）而丢失可用性的可能性）。本研究旨在通过提出一个形式化框架来弥补这一差距，该框架将分布式秘密放置问题视为在通用网络上进行鲁棒性优化。 ## II 模型 ## III 一个测度 ## IV 生存性的精确表示 ## V 从生存性到谱函数 ## VI 数值结果 ## VII 结论与展望 ## 附录 A 符号表 ## 附录 B 在受限参与者条件下的一般框架 ## 附录 C 从例子看结果的推导 ## 附录 D 从谱到图中黑塞矩阵的非对角元 ## 附录 E 生存性的近似和 Bonferroni 边界 对于生存性，完全精确的级数展开式 (18) 包含了所有可能的由 MICS 构成的并集。由于项数增长极快，必须进行截断。第一个截断是忽略包含超过 M 个连通分量的并集。设 0≤S−SM≤∑m>MNmp ̄m, (45) 其中 Nm 是大小恰好为 m 的连通覆盖（即顶点数）的并集数量。对于平均度为 z 的局部树状图，粗略估计 Nm≲|Γ|zm−1 给出 S−SM≲|Γ|p ̄(zp ̄)M1−zp ̄,zp ̄<1. (46) 因此，当较大的连通覆盖的生存概率足够低时，截断是可控的。 第二个误差来源来自组合局部重构事件。设 Ev(R) 为以 v 为中心、半径为 R 的球内包含至少一个存活的连通覆盖的事件，并设 Pv(R)=P(Ev(R))。最简单的局部近似为 SR1=1−∏v(1−Pv(R)). (47) 这视局部事件为独立事件。对于第二种生存性近似，以下性质成立：半局部近似并非不加区分地丢弃所有非局部信息。它精确地考虑了完全包含在至少一个半径为 R 的邻域内的每个极小连通信息携带子图。为精确表述，设 BR(v)={u∈V(Γ):dΓ(u,v)≤R} (48) 为顶点 v 的半径为 R 的邻域，并设 V(Γ~′) 表示 MICS Γ~′ 的顶点集。定义 ρ(Γ~′)=minv∈V(Γ)maxu∈V(Γ~′)dΓ(u,v). (49) 因此 ρ(Γ~′) 是包含 Γ~′ 的最小图球的半径。半局部近似精确包含那些满足 ρ(Γ~′)≤R (50) 的极小子图。 因此，唯一可能贡献误差的子图是其空间范围大于近似中使用的邻域的那些子图。因此， 0≤Strue−SR2≤∑Γ~′∈MRp ̄ν(Γ~′),ν(Γ~′)=|V(Γ~′)|. (51) 等价地， 0≤Strue−SR2≤∑Γ~′∈G~ρ(Γ~′)>Rp ̄ν(Γ~′). (52) 特别地，如果所有全局极小连通信息携带子图都包含在某个半径为 R 的邻域内，则 SR2=Strue. (53) 对于可入侵性，如果包含所有符号子集，则 H ̄=1−H 的表达式是精确的： H ̄=∑∅≠T⊆X(−1)|T|+1q ̄cT,cT=#{v:χ(v)∩T≠∅}. (54) 如果这一包容-排除求和截断到 K 阶，Bonferroni 边界给出严格的误差估计。记 BK=∑1≤|T|≤K(−1)|T|+1q ̄cT, (55) 则 B2m≤H ̄≤B2m−1. (56) 因此，如果使用中点 H ̄2mmid=(B2m+B2m−1)/2，则 |H ̄−H ̄2mmid|≤B2m−1−B2m2. (57) 值得注意的是，出于实用目的，SR2 也可被截断，其截断误差可通过 Bonferroni 边界分析。结合上述估计，近似鲁棒性泛函 FR=αSR+(1−α)H ̄R (58) 的误差可按如下方式粗略界定： |F−FR|≤αεcover+(1−α)εhack, (59) 其中 εcover 由式 (45) 估计，εhack 由运行性展开截断时的 Bonferroni 间隙估计。 ## 附录 F 半局部消息传递优化 鲁棒性泛函的精确优化是困难的，因为生存性项依赖于所有极小信息携带子图及其重叠。为此，我们采用半局部 max-sum 过程作为启发式优化方法。该算法的目标不是在优化过程中评估精确的全局泛函，而是根据局部信息生成良好的候选放置方案。 设 Γ=(V,E) 且 X={X1,…,XNsym} 为符号集。节点 v 的状态是一个非空二元向量 χv∈Ωv⊆{0,1}Nsym∖{0}, (60) 其中 χv,a=1 表示 v 存储符号 Xa。在数值实现中，Ωv 被限制为每个节点最多包含 M 个符号的状态。叶子节点进一步限制为单元素状态，因为允许它们存储多个符号会极大增加局部状态空间，而不会产生许多独立的重构路径。 对于每个节点 c，我们定义一个局部因子，其作用域为 Bc={c}∪Ncsel, (61) 其中 Ncsel 是选定的邻域子集。Bc 的大小被设限，以保持局部赋值数量可控。对于每个赋值 χBc，枚举所有包含所有符号且具有此性质的最小连通子集 C⊆Bc。大小为 |C| 的簇以概率 p ̄|C| 存活，其中 p ̄=1−p。我们为其分配附加权重 w(C)=−log(1−p ̄|C|)。 (62) 如果同一簇在多个因子作用域中可见，其权重除以可见性重数 m(C)。 因此局部生存性得分为 Wc(χBc)=∑C∈Cc(χBc)w(C)m(C), (63) 其中 Cc(χBc) 是从因子 c 可见的局部极小信息携带簇的集合。 竞争性局部项是被入侵节点在 Bc 内包含所有符号的概率。通过包容-排除计算： Hc(χBc)=∑A⊆X(−1)|A|(1−q)nc(A), (64) 其中 nc(A) 是 Bc 中携带至少一个来自 A 的符号的节点数，且 nc(∅)=0。 max-sum 中使用的局部因子为 ψc(χBc)=αWc(χBc)+(1−α)(1−Hc(χBc)). (65) 消息从因子发送到变量。用 mc→v(t)(χv) 表示从因子 c 到节点 v 的消息，更新公式为 m^c→v(t+1)(χv)=maxχBc∖v[ψc(χBc)+∑u∈Bc∖vd:u∈Bdd≠cmd→u(t)(χu)]. (66) 通过减去均值对消息进行归一化，并按下式进行阻尼： mc→v(t+1)=λmc→v(t)+(1−λ)C^c→v(t+1), (67) 其中 0≤λ≤1 是阻尼参数，常数 Cc→v(t+1) 选取为使 ∑χv∈Ωvmc→v(t+1)(χv)=0. (68) 等价地，Cc→v(t+1) 是阻尼消息在 Ωv 中所有允许状态上的平均值。阻尼减少了环路 max-sum 迭代的振荡，而归一化固定了消息的任意可加性量纲。 收敛后，通过最大化输入消息之和来解码每个节点的状态。然后全局评估所得放置方案。收集邻域中所有局部极小簇，去除重复项，并丢弃包含更小完全信息簇的簇。如果 CMP 是结果集，则近似生存性为 SMP=1−∏C∈CMP(1−p ̄|C|). (69) 该表达式对不相交簇是精确的，否则忽略高阶重叠修正。可入侵性全局评估为 HMP=∑A⊆X(−1)|A|(1−q)|U(A)|, (70) 其中 U(A) 是携带至少一个来自 A⊆X 的符号的节点集。最终的近似目标为 FMP=αSMP+(1−α)(1−HMP). (71) 主要计算瓶颈是因子表的构建。如果 sv=|Ωv|，因子 c 检查的赋值数为 Ac=∏v∈Bcsv. (72) 因此该方法随因子大小和每个节点允许的符号数呈指数增长。为此，作用域 Bc 被设限，状态空间 Ωv 被剪枝。粗略成本估计为 TMP=O(∑c∈VAc2|Bc|+I∑c∈VAc|Bc|), (73) 其中第一项对应因子构建，第二项对应 I 次 max-sum 迭代。因此，该方法适用于中等规模网络和小型符号集，但应视为启发式半局部优化器，而非可扩展的精确算法。 在图 7 中，计算了一个 N=50 的 ER 网络，z=3，4 个符号，针对不同的 α、p 和 q 值。参见图注。 图 7: F≡max(F(α∈{0.2,0.4,0.6,0.8},p,q)) 的图