基于卡片的多方计算：双辅助卡多输入与协议洗牌次数的上界

### 基于卡片的多方计算：双辅助卡多输入与协议洗牌次数的上界 在当今的信息时代，安全计算变得越来越重要。安全计算允许持有私有输入的参与者在不泄露过多输入值的情况下评估预定函数。而基于卡片的密码学，作为一种独特的安全计算方法，使用物理卡片组来实现这一目标。本文将深入探讨双辅助卡多输入与协议中洗牌次数的上界问题。 #### 1. 引言 安全计算能让持有私有输入的玩家在不泄露必要信息的前提下评估预定函数。基于卡片的密码学则是利用物理卡片组来实现安全计算的方法。通常使用两种卡片，背面无差别表示为“?”，正面为“♣”或“♥”。卡片按特定方式排列来表示布尔值，“♣♥ = 0”，“♥♣ = 1”。当两张面朝下的卡片按此编码规则代表一个比特“𝑥∈{0, 1}”时，这两张卡片被称为对“𝑥”的承诺，记为“? ? [𝑥]”。 ##### 1.1 Mizuki–Sone与协议 目前已知最实用的承诺格式双输入与协议是Mizuki和Sone在2009年提出的MS - AND协议，其步骤如下： 1. 放置两个对“𝑥, 𝑦∈{0, 1}”的输入承诺以及两张辅助卡，将中间两张卡片面朝下放置：“? ? [𝑥] ♣♥ ? ? [𝑦] → ? ? [𝑥] ? ? [0] ? ? [𝑦]”。 2. 重新排列序列。 3. 对六张卡片序列应用随机二分切割（RBC），即把卡片序列分成两半并随机交换左右两侧：“[? ? ? | ? ? ?] → ? ? ? ? ? ?”。 4. 再次重新排列序列。 5. 从左侧翻转两张卡片，根据两张显示卡片的顺序，得到对“𝑥∧𝑦”的承诺：“♣♥? ? [𝑥∧𝑦] ? ?” 或 “♥♣? ? ? ? [𝑥∧𝑦]”。 协议结束后，步骤5中翻转的两张卡片可作为其他协议运行中的辅助卡，称为自由卡。另外两张面朝下且不是对“𝑥∧𝑦”承诺的卡片称为垃圾承诺，通过对组成垃圾承诺的两张卡片进行洗牌并翻转，可将其转换为两张自由卡。 ##### 1.2 承诺格式多输入与协议 我们的目标是构建承诺格式多输入与协议，即给定“𝑛”个输入承诺“? ? [𝑥1] ? ? [𝑥2] · · · ? ? [𝑥𝑛]”，产生对“𝑥1 ∧𝑥2 ∧· · · ∧𝑥𝑛”的承诺。通过重复应用MS - AND协议“𝑛 - 1”次，可以构建一个承诺格式的“𝑛”输入与协议，所需辅助卡数量为2，所需洗牌次数（即随机二分切割次数）为“𝑛 - 1”。 ##### 1.3 本文贡献 在有两张辅助卡的条件下，承诺格式“𝑛”输入与协议所需洗牌次数的一个明显上界是“𝑛 - 1”。而Shinagawa和Nuida在2020年提出的“批处理”技术可以减少洗牌次数。本文将批处理技术应用于MS - AND协议，构建洗牌次数更少的双辅助卡“𝑛”输入与协议。具体来说，首先定义了通过将批处理技术应用于MS - AND协议得到的双辅助卡“𝑛”输入与协议类，然后展示了在“2 ≤ 𝑛 ≤ 500”的情况下，该类协议中所需洗牌次数最少的“𝑛”输入与协议。结果表明，所提出的通用协议在许多“𝑛”的情况下，在洗牌次数方面是最优的。对于“2 ≤ 𝑛 ≤ 500”中通用协议不是最优的“𝑛”，也找到了最优协议。 ##### 1.4 相关工作 承诺格式双输入与协议的历史可以追溯到1993年，此后发明了一些协议，2009年出现了MS - AND协议。随后，使用复杂洗牌的四卡和五卡协议也得到了发展。对于承诺格式多输入与协议，最近提出了仅使用一两次洗牌的协议，但需要大量辅助卡。此外，还有一些专门的协议也被人们所知。基于卡片的密码学研究领域近年来发展迅速，涵盖了物理零知识证明协议、私有模型安全计算、对称函数评估等多个活跃主题。 ##### 1.5 本文组织 后续内容安排如下：在第2节中，介绍批处理技术以及所需的“堆乱序洗牌”。在第3节中，展示如何将批处理技术应用于多个MS - AND协议。在第4节中，定义通过应用批处理技术得到的协议类，并将寻找洗牌次数更少的协议问题转化为“MSbatching移动序列”问题。在第5节中提出一个简单的通用协议。在第6节中，通过动态规划算法分析“MSbatching移动序列”问题，并展示在“2 ≤ 𝑛 ≤ 500”的情况下，在所有协议类中洗牌次数最少的最优“𝑛”输入与协议。最后，在第7节中给出结论。 #### 2. 预备知识 ##### 2.1 堆乱序洗牌 堆乱序洗牌是一种洗牌操作，它将卡片序列分成多个相同大小的堆，然后随机均匀地重新排列这些堆的顺序，同时保持每个堆内卡片的顺序不变。例如，对由三堆组成的九张卡片序列应用堆乱序洗牌，会以1/6的概率得到以下六种序列之一： ```plaintext [1? 2? 3? | 4? 5? 6? | 7? 8? 9?] → { 1? 2? 3? 4? 5? 6? 7? 8? 9?, 1? 2? 3? 7? 8? 9? 4? 5? 6?, 4? 5? 6? 1? 2? 3? 7? 8? 9?, 4? 5? 6? 7? 8? 9? 1? 2? 3?, 7? 8? 9? 1? 2? 3? 4? 5? 6?, 7? 8? 9? 4? 5? 6? 1? 2? 3? } ``` 堆乱序洗牌可以通过将每个堆放入信封并随机搅拌信封来轻松实现。MS - AND协议中出现的随机二分切割可以看作是对两堆（每堆三张卡片）的堆乱序洗牌。 ##### 2.2 批处理技术 批处理技术将多个可以并行执行的堆乱序洗牌组合成一个单一的堆乱序洗牌，从而减少洗牌次数。简单来说，在为每个堆乱序洗牌的堆添加带有辅助卡的“标识符”后，一起执行一次堆乱序洗牌，然后打开标识符，将每个堆放回其原始堆乱序洗牌的位置。 例如，假设要并行应用MS - AND协议中出现的两个随机二分切割（RBC），并使用批处理技术。具体步骤如下： 1. 为了识别两个RBC，使用“♣”和“♥”。在每个堆的头部放置一张用于识别的辅助卡：“♣? ? ? ♣? ? ? ♥? ? ? ♥? ? ?”。 2. 翻转标识符卡片，并对四堆应用堆乱序洗牌：“[? ? ? ? | ? ? ? ? | ? ? ? ? | ? ? ? ?] → ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?”。 3. 将标识符卡片面朝上。假设得到以下卡片序列：“♣? ? ? ♥? ? ? ♥? ? ? ♣? ? ?”。 4. 对堆进行排序，使头部为“♣”的堆在左侧，头部为“♥”的堆在右侧，就像步骤1中插入标识符卡片时一样。在上述示例中，将第四堆移到第二堆前面：“♣? ? ? ♥? ? ? ♥?