容错学习(learning with errors, LWE)问题就是求解带噪声的线性方程组问题, 由Oded Regev在[Reg05] 中提出, 他也因此结果荣获2018年的哥德尔奖. LWE问题的困难性基于的复杂性假设非常弱, 但是功能却异常强大, 由于LWE问题尚无有效的量子求解算法, 因此基于LWE假设的加密方案被认为是抗量子的.

LWE问题是求解带噪声的线性方程组问题. LWE问题的困难性基于的复杂性假设非常弱, 但是功能却异常强大, 由于LWE问题尚无有效的量子求解算法, 因此基于LWE假设的加密方案被认为是抗量子的.

虽然安全多方计算已经被研究了很多年, 但是即使是最简单的协议, 也鲜有被非研究密码学\计算理论\算法的计算机科学同学知道. 此次受郁老师安排, 来参加中密会举办的密码学高端培训会, 弥补了之前知识中的漏洞, 因此决定在这里系统地介绍安全多方计算的知识.’

这次老大让我来参加中密会高端培训会之八学习一下姿势. 这次学习的真的是满载而归呀! 连脏衣服都装了我大大一包呢! 故准备把基础的东西整理一下. 让自己学习踏实一些, 也让Blog内容完备一些.

If $\mathbf{P}=\mathbf{NP}$, then $\mathbf N=1$ or $\mathbf{P}=0$.

—-Turing Machine

$\mathbf{NP}$完备性的是计算复杂性上一个至关重要的问题. 简而言之, $\mathbf{NP}$问题就是那些能够在确定多项式时间内被验证答案的判定问题, 即那些很容易就被检验的问题. $\mathbf{NP}$问题中, 有大量非常有现实意义但到现目前为止都没有好的解决办法的问题. 有关$\mathbf{NP}$完备性的讨论热度也从来没有衰减过.

2000年, 美国克雷数学研究所将$\mathbf{P}\overset{?}=\mathbf{NP}$列为七个千禧年大奖难题之一.

BGV同态加密方案是由Zvika Brakerski, Graig Gentry, Vindo Vaikuntanathan提出于[BGV12] ^[1]. 该方案是BV11b方案基础上一个较大的改进. 该方案挖掘出BV11b方案中模数切换可以降低密文的绝对噪声这一特点, 将其发扬广大, 使得在加密在无需Bootstrapping的情况下可以做到较多层数的同态乘法运算.

如果需要实现全同态加密, 该方案仍需要引入Circular Security假设和Boostrapping. 但是由于模数切换使得我们可以在不进行Bootstrapping的情况下做较多次数的同态运算, 并且使得Bootstrapping之前的密文模数变得非常小, 因此Bootstrapping是非常容易的. 因此该方法能够显著降低Bootstrapping的次数和难度.

[BV11b] ^[1]方案是最早的基于标准LWE假设的加密方案, 该方案基于一个优化版本的LWE公钥加密, 采用类似于多项式插值的方式来实现同态运算.

GSW方案是由Craig Gentry^[1], Amit Sahai与Brent Waters于2013年提出的方案, 发表于论文[GSW13] ^[2]中.

GSW方案确实如论文标题一样, 概念清晰明了, 其Intuition简单到一个刚学完线性代数的大一新生也能理解. GSW还支持基于属性的加密, 但本文中我们将不介绍这一部分内容.

当然, 完全理解GSW方案仍然需要用到一些比较进阶的知识, 如LWE问题的困难性等. 我们在本文中不会对这些知识做过多的介绍, 这些知识将在今后其他的博文中介绍. 关于同态加密的基础知识可以参阅博文同态加密(0) 基础概念, 这篇博文完成后, 地址将被更新到这里.

素数问题是数论中描述最简单却是棘手的问题, 历代数学家都在素数上耗费了大量精力, 得到了一些令人惊叹的结论, 但素数中仍存在这许多谜题…

本来都不想写初等数论的笔记, 一来是自己做的密码与初等数论关系不是特别大, 要用的数论知识都可以现学现用. 二来是初等数论还是比较简单, 写出来也不会有多少人看. 但是最近因为课程需要一些初等数论知识, 加上一直想看一看哈代的数就写了. 初等数论这块, 很多知识都可以从群论知识退化而来, 因此一些地方我不会写出标准的证明, 而是会用理解的方式来进行讲解, 这也是我自己倾向的数论学习方式.

One-way funtion is a funtion which is easy to compute but hard to invert. Here “easy” and “hard” means the lower bound of its computational complexity. The existence of one-way function is the necessary condition of the existence of modern cryptography schemes.

In computational complexity theory and cryptography, averaging argument is a standard argument for proving theorems. It usually allows us to convert probabilistic polynomial-timealgorithms into non-uniform polynomial-size circuits. (Wikipedia)