笔记分享 | 组队学习密码学（1）——密码学与MPC基础
基础概念
1.1 对称加密
首先双方在安全的信道上共享一个对称密钥Key，然后发送方使用这个Key对数据X进行加密，产生一个密文Y。这个Y就可以在任意信道上传输，因此Y可以被攻击者也可以叫做密码分析人员获得，他们可以解析出是 和 。接收方获得Y之后，他可以通过Key解密获得X。因此如果一个密码算法足够安全，是要求黑客攻击者获得了Y仍然不能够解密获得Key。
1.2 哈希函数
哈希函数非常的简单，将任意一个很长的数据或者是很短的数据映射为一个固定长256 bit的数据，如果数据特别短怎么办？直接补0。下面是哈希函数的6个关键性质：
1.3 素数群
群是一个集合，这个集合需要满足以下6个条件：
群的两个关键概念：
概念1：如果群元素g能够通过有限次本身运算，表达群内其他元素，则称为群的生成元。
概念2：群内元素个数称为群的阶
1.4 椭圆曲线群
椭圆曲线群跟素数群非常的相似，对外的表达还是群的6个性质，只不过它的内部运算原理发生了一点变化。
数字签名
本次活动介绍的是应用于比特币的ECDSA签名。数字签名的签名方用自己的私钥进行签名，那些验证方就会用签名方的公钥对它进行校验，也叫做验证。
私钥一般是一个随机数，它的公钥就是。所以已知y和g，如果想要把它的指数x搜出来需要指数时间才能完成，这是不可行的。所以已知私钥能够快速计算公钥，已知公钥计算私钥的难度会非常大，可能需要100年的时间。
根据上图中的签名过程，计算逆元的过程是比较简单的，我们可以快速得到R，再通过哈希函数得到r，模运算后我们可以得到签名（r,s）。而验证过程，其他验证方只需要公钥就可以快速验证，只要R`=R，则验证成功。
公钥加密
基于素数群的ElGamal加密：发送方使用对方的公钥加密数据，那么接收方接收到数据的时候就会使用自己的私钥解密数据。
第一种加密方式，我们需要将消息编码为群元素再进行操作，因为编码为群元素了之后消息 m 才可以和群元素进行运算，这里叫做乘法运算。
第二种加密方式，如果消息m就是一个256bit长度的随机数，就需要进行哈希操作，让变为群元素。
基于椭圆曲线群的ElGamal加密和基于素数群的ElGamal加密高度相似：
4
不经意传输协议
Alice 有两个数据， A0 和A1， Bob 有一个选择比特位 r = 0 或者 r = 1，这个是协议的输入。Alice 输入两个数据， Bob 输入 1 bit 的 r ，是协议运行之后有一个结果， Bob 获得这个Ar，然后 r 等于0 它就获得了A0。r 等于1，它就获得了A1， Bob 不能够获得两个数据。Alice 不知道 Bob 获得了哪个，只知道他一定获得了其中一个。
百万富翁问题与混淆电路
假设百万富翁是Alice和Bob， Alice 和 Bob 要进行一个两方运算，算法是f，然后需要构建一个与或非的门，构造出一个布尔电路。
混淆电路主要包括4个步骤：
第一步：Alice生成混淆电路
（1）生成与门逻辑电路的真值表，并且对于真值表按照与门进行计算标注
（2）将真值表中的值替换为随机数（隐藏一一映射表，隐藏真实值）
（3）使用替换值进行2次AES加密
（4）对加密结果顺序打乱，就是混淆表。混淆表内容和行号无关。就是混淆二字的由来。
第二步：Alice发送混淆表与相关数据
（1）Alice发送自己的输入值对应的替换值给Bob
（2）Bob通过不经意传输协议，从Alice那里获得他需要的的输入的替换值
（3）Alice发送与门的混淆表
第三步：Bob混淆表2次AES解密
第四步：Alice和Bob共享结果
Paillier同态加密及其应用
Paillier同态性在哪里？两个密文做密文加法运算，叫做密文抽象加。密文抽象加如何加？实际上就叫做两个密文直接相乘，把加法关系带进公式。
7
素性测试
小伙伴们可以点击 “在看” 并分享，公众号后台回复20230410，即可获得完整版PDF笔记《OpenMPC社区讲座：密码学与MPC基础》
往期推荐
1.CCVR：一种生成虚拟数据的联邦学习算法
2.PSI系列（2）组件 | OT Extension (IKNP)PSI系列（1）组件 | Cuckoo Hashing4.笔记分享 | 冯登国院士MPC讲座（1）——MPC基本概念和基础组件