笔记分享|浙大暑期密码学课程：两方安全计算
上篇笔记是对于可证明安全基础课程的整理，详情请见笔记分享|浙大暑期密码学课程：可证明安全基础。
本篇笔记对张秉晟老师在浙江大学的暑期Crypto School的《MPC I》课程进行了整理，可前往以下b站链接或点击下列视频观看完整课程。
浙大暑期Crypto课程-MPC I（上）
https://www.bilibili.com/video/BV1yX4y1p7rG/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
浙大暑期Crypto课程-MPC I（下）
https://www.bilibili.com/video/BV1bX4y1p7qu/?spm_id_from=333.788&vd_source=15b7926a3a203446fa868f18be9bc87e
摘要
以下是衡量安全多方计算的三个维度，主要包括安全假设，安全保障和性能，其中安全假设一般注重同步网络中的半诚实敌手，下图介绍了三个维度中主要考量的要点。
两方安全计算的设计策略
一般的设计思路可以分为自顶向下和自底向上，如下图所示，三个层次主要包括协议层，原语层和假设层。
协议是密码学中最高层次的，如MPC协议，PSI协议等，原语是第二层次的，主要包括加密，数字签名等算法，假设是最低层次的，任何的协议和原语的安全性都依赖于一些假设，比如求解离散对数问题是困难的，求解大整数分解问题是困难的。
一般设计协议是自顶向下，教学采用自底向上，教学采用该方法可以易于让学生接受。
Elgamal加密
下图是Elgamal加密的示意图，Elgamal是一种公钥加密方案，主要由初始化，密钥生成，加密和解密四个算法构成。
根据上次课程所讲，我们需要确定一个算法在什么假设下能够达到什么样的安全性，那么同理，我们需要考虑Elgamal在何种假设下可以达到什么样的安全性。
接下来下图定义了公钥加密中IND-CPA的安全性博弈定义。
Elgamal是IND-CPA安全的，张老师也在白板上推导了Elgamal的IND-CPA安全，更多内容请见录播课程。
在安全计算中，我们希望能够在不知道私钥的情况下，对密文进行运算，运算的结果解密后和明文的运算结果保持一致，我们记为数据的延展性。
同态加密解决了上述的问题，接下来我们简要讲解一下Lifted Elgamal加密算法。
Lifted Elgamal加密是满足加法同态性，并且只要消息空间范围不大，我们可以直接通过计算离散对数，得到最后的明文消息。
同态加密及在两方安全计算的应用示例
假设下面是一个两方计算模型，P1和P2分别输入a和b，P1得到最后的结果f(a,b)，如下图所示。
我们可以采用单边模拟（one-side simulation）的方式来证明该协议的安全性。
我们仍然采用之前的例子来讲解安全多方计算，即两个参与方，分别计算a和b的乘积，即a AND b，具体如下图所示。
下图是本协议的交互方式，主要是基于Lift Elgamal进行构造。
本方案的正确性显然能够满足，该方案的正确性主要基于Lift Elgamal的正确性，如下图所示。
下图主要描述了P1的隐私，即P2只能看到随机的密文，而得不到其他任何信息。
下图是修复后的协议，在该协议中，通过选取一个随机值r'，可以实现P2的隐私保护，即P1得不到P2的输入相关信息。
下图所示是仅有两条消息构成的两方计算协议。
接下来的例子，将一个比特扩展到多个比特，实现了标量的乘法操作，如以下两张图所示。
下图是上述两方计算协议中，P1和P2的隐私性解释如下：P1只能看到最终输出的随机加密密文，P2只能看到P1输入的随机加密密文。
下面同时给出了第一个两方协议的扩展和在汉明重量计算中的应用。
下图是计算汉明重量的方法，协议和安全性，协议的安全性和之前所提的标量乘法的安全性相类似。
最后，张老师还对方案给出了详细的安全性证明，有兴趣的同学可以观看录播。
(PS：笔记里是作者自己整理，可能会有一些不太准确的表达，也会有一些不当的理解，欢迎大家在留言区指出，一起学习交流)
往期推荐
1.笔记分享|浙大暑期密码学课程：可证明安全基础
2.深入浅出零知识证明（一）：Schnorr协议抗合谋的秘密分享协议4.重新审视ECDSA中的Paillier算法