基于 2-of-2 多方安全计算的 MACI 匿名化方案

感谢 Felix Cai 对 MACI 和隐私投票中多个问题的讨论。

这篇文章将展示基于 2-of-2 MPC 技术的 MACI 匿名化方案的具体实现。本文核心内容主要分为三个部分:从任意算法到逻辑电路的实现;从逻辑电路到混淆电路的实现;利用不经意传输实现多方安全计算。最后,我们总结基于多方安全计算的匿名化方案。

算法

在 MACI 系统中,操作员 Operator(记为O)管理着一个数组,这个数组记为 deactivate[],其元素个数与 registry 数组中的元素个数相同。数组中每个位置的编号代表了 key 值(用户的编号),而每个位置存储着对应的公钥。为了更好地理解 deactivate[] 数组,可参考如下例子:在 deactivate[] 数组中,假设 registry 中的用户1(deactivate[] 数组中的第一个元素)发起了 deactivate key 操作,操作员O收到该操作请求后,如果操作的合法性被O承认,O在 deactivate[] 数组中的第一个位置填入 registry 数组中第一个位置所包含的 value 值(用户2的公钥)。另外,假设用户O没有发起 deactivate key 操作,那么 deactivate[] 数组中的第二个元素的值为 0。这样一来, deactivate[] 数组的元素个数和 registry 数组中的元素个数相同就可以理解了。

现在,为了实现 MACI 系统对管理员的匿名性,需要设计一个 2-of-2 的 MPC 方案来实现以下两个性质:

基于 2-of-2 多方安全计算的 MACI 匿名化方案

先暂且不考虑这两个要实现的目标。先考虑更换密钥的操作: A发起更换 deactivate[] 数组中属于A的公钥的请求,O验证A的请求是否合法,如果合法,则执行更换公钥操作;否则,拒绝请求。

基于 2-of-2 多方安全计算的 MACI 匿名化方案

根据上述逻辑,我们先设计一份伪代码来实现这个操作,如下:

基于 2-of-2 多方安全计算的 MACI 匿名化方案

逻辑电路的生成原理

基于 2-of-2 多方安全计算的 MACI 匿名化方案基于 2-of-2 多方安全计算的 MACI 匿名化方案

为了简单起见,暂且假设一个公钥由二位二进制数来表示(实际的公钥是 256 位二进制数)。那么,现在就需要用用户A的输入公钥,对比 deactivate[] 数组中的二把公钥。因此,需要对比二次。

基于 2-of-2 多方安全计算的 MACI 匿名化方案

逻辑电路由逻辑门组成,逻辑电路中的逻辑门被分为 层,比如上面的电路是两层。逻辑门第一层需要用户来添加输入, 其他层是中间节点,最后是根节点。对于用户输入的逻辑门,有两个输入和一个输出。其中一个输入由用户A完成。另外一个由O完成。这三个逻辑门组成了一个子逻辑电路。这个子逻辑电路负责一次公钥的对比。

基于 2-of-2 多方安全计算的 MACI 匿名化方案

逻辑电路的生成工具

在现实中,为了让一个固定的算法转换成逻辑电路,需要用到一些工具,如

1.Verilog HDL 和 VHDL:这两种硬件描述语言被广泛用于数字电路的设计和仿真,可以使用它们来描述算法的行为,并将其转换为逻辑电路的形式。这些语言都支持从高级语言(如C、C++ 和 Java)转换为硬件描述语言的形式。使用 Verilog 或 VHDL 需要一定的硬件设计和编程经验。

2.Xilinx Vivado Design Suite:这是一款商业软件,用于 FPGA(现场可编程门阵列)的设计和开发。它提供了一个综合工具,可以将高级语言或 RTL(寄存器传输级)代码转换为逻辑电路的形式。它支持多种编程语言,包括 C、C++、SystemC、Verilog 和 VHDL 等。

3.Yosys:这是一款开源的 EDA(电子设计自动化)工具,用于数字电路的设计和仿真。它支持从 Verilog 和 VHDL 等硬件描述语言转换为逻辑电路的形式。它也支持从高级语言(如 C、C++ 和 Python)转换为 RTL 代码,然后转换为逻辑电路的形式。

混淆电路(Garbled Circuit)

逻辑门的加密(混淆)

回到现在的例子中,因为我们的公钥在 deactivate[] 数组中都是有序号的(序号等价于用户的编号),且数组 deactivate[] 中的最大元素个数是有上限的(用户的个数)。因此,假设最大元素个数是N,那么,就需要构建N个子电路,然后合成一个最终的逻辑电路。

由于逻辑电路在每一个 epoch 中(一个 epoch 是区块链更新 registry 中元素的一个周期)是固定的,那么,所有用户都可以使用这个早已经生成好的,并存储在区块链中的逻辑电路。在本文例子中,由于 deactivate[] 数组中只有两个元素,因此子电路只有两个(每个子电路对应于一次公钥的对比)。

注:在一个 epoch 中,registry 数组中元素个数是固定的,因此用户的输入和数组中的元素的对比次数是固定的,因此逻辑子电路的个数是确定的,且逻辑子电路是事先可以确定好的,因此整个逻辑电路是唯一确定的。

接下来,就是将逻辑电路的每一个输入进行加密,然后将每一个逻辑门进行混淆。

先考虑加密。加密这个动作是由用户A完成的。他对每一个输入和输出的 0 和 1 用加密值表示。注意,最终的根逻辑门的输出不需要进行加密,在本案例中,就是 0(对比失败),和 1(更换新的公钥)。如图所示:

基于 2-of-2 多方安全计算的 MACI 匿名化方案

逻辑电路中的每一条引线的 0 和 1 都用加密值代替。同时,每一个逻辑电路都有一个固定的编号(这个是所有人都已知的)。例如,编号 1、2、5 就构成了一个子电路 1(比较用户的公钥和数组中的第一把公钥)。

基于此,将逻辑电路的每一个逻辑门的输入和输出(除了根逻辑门)进行加密后,在 Operator 的视角里,对于加密后的逻辑电路,他就不知道每个逻辑门的输入数字(加密值)对应的明文(是 0 还是 1)。

输入加密的方法

在混淆电路中,为每个输入值生成两个随机 key 的过程通常是使用伪随机数生成器(PRNG)来实现的。常用的生成随机 key 的实现和库有很多,例如 OpenSSL、Crypto++、libsodium 等。

输出加密的方法

基于伪随机函数 PRF 的方法是 Yao 的混淆电路中实现对输出二进制数 0 和 1 的加密的主要方法之一。具体来说,这种方法可以实现对每个逻辑门的输出进行加密,保证了数据的机密性和可靠性。

在基于 PRF 的方法中,每个逻辑门的输出都被混淆成为一组包含多个 label 的二元组,其中每个 label 都是一个随机的 01 字符串。在生成每个 label 时,可以使用伪随机函数(PRF)来实现。具体来说,可以使用一个密钥和输入值(如 0 或 1)作为 PRF 的输入,然后得到一个随机的 01 字符串作为 label。由于 PRF 是一种可以模拟真正随机数的算法,因此生成的 label 具有高度的随机性和不可预测性,保证了数据的机密性和安全性。

在混淆输出时,可以将每个逻辑门的输出表示为一个包含两个 label 的二元组(如 {label0, label1})。其中,当输入为 0 时,使用 label0 作为输出;当输入为 1 时,使用 label1 作为输出。在将逻辑门的输出发送给下一个参与方时,只发送一个包含正确 label 的二元组,保证了数据的机密性和保密性。常见的 PRF 包括 HMAC、SHA、AES 等。

需要注意的是,对逻辑门的输出采用上述方法的目的是为了便于不经意传输(oblivious transfer)的实现。

基于 2-of-2 多方安全计算的 MACI 匿名化方案

这里其实就可以推导不经意传输过程了。比如,用户 A 将这四个输出——

基于 2-of-2 多方安全计算的 MACI 匿名化方案

用户 A 输入的生成

现在,我们继续假设,用户A公钥的编号是 1,数值是 10,而数组中的二把公钥(编号分别为 0、1)的数值分别是 11, 10。也就是说用户A的公钥在数组中。

接着,用户将自己的输入,分别输入到两个子电路中(sub-circuit 1 和 2)。用户在第一个逻辑子电路(1、2、5)中进行输入。他的输入是:在编号为 1 的逻辑门输入 2674(代表二进制数 1);在编号为 2 的逻辑门输入 8798(代表二进制数 0)。用户在第二个逻辑子电路(3、4、6)中进行输入。那么,他的输入是:在编号为 3 的逻辑门中输入 9809(代表二进制数 1);在编号为 4 的逻辑门中输入 3453(代表二进制数 0)。

基于 2-of-2 多方安全计算的 MACI 匿名化方案

电路混淆

接下来的步骤就是将逻辑电路进行混淆。

基于 2-of-2 多方安全计算的 MACI 匿名化方案基于 2-of-2 多方安全计算的 MACI 匿名化方案

这样一来,根据这个表格的排序可能性,O想通过表三还原成真正的表一,会碰到 4 种可能性。那么,如果在一次证明中涉及到N个逻辑门,每个逻辑门用户A都做上述操作,那么就有4N种可能性。这样,通过排序任意颠倒,使得O很难推断出每个数字到底代表 0 还是 1。

第一次通信

基于 2-of-2 多方安全计算的 MACI 匿名化方案

不经意传输(Oblivious Transfer)

基于 2-of-2 多方安全计算的 MACI 匿名化方案

此时,我们需要回顾两个一定要保证的性质:

基于 2-of-2 多方安全计算的 MACI 匿名化方案基于 2-of-2 多方安全计算的 MACI 匿名化方案

上述三个步骤,满足了第二个性质,但是没有满足第一个性质,也就是说,O在解密了其中一个加密值后,得到了明文 1,但是,也暴露了另一个明文 0。这样一来,混淆逻辑门表就暴露了很多信息给O,这样让O有机会破解A的秘密,从而使得性质 1 无效。

基于 2-of-2 多方安全计算的 MACI 匿名化方案

从对一个逻辑门的 OT 通信可以看出整个 OT 通信的全貌,即每个逻辑门的 OT 通信都是如此,且在一次 OT 通信过程中全部完成。这样,O就能得到所有叶子逻辑门的输出,这样他就能进一步得到分支逻辑门的输出,从而最终得到根逻辑门的输出。

方案改进

上述方案中,需要且可以改进的地方有很多。例如,改进算法设计,降低算法的复杂度;改进逻辑电路的设计,让逻辑电路变得更加简单(减少门的个数,减少通信是需要传递的信息);增加方案的安全性,加大破解方案的计算复杂度;让交互变成非交互。

算法和逻辑电路的改进

基于 2-of-2 多方安全计算的 MACI 匿名化方案

但是,如果采用 Merkle Patricia Tree 的数据结构的话,对比的次数要少很多(这是因为对于 256 位的公钥来说,形成的 MPT 一定是稀疏的,因此,可能筛选二到三轮就可以筛选出想要的值)。那么,一旦算法计算复杂度下降了,逻辑电路的设计也就要简单很多。

逻辑电路的设计也有化简的可能性。

基于 2-of-2 多方安全计算的 MACI 匿名化方案

A的每个输入都不同,O也是。实际上,可以进行化简。变成如下图所示。

基于 2-of-2 多方安全计算的 MACI 匿名化方案

这样的化简可以让输入变少。

增加安全性

基于 2-of-2 多方安全计算的 MACI 匿名化方案

如果O想输入的是 0,那么他得到的结果必然是 0,也就是说,他天然知道输出 0 的加密值,那么他就天然知道了 1 的加密值。同时,由于A的输入已经是确定的,那么他可以根据A的输入值,和1的输出的加密值所在的行,去分析,如果 1 的输出的加密值所在的行,不包含A的输入加密值,那么A的输入就是 0,否则就是 1。

为了解决这类问题,我们需要对输出全部进行加密。比如使用该种方法:上表中的四个输出值 0、0、0、1 分别加密为——

基于 2-of-2 多方安全计算的 MACI 匿名化方案

——这样一来,输出的四个值分别对应为四个不同的密文。因此,在此环境下, 无法通过上述推断来反推出A的输入值是 0 还是 1。但是,这种方法使得输出加密值的个数从二变成了四。通信复杂度会增大。

此外,非交互式的不经意传输协议也值得研究。

总结

上述方法首先不考虑需要实现 MACI 匿名化的两个目标,即在明文下设计一个算法,让O能够正确判断是否执行用户A的请求。基于此,再将所设计的算法转化成逻辑电路。再将逻辑电路转化成混淆电路。需要注意的是,逻辑电路在每一个区块链的 epoch 中是固定的且能够从区块链中直接获取的。用户A获取该 epoch 的逻辑电路,利用相应工具将逻辑电路转化成混淆电路。同时,用户A将每一个混淆电路的输入进行加密,并将加密好的信息发送给O。此时,O由于不知道加密后的输入对应的明文是什么,O也就不知道用户A具体的输入是什么了,这样就实现了匿名化的第一个性质。

进而,使用不经意传输是实现第二个目的的方法。通过不经意传输,用户A并不知道O具体采用了哪些加密值进行进一步的输入,因此用户A无法推断出 deactivate[] 数组中的其他元素信息。同时,由于O通过不经意传输获得了足够的有效输入,因此O将这些有效输入输入到被加密的混淆电路中,最终能够得到正确的输出,该输出和明文下执行第一节的算法所得到的输出是相同的。因此,O就能够根据输出来判断是否要执行用户A的请求。

最终,O将上述所有操作利用零知识证明生成操作的 proof。区块链对 proof 进行验证,验证通过后,区块链将根据 deactivate[] 数组中的元素和 registry 数组中的元素来更新 registry 数组并结束 epoch 和开启下一个 epoch。

承接区块链项目定制开发

微信:btc9767

QQ :1330797917

TELEGRAM: BTCOK9

承接区块链项目定制开发


qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 基于 2-of-2 多方安全计算的 MACI 匿名化方案

发表回复