Secret sharing with additive access structures from correlated random variables

技术摘要：基于相关随机变量的加性访问结构秘密共享

问题陈述
本文研究了在动态环境下进行秘密共享的问题，其中授权参与者的集合（访问结构）会随时间演变。传统的秘密共享模型通常假设访问结构是固定的；如果结构发生变化，则必须重新分配份额，这会导致效率低下。虽然“演进访问结构”（Evolving Access Structure, EAS）模型允许单调增长，但它假设参与者是顺序加入并通过私密信道接收份额。

本研究引入了**加性访问结构（Additive Access Structure, AAS）**模型，该模型在两个基本方面与 EAS 不同：

1. 同步初始化： 所有参与者最初都已存在。
2. 相关随机性源： 份额是从一个相关的随机源（例如无线网络中的信道增益测量值）同时生成的，而不是通过私密信道进行分发。
3. 公共通信： 委托人（Dealer）通过公共、无噪声且经过身份验证的信道与参与者进行通信。委托人仅在时间步发生时才获知访问结构的变化（新的授权组），并且必须迭代地调整其秘密共享策略。

目标是确定一种秘密共享策略，使授权组能够以高可靠性恢复秘密，同时确保未经授权的组获取的信息量微乎其微，同时最大化秘密速率（即共享的秘密大小与源观测值数量的比值）。

方法论
作者提出了一种基于**随机分箱（Random Binning）**并将其应用于动态环境的秘密共享策略。该方法的核心包括：

• 量化随机分箱： 委托人观测来自相关源 $(Y, X_L)$ 的序列 $Y^n$。对于每个时间步 $t$，委托人和参与者利用预先确定的随机分箱函数（$g_i$ 和 $h_j$）将源序列映射到索引。
• 迭代编码： 在每个时间步 $t$，委托人确定要包含在公共消息中的分箱索引数量 ($k_t$) 以及被指定为秘密的索引数量 ($\sigma_t$)。这些计数是基于当前的授权集 $A_t$ 和未授权集 $U_t$ 进行选择的。
• 先验策略规范： 该证明的一个新颖之处在于引入了量化的分箱数量。这使得构建一种完全由先验指定的单一秘密共享策略成为可能。至关重要的是，该策略并不依赖于对未来时间步 AAS 如何演变的知识；委托人只需知道当前访问结构即可确定该特定步的消息和秘密。
• 解码： 授权参与者利用其局部观测值 ($X^n_A$)、累积的公共消息以及分箱函数来识别符合典型性约束和接收到的分箱索引的唯一源序列。

主要贡献与结果
本文建立了以下理论结果：

1. 固定结构速率的可达性： 作者证明，在 AAS 模型中，存在一种策略使得在任何时间步 $t$ 的可达速率与所有其他时间步的访问结构无关。具体而言，可达速率 $R_t$ 与已知于固定结构模型的最佳可达速率相匹配：
   $$R_t = \min_{U \in U_t} H(Y | X_U) - \max_{A \in A_t} H(Y | X_A)$$
   这一结果意味着，动态性质本身并不会像在静态场景那样降低秘密速率。

2. 阈值访问结构的容量： 本文证明，当给定时间步的访问结构构成阈值访问结构（即任何规模 $\ge f_1(t)$ 的组均为授权组，任何规模 $\le f_2(t)$ 的组均为未授权组）时，所提出的策略是达到容量的。在委托人与参与者共享独立私钥的特定情况下，容量显示为：
   $$R_t = H(X)(f_1(t) - f_2(t))$$

3. 全知性 vs. 因果性： 一个重要的发现是，对于阈值 AAS 情况，一个全知型委托人（预知整个未来访问结构序列）相对于因果型委托人（仅知道当前结构）在可达秘密速率方面并无优势。

意义与主张
本文声称将依赖相关随机性的秘密共享模型从固定加性访问结构推广到了动态加性访问结构。其主要意义在于证明了动态适应性并不会以牺牲秘密速率的效率为代价。作者展示了可以在不需要预知系统演变的情况下，实现与最佳静态策略相同的性能界限。

研究强调，令人“惊讶”的结果是，在时间步 $t$ 的可达速率与访问结构的历史或未来无关。虽然论文对于一般 AAS 情况提供了一个非构造性的存在性证明（依赖于概率法来证明合适的分箱函数之存在性），但它也明确指出，为一般 AAS 提供构造性可达性证明仍然是一个开放性问题，这将其与现有的针对固定结构的构造性证明区分开来。

论文总结道，对于基于阈值的动态结构，容量得到了充分表征，且缺乏对未来访问结构变化的预见性并不会损害系统的性能。