标签：Shuffle mathsf Compaction 密文 shuffle Bob pi vec

Shuffle and Compaction

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

Shuffle定义：

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(数之间内在的逻辑顺序)更弱一些，即

\[ \mathsf{Shuffle}<\mathsf{Compaction}<\mathsf{Sort}， \]

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

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

Stable定义：

TwoPartyShuffle and StableCompaction

\(\mathsf{TwoPartyShuffle}\):

协议简述：

思想：加法同态的重随机化配合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\)轮，这是肯定不可接受的，但是现在我也不太知道怎么简单高效实现这个步骤。

\(\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\)比特，考虑到0-1矩阵需要参与算数电路，需要假设字长为\(l\)比特，则这部分通信代价为\(2nl\)比特。接下来进行两次乘法，

标签：Shuffle,mathsf,Compaction,密文,shuffle,Bob,pi,vec
From： https://www.cnblogs.com/AFLuo/p/18464480