Secret-shared Shuffle—秘密共享下的洗牌协议

点击上方蓝字获取更多新鲜资讯

本文介绍发表在ASIACRYPT-2020的文章

https://eprint.iacr.org/2019/1340

Secret-shared shuffle[1]可以理解为经过秘密共享置换下的洗牌后，数据集以秘密共享的形式存储。该文提出了一个两方的半诚实安全(semi-honest)模型下的秘密共享洗牌方案。在很多协议中，比如安全协同过滤(secure collaborative filtering), 茫然排序(oblivious sorting)以及在集合交集(set intersection)上的安全函数评估(secure function evaluation)等，secret-shared shuffle都作为一个基本的组成部分。实现Secret-shared shuffle的传统方式有基于公钥的密码方式和在置换网络上的对称密码方式。前者是计算约束的(computation-bound)，后者受通信约束(communication-bound)。该文利用GGM可穿刺的PRFs，提出了一个计算和通信开销都较低的方案。具体来说，该方案比基于公钥的方法快三个数量级，比基于置换网络的对称密钥密码方法快一个数量级。

1.什么是Secret-shared shuffle?

在该文中，Secret-shared shuffle协议是指，两方  和  协同shuffle一个  个元素的数据集  ，双方各自得到洗牌后的数据集的秘密共享的一部分。需要指出的是，双方都不知道shuffle的顺序，该文中采取的方法是  生成一个置换关系  ,  生成一个置换关系  ,shuffle之后的数据集为  。Shuffle前的数据集  可以是只有一方持有，也可以是由双方秘密共享的。

2. 方案概述

Permute+shuffle是指其中的置换关系只由某一方持有，比如  持有  ,  持有或者由双方秘密共享。Secret-shared shuffle可以通过两次Permute+shuffle获得。

2.1 通过Share Translation协议构造Permute+shuffle

这里假设 持有  ,  持有。

选择两个独立不相关的集合  和  ,计算  并发送给  。 计算  。如果我们假设最后的share结果是持有  而是持有 。那么，我们只需要假设 已经通过某种方式获得了  ， 计算  即为  。这种通过某种方式使得  获得  的协议称为Share Translation。

2.2 通过Oblivious Punctured Vector(OPV:茫然可穿刺向量)构造Share Translation

OPV协议：输入 ， 协议生成一个随机的向量  使得:

-  能拿到除了  之外的所有元素。

- 能拿到  的所有元素但是不知道  。

这里的OPV协议跟  OT类似。本文不对OT [1] 协议做赘述。

利用  次OPV协议,  拿到除了  的 ，其中 ,  拿到 , 其中。  可以利用  构造一个的矩阵，第  行元素为 。对任意 ， 计算  ，即第  列元素相加，对任意 ， 计算  ，即第  行元素相加。在  方，我们希望对第  个元素，能够获得  。在矩阵表示中，  ,  。然而，在  中，  并不知道  ， 在  中， 也并不知道 。但是因为异或特性，  可以直接计算 。

为了方便理解，下图一表示  的“punctured”矩阵。假设  ，则  ，即为图中黄色部分与绿色部分所有元素的异或结果。尽管黑色部分的元素未知，但是它被异或两次，不会对我们的计算结果产生影响。

图一：“punctured”矩阵

通过上面的构造，  次OPV协议后，  拿到了  ，  拿到了  和  。通过上述OPV协议构造的Share Translation协议的运行时间与  成比例关系。

2.3 通过OT和GGM PRF构造OPV

GGM PRF: 这里只进行简单介绍。对于  个元素，我们可以构造一个根为  的  层的GGM tree(如图二所示)，叶子节点  用来表示个PRF的值。

图二：GGM PRF

构造OPV： 生成GGM PRF，如之前所说，如果  的输入为  ，那么  应该可以拿到除了  之外的所有叶子节点。

• 简单的想法：假设  的第一个比特为1，  和  进行  OT，其中  的输入为1的相反数0，  的输入为  和  。因为  拿到了  ，所以他可以计算出所有第一个比特为0的叶子节点的值（  ），即图二中树的左半边。假设  的第二个比特为0， 和  进行  OT，其中  的输入11（这里第一个比特不再取反），  的输入为  。 可以拿到了  ，所以他可以计算出以  为根的子树的所有叶子节点的值（  ）。以此类推，双方执行  OT等等。但是，最终还是要执行 OT。

• 只通过 OT：对于  的第一个比特，OT方式与上面方法相同。在  获取  ，  的输入为  。因为  在第一次OT后，可以计算整个树的左半边，所以可以其自行计算  ，从而得到  。第三次OT时， 的输入为 。以此类推，一次OPV共需要  次  OT。

           该方法的运行时间与  成比例，通信开销与  有关。

2.4 基于Permutation-network(置换网络)的Permute+share协议

利用只通过 OT构造的OPV，我们可以构造计算开销与  成比例，通信开销与  有关的Share Translation协议，其中  为安全参数。

这里利用置换网络降低计算开销 [2]。主要思想是，将置换  分解成多个不相干的元素个数为  的置换  。分解之后的好处是，多个小置换构成的Share Translation可以并行运行，因此计算开销转换为与  有关。该文取  从而将计算开销降为  。

本文我们只给出了作者构造的思想，具体的协议过程还是要参照原文。作者对具体协议还给出了详细的安全性证明。

3.总结

该文章比较适合元素长度  的场景。文中的Share Translation思想在一定程度上可以归结为预计算。这种对data-independent的数据做离线处理，只将data-dependant的数据放在online计算的思想在安全多方计算中被广泛应用，极大的提高了MPC的效率。

如有错误之处，欢迎指正。

参考文献：

[1]Chase, M., Esha G., Oxana P.: Secret-Shared Shuffle. In International Conference on the Theory and Application of Cryptology and Information Security, pp. 342-372. Springer, Cham, (2020).

[2] Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) Advances in Cryptology - CRYPTO 2003. pp. 145–161. Springer Berlin Heidelberg, Berlin, Heidelberg (2003)

[3] Mohassel, P., Sadeghian, S.: How to hide circuits in mpc an efficient framework for private function evaluation. In: Johansson, T., Nguyen, P.Q. (eds.) Advances in Cryptology – EUROCRYPT 2013. pp. 557–574. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)

往期内容：

欢迎投稿

邮箱：[e-mail]

参与更多讨论，请添加小编微信加入交流群