超宽字RAM上的部分和与基于卡片的安全多方计算

### 超宽字 RAM 上的部分和与基于卡片的安全多方计算 #### 1. 超宽字 RAM 相关研究 在超宽字 RAM（UWRAM）的研究中，通过对 Fenwick 树进行“自顶向下”遍历可以在 $O(\log n)$ 时间内完成某些操作，但相关技术似乎无法加速 UWRAM 上的解决方案。目前，UWRAM 上选择操作的复杂度仍是一个有待研究的开放问题。 同时，UWRAM 和 RAMBO 计算模型之间的确切关系也尚未明确。虽然有研究展示了如何以较小的空间开销模拟 RAMBO 算法，但直接设计 UWRAM 算法可能会产生更优的结果。人们仍在探索这两种模型之间的精确关系，以及是否能得到更强的模拟结果。 #### 2. 基于卡片的安全多方计算 ##### 2.1 研究背景与动机 安全多方计算是密码学中一个活跃的研究领域，而基于卡片的密码学是其中的一个分支。它始于 1989 年 den Boer 引入的“五张卡片技巧”，用于计算逻辑与函数。此后，人们开发了许多计算各种函数的协议。 例如，在一次两候选人选举中，一群朋友希望只有在所有人都支持同一候选人时才讨论选举，但每个人都想隐藏自己的偏好，直到确定大家的选择一致。这就引出了一个安全多方计算问题：如何在不泄露任何额外信息的情况下，判断所有人的偏好是否一致。 ##### 2.2 相关工作 - **五张卡片技巧**：用于计算两个玩家比特的逻辑与函数。使用三张相同的 ♣ 卡片和两张相同的 ♥ 卡片，通过交换卡片位置和随机切牌操作，根据卡片的循环序列判断逻辑与的结果。 - **其他协议**：后续人们开发了更多计算与函数的协议，旨在减少所需卡片数量或改进协议的其他属性，如输出格式、运行时间和洗牌类型等。此外，还开发了计算异或函数、复制承诺、多数函数和加法等协议。Nishida 等人证明了任何 $n$ 变量布尔函数可以用 $2n + 6$ 张卡片计算，对称函数可以用 $2n + 2$ 张卡片计算。 | 函数类型 | 所需卡片数量 | | ---- | ---- | | 任意 $n$ 变量布尔函数 | $2n + 6$ | | 对称函数 | $2n + 2$ | ##### 2.3 六张卡片技巧 对于三变量的相等函数，Shinagawa 和 Mizuki 开发了“六张卡片技巧”。玩家将三个比特的承诺面朝下放在桌子上，然后进行特定的卡片排列，得到八种可能的序列。通过循环旋转，只有两种可能的序列，其中一种对应所有比特相等的情况。通过随机切牌和翻牌操作，可以判断相等函数的值。 然而，这种技巧严重依赖于 $n = 3$ 的对称性，对于一般的 $n$，可能不存在使用 $2n$ 张卡片的等效协议。例如，在 $n = 4$ 的情况下，使用一张随机切牌的八张卡片协议不存在。 ```mermaid graph LR A[初始卡片序列] --> B[进行 (2 4 6) 排列] B --> C{循环旋转后序列} C -->|情况 1| D[判断相等函数值为 1] C -->|情况 2| E[判断相等函数值为 0] ``` #### 3. 基本操作 在基于卡片的协议中，有几个基本操作是非常重要的： - **随机切牌**：将卡片序列打乱成均匀随机的循环排列。在现实中，可以通过印度切牌法实现。 - **随机 $k$ 段切牌**：将 $km$ 张卡片分成 $k$ 个块，然后将这些块打乱成均匀随机的循环排列。可以通过将每个块放入信封，对信封堆进行随机切牌，然后取出卡片来实现。 - **与随机比特异或**：通过对卡片序列进行随机 2 段切牌，可以将每个输入比特与同一个随机比特进行异或操作。 - **在 $\mathbb{Z}/k\mathbb{Z}$ 中加法**：对于 $k \geq 3$，使用 ♣ 方案和 ♥ 方案编码整数。通过一系列操作，将两个整数相加并编码在 ♥ 方案中，而无需额外的卡片。操作步骤如下： 1. 将两个整数编码的卡片按特定顺序排列成新序列 $Z$。 2. 对 $Z$ 进行随机 $k$ 段切牌。 3. 将切牌后的卡片放回原序列，得到编码 $a - r$ 和 $b + r$ 的序列。 4. 翻开编码 $b + r$ 的卡片，得到 $s = b + r$。 5. 将编码 $a - r$ 的卡片向右移动 $s$ 个位置，得到编码 $a + b$ 的序列。 #### 4. 主要协议 要计算 $n$ 变量的相等函数，我们可以先计算输入比特的总和。协议的直觉是，对于 $k = 2, 3, \cdots, n$，归纳地计算 $\sum_{i = 1}^{k} a_i$ 在 $\mathbb{Z}/(k + 1)\mathbb{Z}$ 中的值。由于这个和最多为 $k$，其在 $\mathbb{Z}/(k + 1)\mathbb{Z}$ 中的值与实际值相同。 通过这些操作和协议，我们可以开发出一种使用 $2n$ 张卡片安全计算 $n$ 变量相等函数的协议，并且相同的技术可以应用于计算任何双对称函数和对称函数。 ### 超宽字 RAM 上的部分和与基于卡片的安全多方计算 #### 5. 计算 $n$ 变量相等函数的详细步骤 为了更清晰地展示如何使用 $2n$ 张卡片安全计算 $n$ 变量相等函数，下面给出详细的步骤： 1. **初始化**：每个玩家将自己的比特 $a_i$ 用承诺（$0$ 用 ♣♥ 编码，$1$ 用 ♥♣ 编码）表示，并将这些承诺面朝下依次排列在桌子上，形成一个长度为 $2n$ 的卡片序列。 2. **归纳计算部分和**： - 对于 $k = 2$，使用前面提到的在 $\mathbb{Z}/(k + 1)\mathbb{Z}$ 中加法的方法，计算 $\sum_{i = 1}^{2} a_i$ 在 $\mathbb{Z}/3\mathbb{Z}$ 中的值。 - 对于 $k = 3$，同样使用该加法方法，结合之前计算得到的 $\sum_{i = 1}^{2} a_i$ 的结果，计算 $\sum_{i = 1}^{3} a_i$ 在 $\mathbb{Z}/4\mathbb{Z}$ 中的值。 - 以此类推，直到 $k = n$，计算出 $\sum_{i = 1}^{n} a_i$ 在 $\mathbb{Z}/(n + 1)\mathbb{Z}$ 中的值。 3. **判断相等函数值**：由于相等函数 $E(a_1, \cdots, a_n)$ 的值只取决于 $\sum_{i = 1}^{n} a_i$，如果 $\sum_{i = 1}^{n} a_i$ 等于 $0$ 或 $n$，则 $E(a_1, \cdots, a_n) = 1$；否则，$E(a_1, \cdots, a_n) = 0$。 4. **随机切牌与结果揭示**：为了保证安全性，在揭示结果之前，对卡片序列进行随机切牌操作，将其打乱成均匀随机的循环排列。然后将所有卡片面朝上，根据循环排列的结果判断相等函数的值。 ```mermaid graph LR A[初始化卡片序列] --> B[归纳计算部分和] B --> C[判断相等函数值] C --> D[随机切牌] D --> E[揭示结果] ``` #### 6. 应用于双对称函数和对称函数 除了计算 $n$ 变量相等函数，相同的技术还可以应用于计算双对称函数和对称函数： - **双对称函数**：对于任何双对称函数 $f: \{0, 1\}^n \to \mathbb{Z}$，可以使用 $2n$ 张卡片进行计算。具体步骤与计算 $n$ 变量相等函数类似，先计算输入比特的总和，然后根据总和与双对称函数的定义来确定函数值。 - **对称函数**：对于任何对称函数 $f: \{0, 1\}^n \to \mathbb{Z}$，需要使用 $2n + 2$ 张卡片。在计算输入比特总和的基础上，可能需要额外的卡片来处理一些特殊情况或满足对称函数的要求。 | 函数类型 | 所需卡片数量 | 计算方法 | | ---- | ---- | ---- | | $n$ 变量相等函数 | $2n$ | 计算总和并判断 | | 双对称函数 | $2n$ | 计算总和并根据定义确定值 | | 对称函数 | $2n + 2$ | 计算总和并处理特殊情况 | #### 7. 安全性分析 基于卡片的协议在安全多方计算中具有重要的优势，主要体现在以下几个方面： - **信息隐藏**：通过随机切牌和洗牌操作，能够有效地隐藏每张卡片的初始位置和玩家的输入信息。即使在揭示结果时，也只能得到函数值，而不会泄露任何玩家的具体输入。 - **物理安全性**：使用实际的卡片进行计算，避免了计算机系统可能存在的安全漏洞，如黑客攻击、数据泄露等。 - **可验证性**：协议的操作步骤简单明了，易于验证其正确性。任何参与者都可以通过检查卡片的排列和操作过程来确认计算结果的准确性。 #### 8. 实际应用场景 基于卡片的安全多方计算在现实生活中有许多潜在的应用场景，例如： - **选举投票**：在选举过程中，选民可以使用卡片协议来安全地判断是否所有选民都支持同一候选人，而无需透露自己的投票意向。 - **商业合作**：在商业谈判中，各方可以使用卡片协议来判断是否对某个合作方案达成一致，保护各方的商业机密。 - **隐私计算**：在需要进行隐私保护的计算任务中，如医疗数据统计、金融数据分析等，卡片协议可以提供一种安全的计算方式。 #### 9. 总结 通过对超宽字 RAM 上的部分和计算以及基于卡片的安全多方计算的研究，我们发现了一些有趣的结果和方法。在超宽字 RAM 方面，虽然相关技术在某些问题上的加速效果尚不明确，但仍为进一步的研究提供了方向。在基于卡片的安全多方计算方面，我们提出了一种使用 $2n$ 张卡片安全计算 $n$ 变量相等函数的协议，并将其扩展到双对称函数和对称函数的计算中。这些协议具有信息隐藏、物理安全性和可验证性等优点，在实际应用中具有广阔的前景。未来的研究可以进一步探索如何优化这些协议，减少所需的卡片数量和操作步骤，提高计算效率和安全性。