安全计算中的可识别中止与秘密共享技术解析

### 安全计算中的可识别中止与秘密共享技术解析 #### 1. 基本定义与概念 - **多方函数的安全计算**：设 \(f : (\{0, 1\}^*)^n \to (\{0, 1\}^*)^n\) 为一个 \(n\) 方函数。若对于每个现实世界的敌手 \(A\)，都存在一个模拟器 \(S\)，其运行时间是 \(A\) 运行时间的多项式，使得对于大小至多为 \(t\) 的每个 \(C \subseteq [n]\)，有 \(\{REAL_{\Pi,C,A}(aux)(x, \lambda)\}_{x\in(\{0,1\}^*)^n,\lambda\in\mathbb{N}} \equiv_s \{IDEAL_{f,C,S}(aux)(x, \lambda)\}_{x\in(\{0,1\}^*)^n,\lambda\in\mathbb{N}}\)，则协议 \(\Pi\) 能 \(t\) - 安全地计算函数 \(f\)。 - **秘密共享方案**： - 普通秘密共享方案：消息空间为 \(\{0, 1\}^*\) 的秘密共享方案由概率多项式时间算法 \(Share\) 和确定性多项式时间算法 \(LRec\) 组成。 \(Share(msg) \to (s_1, \ldots, s_n)\) 接收消息 \(msg \in \{0, 1\}^*\) 并输出份额 \(s_1, \ldots, s_n\)； \(LRec(s_i, \{s_j\}_{j\in S}) \to (msg, L)\) 接收份额 \(s_i\) 和份额子集 \(\{s_j\}_{j\in S}\)（其中 \(i \in S \subset [n]\)），输出重构消息 \(\{0, 1\}^* \cup \{\perp\}\) 和指控集合 \(L \subset [n]\)。 - 带公共和私有份额的秘密共享方案：由概率多项式时间算法 \(Share\) 和确定性多项式时间算法 \(Rec\)、 \(LRec\) 组成。 \(Share(msg) \to (s_{pub}^1, \ldots, s_{pub}^n, s_{priv}^1, \ldots, s_{priv}^n)\) 接收消息 \(msg \in \{0, 1\}^*\) 并输出公共份额 \(s_{pub}^1, \ldots, s_{pub}^n\) 和私有份额 \(s_{priv}^1, \ldots, s_{priv}^n\)； \(Rec(\{s_{pub}^i\}_{i\in S}) \to msg/\perp\) 接收公共份额子集 \(\{s_{pub}^i\}_{i\in S}\)（其中 \(S \subset [n]\)）并输出值 \(\{0, 1\}^* \cup \{\perp\}\)； \(LRec(s_{priv}^i, \{s_{pub}^j\}_{j\in S}) \to (msg, L)\) 接收私有份额 \(s_{priv}^i\) 和公共份额子集 \(\{s_{pub}^j\}_{j\in S}\)（其中 \(S \subset [n]\)），输出重构消息 \(\{0, 1\}^* \cup \{\perp\}\) 和指控列表 \(L \subset [n]\)。 #### 2. 访问结构定义 - **阈值访问结构**：对于任意固定阈值 \(t \in [n]\)， \(t\) - 阈值访问结构定义为 \(A_{n,t} = \{S \subset [n] | |S| \geq t\}\)。 - **带观察者的阈值访问结构**：对于任意固定阈值 \(t \in [n]\) 和集合 \(O \subset \{1, \ldots, n\}\)，带观察者 \(O\) 的 \(t\) - 阈值访问结构定义为 \(A_O^{n,t} = \{S \subset \{1, \ldots, n\} | |S \setminus O| \geq t\}\)。 #### 3. 秘密共享方案的性质 - **正确性**：带公共和私有份额的秘密共享方案 \((Share, Rec, LRec)\) 对于访问结构 \(A\) 是正确的，如果对于任意 \(S \in A\)，任意 \(i \in S\)，任意消息 \(msg \in \{0, 1\}^*\)，存在可忽略函数 \(negl(\cdot)\) 使得： - \(Pr[((s_{pub}^1, \ldots, s_{pub}^n, s_{priv}^1, \ldots, s_{priv}^n) \leftarrow Share(msg), (msg, \perp) \leftarrow LRec(s_{priv}^i, \{s_{pub}^j\}_{j\in S}) : msg = msg] = 1 - negl(\lambda)\) - \(Pr[((s_{pub}^1, \ldots, s_{pub}^n, s_{priv}^1, \ldots, s_{priv}^n) \leftarrow Share(msg), msg \leftarrow Rec(\{s_{pub}^j\}_{j\in S}) : msg = msg] = 1 - negl(\lambda)\) 其中概率是对 \(Share\) 算法的随机硬币取的。 - **隐私性**：秘密共享方案 \((Share, LRec)\) 对于访问结构 \(A\) 是私有的，如果对于任意无界敌手 \(A\)，任意 \(S \notin A\)，任意两个长度相等的消息 \(msg, msg' \in \{0, 1\}^*\)，有 \(|Pr[A(\{(s_{pub}^i, s_{priv}^i)\}_{i\in S}) = 1 | (s_{pub}^1, \ldots, s_{pub}^n, s_{priv}^1, \ldots, s_{priv}^n) \leftarrow Share(msg)] - Pr[A(\{(s_{pub}^i, s_{priv}^i)\}_{i\in S}) = 1 | (s_{pub}^1, \ldots, s_{pub}^n, s