密码学选讲 课程笔记

ECNU

---

---

关于作业要求
不能理解必须手写笔记要求的意义，而且要求只是300字。我挺想问，计算机专业（其实所有专业）什么内容的笔记三四百字就够呢？三四百字能学到什么？

把PPT里所有文字或网上搜的任一段落抄一遍，就能有三百字了。你可能觉得，学生在抄的时候，即使不认真做也至少会了解到这些概念，但事实是，不感兴趣的学生抄再多，一两周也能忘掉，对以后更是几无意义（不过可以练字）；感兴趣的学生会去了解，整理个三百一千字的笔记很容易，但要手写个笔记/总结，可能除了浪费时间几无意义（不过也可以练字）。

之前上的很多选修课程，多数学生确实不会认真学，但老师也不会过多在意不想学的。像这门课，为了让不想学的学生也“学一点”，而设定这种看似可行（实际是小学中学的方式了，12年亲身实践证明不想学某东西，抄几遍也才能大概记住一点）、限制想学的学生作业的上限的，还没有见过。要求只能手写确实属于一刀切了。

无论老师是否认同，客观上手写记笔记（尤其是计算机专业）已经是相当不便且低效的方式了。你希望学生记好笔记，但却不希望学生用更好的方式，记内容格式更丰富、结构更直观、查找内容更简单、管理更新更方便的笔记，不能理解。

综上，我可以用markdown或LaTeX作为笔记，但不会浪费时间把这些手抄一遍作为作业。表格都是ProcessOn现做的，文字都是手打的，谢谢。

---

感想

课程报告：主要谈谈课程学习的心得体会，可以谈谈对于密码学的研究背景，未来发展趋势等。

课程学习的感受
了解了密码学的许多基础知识，包括通信系统、常见加密算法、安全性的分类等。

密码学是很有意思但也很难的领域。许多典型的加密算法都是非常巧妙、构思截然不同的构造，但却依赖各种看似无关的数学问题，能做到目前无法被世界上的任何人轻松破解。

抽象模型也是密码学中很重要的东西，比如通信系统中的各类基本模型，或安全性模型中的挑战者与敌手、敌手能力、优势，是直观易懂但能准确描述对应问题的东西。

以前学到的一些数学知识，在学习密码学之前，确实想不到可以用作信息处理与保密。
之前用拉格朗日插值，只是很直接地为了求自然数幂和或某多项式的特定函数值，想不到可以利用多项式的性质，用作密钥共享算法；之前写BSGS，也只是为了单纯求解方程，想不到可以用$x$作为密钥设计非对称加密算法。

总之密码学知识确实是非常有创造性的，很难想象未来，会不会有什么常见算法或简单式子，能够成为全世界都在用的安全算法；如今的通用安全算法会不会因为某些研究而被破解，使全世界不得不重新考虑自己数据的加密。
现在学习的内容也仅仅是加密算法的设计，看似安全的加密算法的破解应该会更有意思。

关于 全同态加密 的感想
“密码学因应用需求而产生，也因应用需求而发展。”
互联网的发展和云计算的产生，使加密数据的搜索和处理能力越来越重要。
除云计算外，全同态加密在电子商务领域也有重要应用，如电子投票、可逆数字水印等。
这些需求都推动了全同态加密的科学研究。

全同态加密不仅用于加密信息的处理，还用于加密信息的检索。
随着云计算的广泛应用，云端服务器中的加密数据规模也飞速增长，排序搜索算法是提升信息检索效率的有效方法，且如果基于全同态加密，也可以保护隐私。

自2009年以来，许多全同态加密算法被提出，但由于问题的困难性和算法的低效率，难以广泛应用，还需要有更多的研究成果。
但全同态加密依然是富有前景的研究领域，对实现云服务安全的突破具有重要意义。

---

概要

密码设计/编码主要研究密码学中的客观规律，以获得各类可证明安全的密码方案、设计有效的密码算法，保证信息的机密性或认证性。
密码分析主要指加密信息的破译或认证消息的伪造，以获取通信或密码信息。

密码学因应用需求而产生，也因应用需求而发展。

生活中的“密码”实际指“口令”。

消息（Message）：要传输的内容，一般是比特流。
明文（Plaintext）：待伪装或待加密的消息。一般为有意义的字符或比特集，或通过某种公开的编码标准就能获得的消息。
密文（Ciphertext）：对明文施加某种伪装或变换后的输出。
密钥（Secret Key）：在明文转换为密文或将密文转换为明文的算法中需要的参数。分为对称密钥和非对称密钥。
密码算法（Cryptographic Algorithm）：简称密码。用于加密和解密的数学函数。
替代密码（Substitution Cipher）：先建立一个替换表，加密时将明文依次通过查表替换为相应的字符，得到的密文即为替代密码。替代密码的密钥就是该替换表 。分为单表替代密码和多表替代密码。
单表替代密码：生成替代密码时使用一个固定的替换表。不能抗击字母频度分析，易被破译。
多表替代密码：用多个替换表依次对明文消息的字母进行代换。

古典密码（Classic Cryptography）：使用置换或代换编码的密码。密码的安全性在于加密算法不被泄露。
现代密码：密码的安全性在于密钥不被泄露。

柯克霍夫原则/香农公理（Kerckhoffs's Principle）：
即使密码系统的任何细节已为人悉知，只要密钥未泄漏，它也应是安全的。

量子密钥分发（Quantum Key Distribution, QKD）：利用量子力学特性保证通信安全性。如果有第三方试图窃听密码，通信的双方便会察觉（任何对量子系统的测量都会对系统产生干扰）。

---

通信

通信指一方向另一方（发送方向接收方）通过某种方法或媒介进行信息传递。

通信系统的一般模型

任何的通信过程都会涉及这些设备：

• 信源：也叫信息源，将各类消息转换成原始电信号，如计算机、话筒。

电信号指随时间变化的电压或电流，原始电信号/基带信号(Baseband Signal)指信源直接将信息转换成的电信号，为未经过调制的电信号。因为其频率低，传输损耗大，一般不适合在传输介质中传输。

• 发送设备：通过调制器，进行调制/调幅/调频，将信源产生的原始电信号，转换为适合在信道中传输的调制信号。具有抗信道干扰的能力，并且具有足够的功率以满足远距离传输的需要。

• 信道：也叫频道，即信号传输介质，将来自发送设备的信号传送到接收端。

特点：
1. 输入信号与输出信号间有延迟。
2. 信号经过信道后，会衰减。
3. 信道中存在噪声，即使输入信号为零，输出信号仍然会具有一定功率。
4. 信道一般是线性的，即输入信号和对应的输出信号之间满足叠加原理。
5. 信道总具有输入信号端和输出信号。

分类：
按照传输媒介，信道可分为三类：
有线信道：以导线为传输媒质。信号沿导线进行传输，其能量集中在导线附近，因此传输效率高，但是部署不灵活。
无线信道：包括以辐射无线电波为传输方式的无线电信道、在水下传播声波的水声信道等。其在自由空间上传播信号时，能量分散，传输效率较低，且易被他人截获，安全性差，但是不需要导线。
存储信道：某种意义上，磁带、光盘、磁盘等数据存储媒质也可以被看作是一种通信信道。将数据写入存储媒质的过程等效于发射机将信号传输到信道的过程，将数据从存储媒质读出的过程等效于接收机从信道接收信号的过程。

按照功能，信道可分为两类：调制信道、编码信道。

• 接收设备：从（受到减损的）接收信号中正确恢复出原始电信号（通过解调器反变换）。

• 信宿：将原始电信号还原为信息，如计算机、扬声器。

模拟通信系统模型

信道传递的信号为模拟信号。

与一般模型基本相同。

数字通信系统模型

信道传递的信号为数字信号。

• 信源编码，信源译码：完成模拟信号的数字化转换，即A/D转换（数模转换），用一定的数字脉冲组合表示信号的特定幅度；提高信号传输的有效性，在保证传输质量的同时尽可能减少码元数目。信源译码为信源编码的逆过程。

• 信道编码，信道译码：信道编码即在信道传输数字时使用的纠、检错编码/抗干扰编码，可提高数字通信的可靠性。基本原理为在信息码元中加入特定的冗余码。接收端的信道译码器按照相应的逆规则进行解码，以 发现或纠正错误。

• 加密，解密：以特定的算法改变原有的信息数据，以提高信息的安全性。接收端会进行相应解密，恢复信息。

• 数字调制，数字解调：编码器输出的信号为数字基带信号，若要远距离、高效传输，需通过数字调制转换为高频信号，以适合在信道中传输。数字解调用来恢复数字信号。

• 同步：通信系统的双方需保证统一的时间标准，这在数字通信中至关重要。

与模拟通信系统相比，数字通信系统：
优点：
1. 抗干扰能力强，误码率低，噪声不积累。
2. 保密性强。
3. 可将来自不同信源的信号综合到一起传输。
4. 易于集成，以实现通信设备微型化。

缺点：
1. 占用较大的传输带宽。
2. 同步要求高，设备需求高，系统复杂。

保密通信系统模型

保密通信理论的研究对象。

加密

对称加密 非对称加密

密钥：一般为一个字符串或数字，在加密/解密时传递给加密/解密算法。

对称加密（Symmetric Encryption）：指加密、解密使用相同密钥的加密算法。在通信时，信源将原始数据（明文）经过加密处理（密文）后发送。接收方收到密文后，使用同样的密钥和加密算法的逆算法对密文进行解密，才能获得明文。密钥不能对外公开。
优点：算法公开，计算量小，加密、解密速度快，效率高。
缺点：双方需先同步密钥，且任意一方的密钥都不能泄露。使用对称加密时，要确保该密钥唯一、不被他人知道，会使得收、发双方所拥有的钥匙数量巨大、密钥管理成为双方的负担。

非对称加密/公钥加密（Public Key Encryption）：指由一对唯一性密钥（公开密钥和私有密钥）组成的加密方法。公开公钥不会对私钥安全性产生影响，且可用于对方进行解密。
要求：利用公钥破解私钥在"计算上"是不可行的。
优点：安全，通信前不需先同步密钥，只需保证私钥不被泄露。便于管理密钥。
缺点：速度较慢，效率较低。

Hash：为单向算法，为目标信息生成一段特定长度的唯一hash值，但不能通过这个hash值重新获得目标信息。常用在不可还原的密码存储、信息完整性校验等。

数字签名

数字签名（公钥数字签名）是只有信息的发送者才能产生的他人无法伪造的数字串，是对信息的发送者发送信息真实性的有效证明。
利用非对称加密技术。

签名者将需要被鉴别的信息通过数字摘要转成固定长度的字符串摘要，再用自己的私钥对该摘要进行加密，即得到数字签名。然后签名者公开完整的信息、数字签名、和加密私钥对应的公钥（不公开私钥）。
鉴别者验证签名时，首先通过同样的数字摘要转换信息得到摘要，然后用公钥对数字签名进行解密。若数字签名解密后与摘要相同，则可证明：该信息是由签名者签署的，且没有被篡改（如果签名者不知道私钥，则公钥解密后的信息必然不是转换后的信息；如果信息内容有改动，即使私钥正确，解密出的内容也与原文的摘要不匹配）。

数字签名只能在技术上保证内容一定是被私钥控制着认可后签署的。此外还需有一个有约束力的公共记账体系，保证私钥与真实的一方绑定，且对方会执行内容，以及任何人不能篡改，且不依赖单个节点。

数字签名的功能
1. 鉴别身份/防伪造/冒充：私钥只有签名者自己知道。
2. 防止信息被篡改。
3. 防止重放攻击。
4. 防止抵赖：数字签名具有不可抵赖性。
5. 有保密性：可加密原信息。

数字摘要
通过哈希函数，将任意长度的消息（明文）“摘要”成固定长度的短消息（密文）即摘要（digest）。该密文又称数字指纹。
非对称加密一般用于处理短信息，对于长信息，如果将消息分段再分别签名，会影响效率。可在签名前对消息进行数字摘要。

密钥协商

两个或多个实体协商，共同建立会话密钥，不需要可信第三方。

密钥分为静态密钥和动态密钥。
静态密钥可存储在某个位置，在一定时间内一直生效。其易泄漏、风险性高。
动态密钥/会话密钥不需要存储，在使用时生成。

RSA密钥交换算法

RSA密钥交换/协商算法依靠非对称加密算法实现密钥交换。
基本原理：拥有公钥的一方生成随机的会话密钥，然后利用公钥进行加密，将加密结果发给持有私钥的一方。对方使用私钥解密，双方便都得到了会话密钥。

过程：
以客户端和服务器端的连接为例。

1. 建立后连接，服务器发送RSA密钥对中的公钥给客户端。
2. 客户端生成一个随机值，作为会话密钥。
3. 客户端利用公钥对会话密钥进行加密，将其发送给服务器端。
4. 服务器端利用其私钥解密出会话密钥。
5. 密钥交换完成，服务器和客户端可以使用该会话密钥和对称加密算法进行通信。
6. 连接结束后，抛弃该密钥。

优点：
安全；不需分配密钥，只需每次生成；虽然RSA运算较慢，但会话密钥长度较小，生成依旧较快。

缺点：
会话密钥的生成完全由客户端决定，并不是真正的“协商”。客户端生成密钥的过程中可能出现安全问题。
不能提供前向安全性。

Diffie-Hellman密钥交换算法

Diffie-Hellman密钥交换/协商算法（Diffie–Hellman Key Exchange）为非对称加密算法，是一种专门的密钥交换算法。
基于计算离散对数的困难性。

过程：
假设Alice与Bob要通过DH进行信息交换，过程如下：

1. 选取两个大质数$g,p$并公开，$g,p$均为大质数，且$g$为模$p$的一个原根（即$\delta_p(g)=\varphi(p)=p-1$）。

2. Alice随机产生一个整数$a$，$a$对外保密。计算$r_a=g^a\ \mathbb{mod}\ p$，并将$r_a$发送给Bob；
   Bob随机产生一个整数$b$，$b$对外保密。计算$r_b=g^b\ \mathbb{mod}\ p$，并将$r_b$发送给Alice。

3. Alice在收到$r_b$后，可计算出密钥为$key=r_b^{a}\ \mathbb{mod}\ p=g^{a*b}\ \mathbb{mod}\ p$；
   Bob在收到$r_a$后，可计算出密钥为$key=r_a^{b}\ \mathbb{mod}\ p=g^{a*b}\ \mathbb{mod}\ p$。

即使攻击者知道公钥$g,p$，且截获了$r_a,r_b$，也无法算出$a,b$和$key$。
因为$a$的值即为方程$g^x\equiv r_a\ \mathbb{mod}\ p$的解，即离散对数运算。离散对数的最优算法应该是BSGS？复杂度为$O(\sqrt p)$。

缺点：
该算法只能用于密钥的交换，而不能进行消息的加密和解密。双方确定要用的密钥后，要使用其他对称密钥操作加密算法实现加密和解密消息。
可抵抗偷窥但无法抵抗篡改，无法抵抗中间人攻击。需搭配其它签名算法。

RSA加密算法

RSA为非对称加密算法。
基于因式分解两个大质数的乘积的困难性。

过程：
1. 任取两个不同大质数$p,q$，计算其乘积$n=pq,\ \varphi(n)=(p-1)(q-1)$。
2. 任取一个大整数$e$，满足$e,\varphi(n)$互质（比如大于$p,q$的任意一个素数）。
3. 计算$e$模$\varphi(n)$的一个逆元$k$，则$n,e$为公钥，$k$为私钥。
4. 对明文进行分组，使每组对应的十进制数小于$n$，然后对每组明文$m$进行如下加密：密文$c=E(m)=m^e\ \mathbb{mod}\ n$。
5. 通过$k$将密文$c$解密为明文$m$：$m=D(c)=c^d\ \mathbb{mod}\ n$。

其中$p,q,k$是不公开的，仅根据$n,e$计算$k$是不可能的（因为无法通过因式分解计算$\varphi(n)$）。

缺点：
因为都是大数计算，速度较慢。

Elgamal加密算法

Elgamal加密算法为基于DH算法的非对称加密算法。
同DH基于计算离散对数的困难性。

过程：
1. 选择一个大质数$p$，取两个数$g,x\lt p$，并计算$y=g^x\ \mathbb{mod}\ p$。则$p,g,y$为公钥，$x$为私钥。
2. 将加密信息分组，对每组信息$m$，随机一个$k\lt p-1$且满足$k$与$p-1$互质。
3. 计算$a=g^k\ \mathbb{mod}\ p,\ b=my^k\ \mathbb{mod}\ p$，密文$c=(a,b)$。
4. 通过$x$将密文$c$解密为明文$m$：$m=\frac{b}{a^x}\ \mathbb{mod}\ p$。

根据公开的$p,g,y,a,b$计算$x$是不可能的。

优点：
加密过程中进行了随机方式加密，抗攻击性强。

缺点：
大数运算多，较慢；密文长度为明文的两倍，传输信息量更多。

---

可证明安全性基础

一些概念

多项式有界：存在常数$c,k\gt 0$和$x_0$，使对所有$x\geq x_0$，$f(x)\leq cx^k$始终成立。也即$f=O(x^k)$，$k$为正实数。

预言者（oracle）：一个可以回答特定问题集合的一个实体。
预言机/谕示机（oracle machine）：与一个预言者相连接的图灵机。

一部预言除了图灵机之外，还包含了：
一条预言纸带（oracle tape）：印上了包含许多B（代表空白）和1的无限序列，代表了一个可以计算预言集合（oracle set）A的函式。
一个预言读取头（oracle head），像是图灵机的读写头一样可以在纸带上左右移动来读取资料，不同的是它不能写入，而且跑的纸带是预言纸带。

安全性的风险及对应特征

认证：伪装
身份认证：验证消息的真实性，即消息的来源是真实的而不是冒充的。
消息认证：验证消息的完整性，即消息在传送或存储过程中是否被修改或数据丢失。

机密性，不可区分性（IND, Indistinguishablity）：窃听/泄露
消息内容需被隐藏或保护，不被泄露。
敌手即使获得了密文，也不能得到其对应明文的任何信息。

不可抵赖性/不可否认性：否认
通信的数据携带有实体特质、不可被复制模仿的信息，确保通信数据是可确认的实体发出的。
发送方不能否认自己发送信息的行为和信息的内容。

完整性（INT），不可伪造性（EU, Existable Unforgeble）：信息篡改/伪造
识别信息是否被修改或是被伪造。

攻击

假设A与B进行了三次通信，则通信会产生三组明密文对：$(m_1,c_1),(m_2,c_2),(m_3,c_3)$。
取决于攻击者拥有的资源，攻击强度由弱到强：
唯密文攻击（COA, Ciphertext-Only Attack）：只知道密文，即$c_1,c_2,c_3$。最弱的攻击方式/安全性。
已知明文攻击（KPA, Known Plaintext Attack）：得到了一些给定的明文和对应密文，即$\{(m_1,c_1),(m_2,c_2),(m_3,c_3)\}$的任意非空子集。

非适应性选择明文攻击（CPA1, Chosen-Plaintext Attack 1）：攻击者可以任意给出明文，并获得其加密后的密文。
适应性选择明文攻击（CPA2, Chosen-Plaintext Attack 2）：攻击者可以任意给出明文，并获得其加密后的密文，且明文的选择可依赖之前获取的结果。

CPA1需一次提交所选的所有明文，CPA2可多次提交，统称为CPA，均属于被动攻击（攻击者是被动的）。

非适应性选择密文攻击（CCA1, Chosen-Ciphertext Attack 1）：攻击者可以任意给出密文，并获得其解密后的明文。
适应性选择密文攻击（CCA2, Chosen-Ciphertext Attack 2）：攻击者可以任意给出密文，并获得其解密后的明文，且密文的选择可依赖之前获取的结果。

区别同CPA1, CPA2，统称为CCA，均属于主动攻击。
CCA1的敌手在见到挑战密文后，不再拥有访问解密预言机的能力，所以CCA1也称为“午餐攻击”，即过了午餐的短暂时间就没有能力了。CCA2叫做“凌晨攻击”。

CPA/CCA指的是机密性/不可区分性（IND），不包括完整性（INT）。机密性是做区分（Distinguish），例如将密文和随机串区分开来；而完整性是指攻击者不能做伪造（Forge），和机密性无关。
目前普遍认为，任何新提出的公钥加密算法都应该在适应性选择密文攻击下达到语义安全性，即IND-CCA2。

选择文本攻击：加密者可以同时任意给出明文/密文，并获得对应的密文/明文。

确定性加密：加密方法确定，每个明文唯一确定一个密文，不会改变。如RSA。
概率性加密：每次加密时，会使用随机数生成密文。因此同一明文多次加密后的结果都不相同。如ElGamal。

确定性加密不是CPA安全的，攻击者可将明文加密后与短明文-密文表进行比对。

不可区分性

https://wenku.baidu.com/view/b04627e0dbef5ef7ba0d4a7302768e9950e76e79.html
https://www.cnblogs.com/xdyixia/p/11610091.html
$PK,SK$分别表示公钥（Public Key）、私钥（Secret Key）。

如果在IND-CPA游戏中，敌手获胜的概率可忽略不计，则称该加密算法在选择明文攻击下具有不可区分性，或 IND-CPA 安全。
或说：$\forall m_0,m_1,\ Encrypt(PK,\ m_0)\approx Encrypt(PK,\ m_1)$。

同态加密

https://www.zhihu.com/question/27645858

Homomorphic Encryption, (HE)：同态加密方案。
Fully Homomorphic Encryption (FHE)：全同态加密，即HE方案支持任意给定的f函数，只要这个f函数可以通过算法描述，用计算机实现。计算开销极大，暂时还无法在实际中使用。
Somewhat Homomorphic Encryption (SWHE)：部分同态加密，即HE方案只支持一些特定的f函数。SWHE方案稍弱，但开销会变得较小，容易实现，现在已经可以在实际中使用。

零知识证明

零知识证明（Zero-Knowledge Proof）指，证明者会向验证者证明某观点，并使其信服，但证明者不会提供任何有用信息，验证者不会获得除了“这个观点是正确的”结果之外的任何信息。

一个例子为：在不给出答案的情况下，向玩家（零知识）证明一个数独有解。证明者可以将答案填入数独，但向玩家隐藏。玩家可以任选一列/行/宫进行验证，证明者会将这9个数字打乱展示给玩家（一定是恰好组成1~9的数字），玩家确认后隐藏并恢复数字位置，玩家可以继续验证。

在密码学中的一个应用为身份验证，如：你有两个质数$p,q$，设$n=pq$，你需要向验证方证明“我持有私钥$p,q$，即我知道$n$的两个质因子”用于身份验证，但不能泄露$p,q$（整数分解的零知识证明）。

安全多方计算

安全多方计算（Secure Muti-party Computation, MPC/SMC/SMPC）的数学表述为：有$n$个参与者$P_1,P_1,...,P_n$，要将各自的秘密输入$x_i$到一个$n$元功能函数中，并计算其结果：$f(x_1,x_2,...,x_n)=(y_1,y_2,...,y_n)$。每个参与者将得知计算结果（所有$y_i$），但不能得知其他任何人的秘密输入。

MPC允许多个数据所有者以安全的方式协同计算/执行分布式计算任务，并得到计算结果，且保证任何一方都无法得到计算结果之外的其它任何信息。
MPC可以获取数据使用价值，但不泄露原始数据内容。

经典例子即百万富翁问题：在无可信第三方（TTP）的情况下，两个富翁如何在不暴露各自财富多少的前提下，比较出谁更富有。

---

哈希

设哈希函数为$H$。
一个好的哈希函数$H$应能避免以下三种攻击。

原像攻击

给定$y$，找一个$x$使得$H(x)=y$。
若该原像问题可解，则称$(x,y)$为有效对；若不可解，则称原像稳固，具有原像抗性。

对于好的哈希函数，只能通过穷举攻击进行原像攻击。对于特定哈希函数，才可以分析其特性构造有效对。

第二原像攻击

对任意给定的$x$，找一个$x'$使得$H(x')=H(x)$。
若该第二原像可解，则称$(x',h(x))$为有效对；若不可解，则称第二原像稳固，具有第二原像抗性，或弱抗碰撞性。

类似原像攻击，对于好的哈希函数，只能通过穷举攻击进行第二原像攻击。对于特定哈希函数，才可以分析其特性构造有效对。

碰撞攻击

任找一对$x,x'$使得$H(x)=H(x')$。
若该碰撞问题可解，则有两个有效对$(x,y)$和$(x',y)$，其中$y=h(x′)=h(x)$；若不可解，则称碰撞稳固，具有（强）抗碰撞性。

由生日悖论，对于输出空间为$N$的随机函数，只需计算约$\sqrt N$个值，就有很大概率发现碰撞。
所以密码的位数必须足够多。

---

Shamir密钥共享算法

密钥共享问题
将密文加密为$n$个shadow。当且仅当至少同时拥有$k$个shadow时，可以恢复出原密文。
$k\leq n$，记为$(k,\ n)$。

Shamir密钥分割

1. 随机一个质数$p$和一个$k-1$次多项式： $$f(x)=\sum_{i=0}^{k-1}a_ix^i\ \text{mod}\ p$$ 令$a_0$取值为密文$s$，则有$f(0)=s$。
2. 随机$n$个互不相同的整数$x_0,x_2,...,x_{n-1}$，满足$1\leq x_i\lt P$。
3. 将随机的$n$个点值$f(x_i)$作为$n$个shadow，并保密。
4. 销毁$f(x)$。$x_i$可以公开。

Shamir密钥重构
当拥有至少$k$个shadow时（记为$y_0,y_2,...,y_{k-1}$），计算

$$s=f(0)=\sum_{i=0}^{k-1}y_i\prod_{j\neq i}\frac{-x_j}{x_i-x_j} \text{mod}\ p$$

即可获得密文$s$。

拉格朗日插值
$n+1$个点可唯一确定一个$n$次多项式。
设已知原多项式$f(x)$的$n$个点$(x_i,y_i)$，则$f(x)$在点$x$处的取值为：

$$f(x)=\sum_{i=0}^ny_i\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}$$

分组密码的工作模式

电子本模式（ECB）
$C_i=E_k(M_i)$
(1) 一种最简易的工作方式；
(2) 相同密钥作用下，在相同的明文加密后将产生相同的密文 ，易于暴露明文的固有格式；
(3) 各密文块间缺乏相关性，信息易于受到块替换攻击 。

密码分组链接模式（CBC）
（1）它能够隐蔽明文的数据模式，相同的明文对应的密文一般是不同的。
（2）当信道噪音等干扰带来密文传输错误时，密文中一个位的错误将影响当前分组以及下一分组的解密

...

---

一个较快速的整数上的全同态加密方案

汤殿华, 祝世雄, 曹云飞. 一个较快速的整数上的全同态加密方案[D]. 华北计算技术研究所, 2012.

定义

符号定义

$\lfloor z\rceil$表示取近似整数，即$\lfloor z\rceil\in(z-\frac12,z+\frac12)$。
对于一个实数$z$和一个整数$p$，用$q_p(z)$表示$z$除以$p$的商，$r_p(z)\in(-\frac p2,\frac p2]$表示余数。也写作：$q_p(z)=\lfloor z\rceil_p,\ r_p(z)=\left[ z\right]_p=z-q_p(z)\cdot p$。
$O(\cdot),\ \omega(\cdot)$分别表示同阶无穷大量和高阶无穷大量。

同态加密

一致性
设一个$t$输入电路为$C$。若对由方案$\varepsilon$的$\text{KeyGen}$生成的密钥对$(pk,sk)$，满足对任意一组明文$m_1,m_2,...,m_t$和对应的一组密文$c_1,c_2,...,c_t$（$c_i=\text{Enc}(pk,m_i)$），有如下等式成立：

$$\text{Dec}(sk,\text{Evalute}(pk,C,(c_1,c_2,...,c_t)))=C(m_1,m_2,...,m_t)$$

则称同态加密方案$\varepsilon$对电路$C$具有一致性。

全同态加密方案
若一个同态加密方案$\varepsilon$对于所有的布尔电路都满足一致性，则称方案$\varepsilon$为全同态加密方案。

Somewhat同态加密方案
具有加同态和乘同态的方案，能支持的多项式次数低于解密算法的多项式次数。

扩展的解密电路
定义两种扩展解密电路：
$\text{Dec-Add}$：输入密钥$sk$和两个密文$c_1,c_2$，计算$\text{Dec}(sk,c_1)+\text{Dec}(sk,c_2)\mod 2$。
$\text{Dec-Mult}$：输入密钥$sk$和两个密文$c_1,c_2$，计算$\text{Dec}(sk,c_1)\times\text{Dec}(sk,c_2)\mod 2$。
记这两种电路的集合为$D_{\varepsilon}$。

自举同态加密方案
设$C_{\varepsilon}$为同态方案$\varepsilon$能评估的电路集合，若$D_{\varepsilon}\subseteq C_{\varepsilon}$，则方案$\varepsilon$为一个自举同态加密方案，即该同态加密方案能处理自己的扩展解密电路。

---

Somewhat同态加密方案

Somewhat同态加密方案的构造

参数：$\rho=\lambda,\ \rho'=2\lambda,\ \eta=O(\lambda^2),\ \theta=\lambda^4,\ \gamma=O(\lambda^5)$，$\lambda$为安全参数。

$\text{KeyGen}$：随机选择$\eta$位的奇素数$p$和$\theta$位的奇素数$q$，令$N=pq$。选择两个随机整数$l\in[0,\dfrac{2^{\gamma}}{p}]$，$h\in(-2^{\rho},2^{\rho})$。计算$x=pl+2h$。设置公钥$pk=(N,x)$，私钥$sk=p$。

$\text{Enc}(pk,m)$：给定消息$m\in\{0,1\}$，随机选择两个整数$r_1\in(-2^{\rho'},2^{\rho'})$，$r_2\in(-2^{\rho},2^{\rho})$，根据公钥$pk=(N,x)$，计算并输出密文$c=m+2r_1+r_2x\mod N$。

$\text{Dec}(sk,c)$：给定密文$c$，用私钥$sk=p$计算$m'=(c\ \text{mod}\ p)\mod 2$。

$\text{Evaluate}(pk,C,c_1,c_2,...,c_t)$：给定一个具有$t$个输入的布尔电路$C$，$c_i$为$t$个密文。将电路中的加法门和乘法门替换为整数上模$N$的加法门和乘法门。将$t$个密文输入到该扩展电路中执行所有操作，输出电路的结果。

解密时，设$c\ \text{mod}\ p\in(-\dfrac p2,\dfrac p2]$，则$c\ \text{mod}\ p=c-p\lfloor c/p\rceil$，所以有$m'=(c\ \text{mod}\ 2)\oplus(\lfloor c/p\rceil\ \text{mod}\ 2)$。

解密正确性

对密文$c=m+2r_1+r_2x\mod N$，可知存在整数$k$使得$c=m+2r_1+r_2x+kN$，即$c=m+2(r_1+r_2h)+p(r_2l+kq)$。
则$\dfrac cp=\dfrac{m+2(r_1+r_2h)}{p}+(r_2l+kq)$。
解密时，应有$\lfloor c/p\rceil=r_2l+kq$，就可使$c-p\lfloor c/p\rceil=m+2(r_1+r_2h)$，模$2$即可正确恢复明文$m$。
所以应有$\left|\dfrac{m+2(r_1+r_2h)}{p}\right|\lt \dfrac12$。称$m+2(r_1+r_2h)$为噪声，则当噪声的绝对值小于$\dfrac p2$时，可以正确解密。

思想框架

该方案的思路参考了Gentry的构造方式：
1. 构造一个Somewhat同态加密方案，使该同态方案能评估低次数的多项式。
2. 压缩构造方案的解密算法，使得压缩后的解密方法能表示成该方案能评估的低次多项式，以降低计算复杂度。

在电路内的每个节点，进行重加密算法更新密文，使该方案能评估任意次数的多项式或任意深度的电路，使其变为一个全同态加密方案。

加同态与乘同态

加法同态
设有两个消息$m_0,m_1$，对其加密为$c_i=m_i+2r_{1,i}+r_{2,i}x\mod N,\ i=0,1$，可知存在整数$k_0,k_1$使$c_i=m_i+2(r_{1,i}+r_{2,i}h)+p(r_{2,i}l+k_iq),\ i=0,1$。
则

$$\begin{aligned}c_0+c_1&=m_0+m_1+2(r_{1,0}+hr_{2,0}+r_{1,1}+hr_{2,1})+p(r_{2,0}l+k_0q+r_{2,1}l+k_1)\\&=\text{Enc}(pk,m_0\oplus m_1)\end{aligned}$$

即$(c_0+c_1)\mod N$就是$m_0\oplus m_1$的加密结果。噪声变化：

$$\left|m_0+m_1+2(r_{1,0}+hr_{2,0}+r_{1,1}+hr_{2,1})\right|\leq \\\left|m_0+2(r_{1,0}+hr_{2,0})\right|+\left|m_1+2(r_{1,1}+hr_{2,1})\right|$$

乘法同态
同上可得$c_0\times c_1=m_0\times m_1+2A+Bp=\text{Enc}(pk,m_0\times m_1)$，即$c_0\times c_1\mod N$就是$m_0\times m_1$的加密结果。噪声变化：

$$\left|m_0\times m_1+2A\right|\leq \left|m_0+2(r_{1,0}+hr_{2,0})\right|\cdot\left|m_1+2(r_{1,1}+hr_{2,1})\right|$$

可见，噪声在加法运算中为线性增长，在乘法运算中为平方增长。所以影响方案评估能力的主要是电路乘法深度或多项式次数。

可评估多项式次数

由上，噪声$\left|m+2(r_1+hr_2)\right|\lt 2(2^{\rho'}+2^{\rho'})=2^{\rho'+2}$。
将评估电路$C$（$t$个输入）表示为多项式$f(x_1,x_2,...,x_t)$，设其次数为$d$，系数为$b_1,b_2,...,b_t$，$|f|=\sum\limits_{i=1}^t|b_i|$。
要使密文被正确解密，则电路$C$输出中的噪声不能超过$\dfrac p8$，则

$$|f(x_1,x_2,...,x_t)|\leq |f|(2^{\rho'+2})^d\leq 2^{\eta-4}\lt \dfrac p8$$

所以该方案可评估的多项式次数$d$，满足：

$$d\leq\dfrac{\eta-4-\log|f|}{\rho'+2}$$

*这里不懂，为什么不是$\dfrac p2$而是$\dfrac p8$。

安全性

该方案的正确性基于部分近似最大公因子问题（Partially Approximate Common Divisor Problem，PACDP）。

部分近似最大公因子问题（PACDP）
给定两个整数$a_0+x_0,b_0$，其中$a_0,b_0$都是一个大素数$p$的倍数，且$|x_0|\ll p$。
根据$a_0+x_0,b_0$求$p$。

定理
设$\mathcal{A}$是该方案的一个IND-CPA攻击者，其优势为$\varepsilon$。则有一个攻击者$\mathcal{B}$，通过调用${A}$，能够解决部分近似最大公因子问题，其优势为$\dfrac{\varepsilon}{2}$。

证明类似Dijk方案中的Theorem 2，不是很懂。

---

全同态加密方案

汉明距离：两个字符串中相同位置不同字符的数量。
汉明重量：字符串中非零符号的个数。二进制串中即为1的个数。

压缩解密算法

记上述Somewhat同态加密方案为$\varepsilon^*$。
在方案$\varepsilon^*$的解密算法中，计算$\lfloor c/p\rceil$需要非常大复杂度，使得其不具有自举性。
本方案采用Gentry方案中的稀疏子集和方法，并在允许可忽略的解密错误的条件下降低数据精度值，从而降低解密算法的复杂度。

参数：$\kappa=\dfrac{\gamma\eta}{\rho'},\ r_{set}=\omega(\kappa\log\lambda),\ r_{sub}=\lambda$。

$\text{KeyGen}$：使用方案$\varepsilon^*$产生公钥$pk=(N,x)$，私钥$sk=p$。设$K=\lfloor 2^{\kappa}/p\rceil$，随机选取一个汉明重量为$r_{sub}$的$r_{set}$维比特向量$\vec s$，并要求$s_{r_{set}}=1$。在$(-2^{\kappa},2^{\kappa})$上按均匀分布随机选取整数$u_i,\ i=1,2,...,r_{set}-1$，计算$u_{r_{set}}=(K-\sum\limits_{s_i=1,i\lt r_{set}}u_i)\mod 2^{\kappa+1}$（此处模结果取最小剩余）。令$y_i=\dfrac{u_i}{2^{\kappa}},\ i=1,2,...,r_{set}$，则向量$\vec y=(y_1,y_2,...,y_{r_{set}})$。输出公钥$pk=(N,x,\vec y)$，私钥$sk=\vec s$。

$\text{Enc}(pk,m)$：使用方案$\varepsilon^*$的加密算法和$pk=(N,x)$生成密文$c^*$。计算$[c^*\cdot y_i]_2,\ i=1,2,...,r_{set}-1$，并保留二进制小数点后$n=\lceil\dfrac12\log r_{sub}+\omega(\log\log\lambda)\rceil$位精度。记取过精度后的数为$z_i$。对$[c^*\cdot y_{r_{set}}]_2$取1位整数位和5位小数位，记为$z_{r_{set}}$。输出密文$c=\{c^*,(z_1,z_2,...,z_{r_{set}})\}$。称$c^*$为主密文，$\vec z=(z_1,z_2,...,z_{r_{set}})$为扩展密文。

$\text{Dec}(sk,c)$：给定密文$c$，用私钥$sk=\vec s$计算$m'=(c^*-\lfloor \sum\limits_{i=1}^{r_{set}}s_iz_i\rceil)\mod 2$。

$\text{Evaluate}(pk,C,c_1,c_2,...,c_t)$：给定一个具有$t$个输入的布尔电路$C$，$c_i$为$t$个密文。将电路中的加法门和乘法门替换为整数上模$N$的加法门和乘法门，记为$g(C)$。将$t$个密文输入到该扩展电路$g(C)$中，在每个门进行运算时，先从每个输入的密文$c$中提取出主密文$c^*$，进行重加密操作更新密文$c^*$，然后将更新后的密文$c^{*'}$作为输入放到门中进行运算，将门的输出作为新的主密文$c^{*''}$，并根据加密算法中的扩展对主密文$c^{*''}$进行扩展，得到$\vec z''$，得到新密文$c'=(c^{*''},\vec z'')$。每个门都进行这样的操作，得到最终输出。

该方案对解密算法进行了压缩处理，使得每次压缩后的结果有足够低的次数？
为保证压缩处理不影响正确性，需有$\lfloor \sum\limits_{i=1}^{r_{set}}s_iz_i\rceil=\lfloor c^*/p\rceil\ (\text{mod}\ 2)$。下面的引理指出了：以可忽略距离接近$1$的概率成立等式$\lfloor \sum\limits_{i=1}^{r_{set}}s_iz_i\rceil=\lfloor c^*/p\rceil\ (\text{mod}\ 2)$，即最初要求的“允许可忽略的解密错误”。

引理
设$\varepsilon_1,\varepsilon_2,...,\varepsilon_t$是独立同分布的随机变量，其取值范围为$[-\varepsilon,\varepsilon]$，且该分布的期望为$E(\varepsilon)=0$。
则

$$Pr\left[\sum_{k\leq t}\varepsilon_k\geq\sqrt t\varepsilon\omega(\sqrt{\log\lambda})\right]\leq n^{-\omega(1)}$$

其中$n^{-\omega(1)}$是可忽略的量。

定理1
在该方案中，有

$$Pr\left[\sum_{i=1}^{r_{set}}s_iz_i-\sum_{i=1}^{r_{set}}s_i[c^*\cdot y_i]_2\lt\dfrac{1}{16}\right]\geq 1-n^{-\omega(1)}$$

由上引理可证明，但引入了前提条件：$n\gt\dfrac12\log r_{sub}+\omega(\log\log\lambda)$，所以可取$n=\lceil\dfrac12\log r_{sub}+\omega(\log\log\lambda)\rceil$。

定理2
设$C_{\varepsilon}$表示方案$\varepsilon$支持的电路。则对任意评估电路$C\in C_{\varepsilon}$，其输出的密文$c=(c^*,\vec z)$以可忽略距离接近$1$的概率成立$\left|\left[\sum\limits_{i=1}^{r_{set}}s_iz_i-\lfloor c^*/p\rceil\right]_2\right|\lt\dfrac14$，可得$\lfloor \sum\limits_{i=1}^{r_{set}}s_iz_i\rceil=\lfloor c^*/p\rceil(\text{mod}\ 2)$。

自举性

解密算法的计算复杂度为$64r_{sub}\lceil \dfrac12\log r_{sub}+\omega(\log\log\lambda)\rceil^{1.71}$

用加法门或乘法门扩展解密电路，所得扩展解密电路的所需要的次数最多为：

$$128r_{sub}\lceil \dfrac12\log r_{sub}+\omega(\log\log\lambda)\rceil^{1.71}$$

所以该方案满足自举性的条件为：

$$128r_{sub}\lceil \dfrac12\log r_{sub}+\omega(\log\log\lambda)\rceil^{1.71}\lt \dfrac{\eta-4-\log|f|}{\rho'+2}$$

取$r_{sub}=\lambda$，则扩展解密电路的次数约为$32\lambda\log^2\lambda$。
设$\log|f|$相对$\eta$非常小，可忽略不计。则取$\eta=\rho'\cdot 32\lambda\log^2\lambda$，则方案能评估的多项式次数约为$32\lambda\log^2\lambda$，且有$D_{\varepsilon}\subseteq C_{\varepsilon}$。所以本方案具有自举性，为全同态加密方案。

总结

因为是自由选题，不清楚什么主题的难度合适。花了一些时间在全同态加密上才发现有些东西确实看不懂也搜不到。但换主题也可能一样不会，所以就写这个内容：了解一种全同态加密算法。

大概了解了一种全同态加密方案，以及其大体构造思路：
1. 构造一个Somewhat同态加密方案，该方案主要复杂度在于解密。其安全性基于某个困难问题。
2. 对解密算法中的数据进行压缩，降低数据精度值，降低其计算所需的多项式次数。

但有些细节依旧不懂：

• 安全参数$\lambda$是只是用来衡量复杂度的么，还是实际中就直接使用一个具体的$\lambda$，然后找一个$O(\lambda^2)$位和一个$\lambda^4$位的质数，就可设计长度为$O(\lambda^{13})$的满足全同态加密的公钥？是因为这个$O(\lambda^{13})$所以还不能使用么？
• 为什么加密数据操作的过程是用电路来表示，而对加密数据的操作正确称作评估电路？
• 为什么能评估$D_{\varepsilon}$的电路称做自举？因为一般电路只包含$D_{\varepsilon}$？
• 为什么是用的稀疏子集和作为压缩方法？每一位在电路的每个节点都要这样操作么？
• 算法的计算准确复杂度与扩展解密电路的次数不同么？