留言板
- [41]周潭平
- 谢谢老师上次的解答。
陈老师，下午看了你发的出版的BGV方案，还是发现好像有个问题呢。
感觉BGV的公钥选取的有问题。作为公钥的Aj在后面都没有用到，并且假如同时把Aj和tao(那个不好打，用谐音了)作为pk的话，我们用矩阵tao–A就可以得到Powersof2(sj')了吧？？？ - 我的回复(2014-4-6 15:31)：TAO是用Powerof2(s)与A的第一列做加法得到的。根据LWE困难性，是无法解出s的。
- [40]lac77
- 但我们看到 r←Z⋂(-2^(ρ' ),2^(ρ' ) )
- [39]lac77
- 谢谢陈老师～在DGHV中证引理4.3时 提到r将公钥参数导致的噪声、x*导致的噪声都淹没，但我们看到，而公钥参数导致的噪声、x*导致的噪声并不能保证 mod 2之后是整数啊，怎么能保证不引起r分布的变化呢
BGV12和GHS12a-d 我理了一下框架 ，因为有遇到不懂的地方所以又回来看DGHV，想找点启发～理解更深一点～～
- [38]lac77
- 关于为什么Evaluate（pk,C,c1,...,ct）里为什么有pk我没有太想明白，想请教～
我理解pk存在的意义：笼统的来说，
1、评估一个电路不含有重加密过程的话，因为需要x0所有有公钥参与
2、含有重加密过程的话因为有c1->c1*的加密过程所以需要pk2
x0和pk2都包含在pk中
但是
1、Gentry的PhD里讲到重加密，包含：
用pk2加密c1
evaluate（pk2,C解密，对sk1的加密，对c1的加密）
这个Evaluate包含pk2是什么道理呢？
2、Gentry的PhD里讲到evaluate是一个嵌套，包含：
augment
reduce
次级evaluate
第一步我理解是将待评估电路翻译成增强电路组，第二步将次级增强电路组反译成次级待评估电路（可能之间还有个用剥离的那级电路做计算的？还木看完）第三步是个次级评估
这里面的公钥存在的道理也不是很清楚了
3、Computing Arbitrary Functions of Encrypted Data里面讲完重加密还讲了个对增广加法电路的评估过程
evaluate（pk2,C增强加，对sk1的加密，对c1的加密，对c2的加密）
这里面就有俩问题了
1、evaluate里待评估电路不再需要增强了，那么这实质上是一个增强电路加+一个重加密过程么？
2、如果不是的话，evaluate做了什么？pk2是干嘛用的？
求指导～～ - 我的回复(2014-3-18 12:40)：我在博文里已经好说的很清楚了，可以有也可以没有，关键看是采用什么方法约减噪音。建议你读后面的论文，例如BGV方案。现在的全同态和以前的有很大进步了，而且不太一样了。那个嵌套我曾经花了很多时间理解了，但是现在看来没有任何意义，它只是Gentry想形式化的去表达罢了。
- [37]周潭平
- 老师请教一下： bv11b每次门操作的输入都要求同一层的密文， 这会导致 什么缺点？比如说要算对应明文1+0+1，应该怎么算？
-
我的回复(2014-3-18 12:34)：由于密文的乘法后需要进行重线性化操作，所以每次计算后密钥都变了。所以密文再做计算前，必须保证是在同一层电路上，即密文对应的密钥必须相同。缺点就是如果不在同一层必须要转换到同一层。
明文是1+0+1，假设对应的密文是c1+c2+c3，首先计算c1+c2得到密文的和为c12，对应的是新的密钥。然后c3需要更新到和c12一样的密钥，然后和c12做加法。
- [36]王志杰
- 听说超难中。估计大陆不多于5篇。
- [35]王志杰
- 大陆高校总共中了多少篇每米？
- [34]s200725020430
- 陈老师，在基于整数的全同态中安全主要是基于近似最大公约数问题的，在求解N个数的最大公约数时，文章中指出可以采用近似丢番图的方法及LLL方法求解。文章中说对M矩阵（由公钥构成的矩阵）用LLL方法进行求解，目标是求一个最短向量v。为什么v=(p0,p1,...,pn).M呢？
- [33]孙爽
- 陈老师，还是比较的问题，虽然有了逻辑比较器，在明文中判断只需要L1，L2，L3的值哪个是1，但是转换到密文上再怎么判断呢？
- [32]周潭平
- 请指教。 在lwe问题中搜索性问题归约到判定性问题的归约过程中，用到了当p<poly(n)时，才使得证明成立了。如果我们用的p=2^n。方案的归约就得到指数级别了。归约还有效吗？
来自the learning with errors problem 一文引理3.1。 - 我的回复(2013-12-23 19:57)：关键看你噪音B取多少。近似因子如果是指数就是不安全的了。
- [31]s200725020430
- 陈老师，在基于整数的全同态中，为什么说c*是允许多项式输出的有效秘文，就说c*/p与某个整数偏离1/8啊（within 1/8 of an integer）?
- [30]s200725020430
- 如果有3个数经过log3/2(3)次后变成两个数，log3/2(3)应该等于2.多啊。而3个数经过1次3for2技术不就得到两个数了吗？
- 我的回复(2013-12-21 18:13)：最多log3/2(k)次。最多----你要考虑最坏情况的。
- [29]s200725020430
- 为什么k个数经过3for2的技术最多log3/2(k)次变成两个数啊
- 我的回复(2013-12-20 17:38)：你自己试试，一堆数给你，3个一组，每3个数生成2个数，最后是不是得到了结果。
- [28]s200725020430
- The depth of the circuit needed to compute the final sum of two numbers is logarithmic in their bitlengths,
but if we are only interested in ⌊s1 + s2⌉ mod 2 and have the promise that s1+s2 is within
1/4 of an integer, this value can be computed by multivariate polynomial of degree 4 (and only nine
terms)，陈老师，这句话是怎么理解的啊？
- [27]孙爽
- 嗯嗯，查到了，谢谢陈老师！
- [26]孙爽
- 哦，那陈老师可以提示一下相关资料吗？
- 我的回复(2013-12-18 01:15)：逻辑-比较器
- [25]孙爽
- 陈老师，现在的全同态加密方案能否做到对比较运算同态呢？即 iff m1>m2,c1>c2（个人感觉由于语义安全这个是做不到的）.如果不能那是否可以通过构造一个“交互式的”全同态加密方案来实现？
- 我的回复(2013-12-16 18:18)：可以比较的。有个逻辑比较方法。
- [24]周潭平
- 求指教。在lwe问题中。假如把n维a的取值范围限定到特定的某个a的集合中(已知的集合)。这些集合至少要包涵多少个实例a才能保证安全?(模数是2的安全参数次幂)。
- [23]孙爽
- 陈老师，现在同态加密的算法实现是不是都用了batch技术啊。
- [22]s200725020430
- 陈老师，你好，在基于整数的全同态的那篇文章中
The depth of the circuit needed to compute the final sum of two numbers is logarithmic in their bitlengths,
but if we are only interested in ⌊s1 + s2⌉ mod 2 and have the promise that s1+s2 is within
1/4 of an integer, this value can be computed by multivariate polynomial of degree 4 (and only nine
terms).后半句this value can be computed by multivariate polynomial of degree 4 (and only nine
terms).这句话是怎么理解的啊？求解释！
