Shuffle and Compaction

文章主题：总结并记录目前常用的安全洗牌协议(Secure Shuffle)与Secure Compaction协议，思想、实现、复杂度分析等。

Shuffle定义：

• 给定输入\(\vec{v}\)，洗牌协议输出一个\(\pi(\vec{v})\)，其中\(\pi\)是一个随机的置乱。

compaction与shuffle很相似，也是给定输入\(\vec{v}\)以及\(\vec{t}\)，根据\(\vec{t}\)来重新安排\(\vec{v}\)中数据条目的顺序。

• 给定\(\vec{v}\)和\(\vec{t}\)，其中\(\vec{t}\)是一个0-1向量。当\(\vec{t}[i]=1\)时，说明\(\vec{v}[i]\)被选中，0则是没有被选中。Compaction协议会将所有被选中的元素筛选出来。

可以说，compaction(指定一个顺序)对元素顺序安排的要求比shuffle(完全随机)更强一些，但比sort(数之间内在的逻辑顺序)更弱一些，即

所以，compaction和sort可以在shuffle的基础上进行构建。

和Sort类似，Compaction中也有稳定性的定义，即在进行Compaction或者Sort后，元素之间的相对顺序不变。
满足稳定性的Compaction与Sort被称为Stable Compaction，Stable Sort。

Stable定义：

• Stable Compaction：被选中的元素之间的相对顺序不变。
• Stable Sort：排序后，若两个元素相等，那么二者排序后的顺序和排序前二者的相对顺序保持一致。

TwoPartyShuffle and StableCompaction

source：secure merge with \(n\log\log n\)

\(\mathsf{TwoPartyShuffle}\):

• 输入：Alice和Bob都持有向量\(v\)的秘密共享，分别记为\(\vec{v}^a\)和\(\vec{v}^b\)。
• 输出：\(\pi(\vec{v})\)的秘密共享，其中\(\pi\)是一个随机置乱。

协议简述：

• 思想：加法同态的重随机化配合local shuffle，可以让某一方对整个数据集进行shuffle。某一方shuffle后，另一方在其基础上再进行一次shuffle，即可得到两个人都无法知晓的shuffle结果。
• 第一步：Alice将自己的秘密共享加密后发送给Bob。
• 第二步：Bob将自己的秘密共享也进行加密，然后对两组密文进行同样的本地shuffle。
• 第三步：为了避免Alice认出自己的密文，Bob对所有密文以及秘密共享进行重随机化，也就是在Alice密文上加上一个随机数，在自己的密文上减去一个随机数。
• 第四步，Bob将两组密文都发送给Alice。Alice也同样对两组密文进行shuffle后，再进行重随机化，即在自己的密文上加上一个随机数的密文，在Bob的密文上减去一个随机的密文。最后将Bob的密文发还回去，这样就得到了结果。

协议思考：

• Q1：为什么需要两对密钥？
  • A1：因为不论Alice或者Bob，都不应该能解密对方的密文，否则整个过程就失去了隐私性。
• Q2：在半诚实条件下，有没有更简单的方法？
  • A2：没有。但在Secret-shared shuffle介绍了将shuffle规约为两次\(\mathsf{Permute + Share}\)的协议，利用Paillier实现。但其本质与这里的\(\mathsf{TwoPartyShuffle}\)是相同的。

复杂度分析：

• Notation：当\(\mathsf{PKE}\)具有固定的密文扩张率(Ciphertext expansion)时，我们用\(S_c\)代表一个密文的长度。用\(n\)记为向量的长度。我们用\(\mathsf{Enc}\)和\(\mathsf{ReRand}\)来分别表示进行PKE加密和重随机化的计算代价。
• 通信：第一步，第四步中Alice分别传送了自己的密文与Bob的密文，消耗\(2nS_c\)。第三步中，Bob传送二者的密文，消耗\(2nS_c\)，总计消耗\(4nS_c\)。注意到，这里是线性的复杂度，这是其他的shuffle协议很难达到的渐进复杂度。
• 计算：Alice和Bob都对自己的秘密共享进行了加密，以及重随机化所有密文，总计\(n \mathsf{Enc} + 2n \mathsf{ReRand}\)。观察到，\(\mathsf{TwoPartyShuffle}\)的计算复杂度也是线性的。
• 轮数：常数轮，两轮。

总结：

• 线性的渐进复杂度：无论是通信还是计算，\(\mathsf{TwoPartyShuffle}\)都是线性的。在理论上具有很好的结果。
• 实际应用：\(\mathsf{TwoPartyShuffle}\)在实际应用中面临两个主要的问题，即在通信上，密文扩张率是一个较大的常数。其次，同态计算的复杂度较高。

Discussion：让lattice-based FHE取代Paillier

• 好处：lattice-based FHE能够同时处理大批量密文，同时降低密文扩张率与同态计算的均摊开销。
• FHE一般只支持rotation，如何由rotation实现密文的本地shuffle？
  • 可能可以参考ThorPIR：Single Server PIR via Homomorphic Thorp Shuffles，但是不确定，目前只从其标题上看到相关关键字，猜测可能有关系。
• 当前的FHE实现中，支持的明文slots数量有限，但是shuffle处理的数据集体量可能很大。

Construct \(\mathsf{StableCompaction}\) from \(\mathsf{TwoPartyShuffle}\)：

• Solution idea：shuffle-then-reveal技巧。给定\(\vec{v}\)和\(\vec{t}\)，运行\(\pi(\vec{v}||\vec{t})=\pi(\vec{v})||\pi(\vec{t})\leftarrow\mathsf{TwoPartyShuffle}(\vec{v}||\vec{t})\)。揭示\(\pi(\vec{t})\)，注意到由于\(\pi(\vec{t})\)是shuffle后的结果，因此\(\pi(\vec{t})\)只会泄露有关\(\mathsf{sum}(\vec{t})\)的信息。揭示后，选择\(\pi(\vec{v})[\pi(\vec{t})==1]\)。注意到这样的方法不具备稳定性，\(\mathsf{StableCompaction}\)引入了稳定性技巧。
• Construction \(\mathsf{StableCompaction}\)：核心技巧是引入两个计数器\(c,d\)，其中\(c\)从0开始计数，而\(d\)从\(\mathsf{sum}(\vec{t})\)开始。生成一个额外的向量\(\vec{y}\)，遍历\(\vec{t}\)。如果\(\vec{t}[i]=1\)，执行\(\vec{y}[i]=c,c=c+1\)，否则执行\(\vec{y}[i]=d,d=d+1\)。这样shuffle后揭示\(\vec{y}\)，只要按\(\vec{y}\)的递增顺序排列\(\vec{x}\)，就能保证选中的条目都在最前面，且相对顺序不变，因此实现了稳定性。

复杂度分析：

• \(\mathsf{StableCompaction}\)的复杂度是\(\mathsf{TwoPartyShuffle}\)加上计算\(\vec{y}\)的复杂度。原文没有给出具体的分析。如果真的一个一个遍历，那导致的通信轮数就是\(n\)轮，这是肯定不可接受的，但是现在我也不太知道怎么简单高效实现这个步骤。

Round-Efficient Shuffle

source：Round-efficient Oblivious Database Manipulation

\(\textsf{Shuffle via Permutation Matrices}\):

• 思想：对于任意的洗牌\(\pi\)，总存在一个0-1矩阵\(M_{\pi}\)使得\(\pi(\vec{v}) = M_{\pi}\vec{v}\)。这个矩阵称为置换矩阵。因此，无论多复杂的洗牌，总是可以将其转化为矩阵-向量乘法。接下来我们考虑两方的例子。
• Alice随机生成一个\(\pi_1\)，并转化为对应的置换矩阵\(M_{\pi_1}\)，然后将置换矩阵共享给Bob。
• Bob同样产生一个置换矩阵\(M_{\pi_2}\)，对应\(\pi_2\)，共享给Alice。
• Alice与Bob共同运行乘法协议先计算\(\vec{u}=M_{\pi_1}\vec{v}\)，在计算\(\vec{x}=M_{\pi_2}\vec{u}\)。

复杂度分析：

• 通信：分享两个置换矩阵需要至少\(2n^2\)比特，考虑到0-1矩阵需要参与算数电路，需要假设字长为\(l\)比特，则这部分通信代价为\(2n^2l\)比特。接下来进行两次向量矩阵乘法，这两次乘法可以一步一步进行，也可以先算两个矩阵的乘积后再计算向量矩阵乘法。这个乘法即便用目前最先进的ABY 2.0来计算，也需要至少\(2n^2\)的通信量。
• 计算：不好衡量，尽管有工作认为在线阶段的计算在PPML中是个重要的瓶颈，并提出用GPU进行优化，但是在更一般的场景中，还是缺少概念，至少我不清楚怎么去衡量秘密共享的计算量。

\(\textsf{Shuffle via Sorting}\): 挺异想天开的想法，我觉得多少有点本末倒置了。

• 思想：假设生成的随机shuffle用一个向量\(\vec{\pi}=(\vec{\pi}[0],\dots,\vec{\pi}[n-1])\)表示，则可以对\((\vec{v},\vec{\pi})\)按照\(\vec{\pi}\)进行排序，排完后就可以得到\(\pi(\vec{v})\)。在这里，作者提到排序可以用排序网络(sorting network)来实现，这是后话了，后续讨论排序的时候应该会讨论这个概念。

复杂度分析：

• 洗牌的复杂度完全取决于排序的复杂度，包括通信与计算。一般来说，排序网络具有\(O(\log n)\)层，每层并行需要算一个switch。每个switch的复杂度大概是一个比较大小接上一次乘法。

\(\textsf{Shuffle via Re-Sharing}\)

• 思想：将shuffle看成一个捉迷藏游戏(hide and seek game)，躲藏方\(\mathcal{C}\)要悄悄地将数据向量\(\vec{v}\)按照约定的\(\pi\)进行洗牌，而不被寻找方\(\mathcal{A}\)发现\(\pi\)。这个问题的解决方式是，所有\(\mathcal{A}\)中的参与方将自己\(\vec{v}\)的秘密共享进行\(\textsf{Re-Sharing}\)到\(\mathcal{C}\)中，\(\mathcal{C}\)所有参与方约定一个\(\pi\)，计算\(\pi(\vec{v})\)的秘密共享，然后再次将\(\pi(\vec{v})\)\(\textsf{Re-Sharing}\)到\(\mathcal{C}\cup \mathcal{A}\)，即所有参与方中。在确定一个共谋上限\(t\)时，可以依赖穷尽\(\mathcal{A}\)，不断执行该过程，保证安全性。
• 举个例子：假设三个参与方\(\mathcal{M}=\{P_0,P_1,P_2,P_3\}\)，如果共谋上限是2，则分为\(\mathcal{A}=\{P_0,P_1\},\mathcal{A}=\{P_0,P_2\},\mathcal{A}=\{P_0,P_3\},\mathcal{A}=\{P_1,P_2\},\mathcal{A}=\{P_1,P_3\},\mathcal{A}=\{P_2,P_3\}\)六种情况。

复杂度分析：

• Notation：假设有\(m\)个参与方，\(\vec{v}\)有\(n\)条数据记录，共谋上限为\(t\)。
• Round Complexity：这等于在\(m\)个参与方中选取\(t\)个参与方，是一个组合数，最坏的情况是当\(t=\lfloor n/2 \rfloor\)，得到结果是\(O(2^m/\sqrt{m})\)，其中主导项是\(2^m\)，也就是通信轮数和参与方数量呈现指数增长；
• 一轮\(\textsf{Re-Sharing}\)：\(\mathcal{A}\)中\(t\)个参与方将自己的秘密共享\(\textsf{Re-Sharing}\)到\(\mathcal{C}\)中，每个寻找方需要传输\(nl(m-t)\)比特，整个协议传送\(nlt(m-t)\)比特。洗牌后，通信代价为\(nl(m-t)(m-1)\)。作者认为，约定洗牌\(\pi\)的过程需要\(O(n\log{n})\)的通信，因此通信代价整体为\(O(n\log{n})\)。

Discussion：

• 优化：可以约定\(\mathcal{C}\)之间共享随机种子，因此洗牌\(\pi\)可以由\(\textsf{PRG}\)生成。

Shuffle For Graph Analysis

source: Secure Graph Analysis at Scale | Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

简述：文章关注隐私保护的图计算。图计算开始于GraphSC，其基于安全排序协议。这篇文章的主要贡献是将图计算基于更高效的安全洗牌，并基于3PC设计了更高效的安全洗牌协议。我们这里主要就关注洗牌协议的构建。

\(\textsf{3-round, 6-message Shuffle Protocol}\)

• 思想：这个洗牌协议基本继承了\(\textsf{Shuffle via Re-Sharing}\)的思路，固定参与方为三方，并且假设三方服务器之间共享了随机种子。
• Sharing Semantics：该协议基于三方\(\mathcal{S}=\{S_1,S_2,S_3\}\)，和ABY3同样的Replicated Secret Sharing。对于一个秘密\(x\)，三个服务器持有的秘密共享\(S_1:\{x_1,x_2\},S_2:\{x_2,x_3\},S_3:\{x_1,x_3\}\)且满足 \(x_1\oplus x_2\oplus x_3=x\)。因为图计算很少涉及算术电路，因此这里直接对比特串进行共享。
• \(\textsf{Shuffle-Pair Sub-Protocol}\)：
  • 假设调用形式为\(\textsf{Shuffle-Pair}(\vec{v},S_1,S_2,S_3)\)；
  • 在协议开始前，每两个服务器之间都共享随机种子\(s_{12},s_{23},s_{31}\)。
  • \(S_1,S_2\)基于\(s_{12}\)产生洗牌\(\pi\)。
  • \(S_1\)洗牌得到\([\![\vec{u}]\!]_1=\pi([\![\vec{v}]\!]_1),[\![\vec{u}]\!]_2=\pi([\![\vec{v}]\!]_2)\)，\(S_2\)洗牌得到\([\![\vec{u}]\!]_2=\pi([\![\vec{v}]\!]_2),[\![\vec{u}]\!]_3=\pi([\![\vec{v}]\!]_3)\)。
  • \(S_3\)基于种子\(s_{31}\)产生\([\![\vec{w}]\!]_1\)，\(s_{23}\)产生\([\![\vec{w}]\!]_3\)。
  • \(S_1\)基于种子\(s_{31}\)产生\([\![\vec{w}]\!]_1\)，将\([\![\vec{w}]\!]_1\oplus [\![\vec{u}]\!]_1\)发送给\(S_2\)。
  • \(S_2\)基于种子\(s_{23}\)产生\([\![\vec{w}]\!]_3\)，将\([\![\vec{w}]\!]_3\oplus [\![\vec{u}]\!]_3\)发送给\(S_1\)。
  • \(S_1,S_2\)设置\([\![\vec{w}]\!]_2=[\![\vec{u}]\!]_2 \oplus ([\![\vec{w}]\!]_1\oplus [\![\vec{u}]\!]_1)\oplus ([\![\vec{w}]\!]_3\oplus [\![\vec{u}]\!]_3)\)。
  • 最终得到\(S_1:\{[\![\vec{w}]\!]_1,[\![\vec{w}]\!]_2\},S_2:\{[\![\vec{w}]\!]_2,[\![\vec{w}]\!]_3\},S_3:\{[\![\vec{w}]\!]_1,[\![\vec{w}]\!]_3\}\)并且\([\![\vec{w}]\!]_1\oplus [\![\vec{w}]\!]_2\oplus [\![\vec{w}]\!]_3 = \pi(\vec{v})\)。
  • 安全性：honest-majority semi-honest。
  • 通信轮数：一轮
  • 通信代价：假设\(\vec{v}\)长度为\(n\)，payload大小为\(m\)，字长为\(l\)，产生\(2nml\)比特通信；
• Construct \(\textsf{3-round, 6-message Shuffle Protocol}\) from \(\textsf{Shuffle-Pair Sub-Protocol}\)：
  • \(\vec{u}=\textsf{Shuffle-Pair}(\vec{v},S_1,S_2,S_3)\)
  • \(\vec{w}=\textsf{Shuffle-Pair}(\vec{u},S_2,S_3,S_1)\)
  • \(\vec{o}=\textsf{Shuffle-Pair}(\vec{w},S_3,S_1,S_2)\)

\(\textsf{2-round, 4-message Shuffle Protocol}\)：

Secret-Shared Shuffle