博文
- 何谓“格上最坏情况的困难性与平均情况的困难性”
- 热度 1
- 格上构建密码学方案的吸引力:最坏情况困难性与平均情况困难性的连接，Ajtai,96 而密码学中的困难性需要的是：平均情况下的困难性。例如，如果随机选择的key，没有概率多项式时间的算法能够以不可忽略的概率破解该key。 而计算复杂论中的困难性是：最坏情况下的困难性。例如，没有多 ...
- GSW13方案分析
- 热度 1
- 噪音问题 ：该方案的噪音形式也很特别。如果密文 C 1 与 C 2 的噪音是 e 1 与 e 2 ，则两个密文加法的噪音是 e 1 + e 2 ，密文乘积的噪音是 m 2 • e 1 + C 1 • e 2 ，乘积噪音不仅依赖于原来的老的噪音，还依赖于密文 C ...
- Bra12方案分析
- 噪音问题 ：该方案的噪音增长形式有些特别，若密文的噪音上限是 E ，初始密文中的噪音上限为 N • B （ B 取自错误高斯分布），则密文加法的噪音为 2E + ，密文乘法的噪音近似为（ n • log q ）• E+( ) • B ，乘法噪音和前面的方案都不同，没有出现 E 2 ， ...
- BGV方案分析
- 从噪音、参数及性能、安全性三个方面对 BGV 方案进行分析。 噪音问题 ：假设密文的噪音是 E ，对应的模是 q j ，则两个密文相加后噪音增长为 2E ，乘积后噪音增长近似为 E 2 。然后进行密钥交换，噪音增长一个小的加法因子 e switch ，噪音为 E 2 + e switch ，再经过模交换噪音变为 ...
- DGHV方案分析
- 热度 1
- 我们从噪音、参数及性能、安全性三个方面对 DGHV 方案进行分析。 噪音问题 ：噪音问题直接影响方案的同态计算能力。上述方案中，两个密文之和的噪音等于噪音之和，两个密文之积的噪音等于噪音之积，所以噪音的增长主要来自于乘法。假设 DGHV 方案中的初始密文噪音为 x i ，且 | x i |B ，那么方案 ...
- ”Homomorphic Evaluation of the AES Circuit“ 论文获奖
- Homomorphic Evaluation of the AES Circuit 获得2012年Pat Goldberg Memorial最佳论文奖。 该奖从2012年世界各地的IBM研究员发表的120篇论文，来自计算机科学、电子工程、数学领域，经过筛选有5篇论文获奖。 根据谷歌搜索，这篇论文被索引了90多次。在全同态加密的发展上迈出了一大步。 该论文描述了对AES电 ...
-
论文是怎样炼成的（1）
- 热度 7
- 论文是怎样炼成的（ 1 ） 陈智罡 论文是怎样写出来的，如果不是作者本人，我们是无从知道其真实的出发点、灵感的获取、以及是如何解决过程中所碰到的困难的。就像历史，我们永远无法知道当时当事人真正的心思、真正的事情过程。 但是我们可以推测。当你读论文的时候，当你有 ...
- 常用的时间计算复杂度
- 热度 1
- 全同态加密中经常用到准多项式时间、对数多项式时间、亚指数时间等等。下面这张表详细列出了这些概念的意义及范例。表中 poly( x ) = x O (1) ,表示关于x的一个多项式。 Name Complexity class Running time ( T ( n )) Examples of running times Example algorithms const ...
- 全同态加密释疑（五）：为什么是电路观点
- 热度 4
- 全同态加密释疑（五）：为什么是电路观点 陈智罡 这个问题是许多刚接触全同态加密研究者困惑的一个问题。 也许初学者以为密码学都是基于数论观点的，其实真正的密码学的灵魂落脚点是计算复杂度。密码学中的所有方案必须要依赖于一个数学难题，这是其安全性所在的根本。问题有多难？拿什么来衡量 ...
- 全同态加密释疑（四）：转折点：LWE上全同态加密的诞生
- 热度 2
- 全同态加密释疑（四）：转折点： LWE 上全同态加密的诞生 陈智罡 Gentry 构造全同态加密方案的思想是非常“规则”的，是按照数学的思维来考虑问题的，就是围绕理想这一概念，因为只有这样才能产生密文的加法和乘法算。 Gentry 第一个全同态加密方案是基于理想格构造的。方案所选择的代数结构是理想 ...
