浙大暑期密码学课程|两方安全计算

浙大,暑期,密码学,课程,两方,安全,计算 · 浏览次数 : 103

小编点评

**浙大暑期密码学课程-笔记|两方安全计算视频地址:浙大暑期Crypto课程-MPC I(上)、浙大暑期Crypto课程-MPC I(下)** **笔记分享** **浙大暑期密码学课程:两方安全计算摘要多方安全计算(MPC)** **参考:笔记分享** **安全多方计算(MPC)** 安全多方计算是一种使用多个参与者的计算方案,以实现安全多方计算。 **三维安全多方计算:** * **安全假设:**半诚实敌手(敌手能够控制至少一个参与者的输出)。 * **安全保障:**通过使用加密算法保护数据安全。 * **性能:**与单个参与者执行相同的计算相比效率低。 **Elgamal加密** Elgamal加密是一种基于判定性DH的密钥交换协议。Elgamal加密的安全性基于以下两点: * 敌手无法在多项式时间内区分随机值和密文。 * 任何的协议和原语的安全性都依赖于一些假设,比如求解离散对数问题是困难的。 **两方安全计算的应用** 两方安全计算的应用包括: * 认证 * 签名 * 密钥生成 **交互式协议** 两方安全计算的交互式协议通常基于以下步骤: 1. 参与者选择一个随机数。 2. 参与者发送这个随机数给另一方。 3. 另一方使用这个随机数解密发送方发送的密文。 **隐私保护** 为了保护隐私,通常使用以下技巧: * 将参与者的输入分成多个子部分。 * 在交互过程中,对子部分进行加密。 * 在解密过程中,使用随机密钥进行解密。 **结论** 安全多方计算是一种强大的安全技术,可以用于实现安全多方计算。Elgamal加密是一种常见的安全多方计算协议。

正文

浙大暑期密码学课程-笔记|两方安全计算

视频地址:浙大暑期Crypto课程-MPC I(上)浙大暑期Crypto课程-MPC I(下)

参考:笔记分享|浙大暑期密码学课程:两方安全计算

摘要

多方安全计算(MPC)有着广泛的应用,本次课程将由来自浙江大学的张秉晟老师带来,主要讲解两方安全协议。

图片

安全多方计算的定义千奇百怪,主要可分为通俗定义狭义定义广义定义

  • 狭义上来说安全多方计算使用混淆电路秘密分享的方式来实现
  • 广义上来说可以使用全同态加密等手段来进行

图片

安全多方计算可以分为通用安全多方计算专用安全多方计算

  • 通用安全多方计算一般是将计算任务转换为布尔电路或代数电路,使用交互式协议来完成运算
  • 专用安全多方计算的效率更高,一般可以不依赖于电路的方式来解决,目前常用的协议主要有隐私求交集PSI协议

图片
以下是衡量安全多方计算的三个维度,主要包括安全假设安全保障性能,其中安全假设一般注重同步网络中的半诚实敌手,下图介绍了三个维度中主要考量的要点。

  • 敌手模型:隐匿作恶()
  • 敌手门限大于1/2无意义!
  • 设置假设:RO()、CRS()

图片

两方安全计算的设计策略

接下来我们以计算一个与门电路为例子,引入两方安全计算,下图是本协议的示意图,主要问题是如何来定义该框架的安全性。

  • 问题:安全计算\(F(a,b)=ab\)
  • 方法:将\(a\)编码(加密)后执行计算,此处应利用「同态」

图片

图片

一般的设计思路可以分为自顶向下自底向上,如下图所示,三个层次主要包括协议层,原语层和假设层

  • 协议是密码学中最高层次的,如MPC协议,PSI协议
  • 原语是第二层次的,主要包括加密,数字签名等算法
  • 假设是最低层次的,任何的协议和原语的安全性都依赖于一些假设,比如求解离散对数问题是困难的,求解大整数分解问题是困难的

图片

图片

一般设计协议是自顶向下(框架-》细节),教学采用自底向上,教学采用该方法可以易于让学生接受。

图片

Elgamal加密

我们在上次课中提到了基于判定性DH的密钥交换协议和一次一密,我们知道一次一密是目前最安全的加密方案,判定性DH假设在密码学中广泛使用,下面三张图是前一次课程的概要。

  • DH协议

图片

  • 一次一密:敌手无法在多项式时间内区分随机值和密文

图片

图片

下图是Elgamal加密的示意图,Elgamal是一种公钥加密方案,主要由初始化,密钥生成,加密和解密四个算法构成。

  • 下图\(t\)应该为\(r\)

图片

图片

根据上次课程所讲,我们需要确定一个算法在什么假设下能够达到什么样的安全性,那么同理,我们需要考虑Elgamal在何种假设下可以达到什么样的安全性。

图片

接下来下图定义了公钥加密中IND-CPA的安全性博弈定义。

图片

Elgamal是IND-CPA安全的:

  • 安全规约

图片

Lifted Elgamal

在安全计算中,我们希望能够在不知道私钥的情况下,对密文进行运算,运算的结果解密后和明文的运算结果保持一致,我们记为数据的延展性【同态?】。

图片

同态加密解决了上述的问题,接下来我们简要讲解一下「Lifted Elgamal加密算法」

图片

Lifted Elgamal加密是满足加法同态性,并且只要消息空间范围不大,我们可以直接通过计算离散对数,得到最后的明文消息

  • 计算离散对数\(DLog\),一般通过查表获得
  • \(Dec(C_1*C_2)=Dec(g^{r_1+r_2},g^{m_1+m_2}.h^{r_1+r_2})=m_1+m_2\)

图片

同态加密及在两方安全计算的应用示例

假设下面是一个两方计算模型,P1和P2分别输入a和b,P1得到最后的结果\(f(a,b)\),如下图所示。

图片

我们可以采用单边模拟(one-side simulation)的方式来证明该协议的安全性。

  • P1的安全证明:假设敌手控制P2,P1的计算结果在敌手看来是随机的,不可区分的
  • P2的安全证明:假设敌手控制P1,P2的计算结果在敌手看来是随机的,不可区分的

图片

计算a AND b

我们仍然采用之前的例子来讲解安全多方计算,即两个参与方,分别计算a和b的乘积,即a AND b,具体如下图所示。

图片

下图是本协议的交互方式,主要是基于Lift Elgamal进行构造。

图片

本方案的正确性显然能够满足,该方案的正确性主要基于Lift Elgamal的正确性,如下图所示。

  • \(d=c^b=Enc(a,r)^b\)
  • \(M=Dec(d)=a+...+a=ab\)

图片

下图主要描述了P1的隐私,即P2只能看到随机的密文,而得不到其他任何信息。

图片下图描述了P2的隐私,当然P2可能有部分信息泄漏(中间信息),P1可以从P2交互的信息中得到额外隐私信息,所以我们需要对其进行修复。

  • P1获得的是\(c^b\),是个固定值,可以通过多次解密试出b。

图片

下图是修复后的协议,在该协议中,通过选取一个随机值\(r'\),可以实现P2的隐私保护,即P1得不到P2的输入相关信息

  • P1获得的是\(c^b.Enc(0,r')\),这样每次获取的结果都是不一样的,可抗重放攻击,且根据「加法同态性」,解密后相当于(ab+0)
  • 问题:加密时用的随机数不同,是否可以进行同态计算?
    • 答案:是
    • 以ElGamal为例:
      • \(c1=Enc(m1,r1)=(g^{r1},m1.h^{r1}),c2=Enc(m2,r2)=(g^{r2},m2.h^{r2})\)
      • \(c1.c2=(g^{r1+r2},m1.m2.h^{r1+r2}),Dec(c1.c2)=m1.m2\)

图片

下图所示是仅有两条消息【逐比特发送】构成的两方计算协议。

图片

计算<a,b>

接下来的例子,将一个比特扩展到多个比特,实现了标量的乘法操作,如以下两张图所示。

图片

  • \(d=(\prod c_i^{b_i}.Enc(0,r')),Dec(d)=a_1.b_1+...+a_n.b_n=<a,b>\)

图片

下图是上述两方计算协议中,P1和P2的隐私性解释如下:

  • P1只能看到最终输出的随机加密密文
  • P2只能看到P1输入的随机加密密文

图片

计算汉明重量

下面同时给出了第一个两方协议的扩展和在汉明重量计算中的应用:

  • 汉明重量:非零符号的个数
  • 汉明距离:表示两个(相同长度)字符串对应位置的不同字符的数量,我们以\(d(x,y)\)表示两个字\(x,y\)之间的汉明距离,具体说,对两个字符串进行异或(XOR)运算,并统计结果为1的个数,那么这个数就是汉明距离。

图片

下图是计算汉明重量的方法,协议和安全性,协议的安全性和之前所提的标量乘法的安全性相类似。

  • 字符a和b的汉明重量\(\delta(a,b)=\Sigma(b_{i}+(1-2b_{i})a_{i})=\Sigma(1-2b_{i})a_{i}+\Sigma b_{i}\)

图片

图片

图片

与浙大暑期密码学课程|两方安全计算相似的内容: