witness encryption 学习"/>
witness encryption 学习
学习材料:.pdf
参考文献:Garg S, Gentry C, Sahai A, et al. Witness encryption and its applications[C] //Proceedings of the forty-fifth annual ACM symposium on Theory of computing. 2013: 467-476.
前面到两节来自上面的lec18,第三节来自论文。 可以大致了解证据加密的怎么构造。
1.一个小故事
想象一下,一个热爱数学的亿万富翁,想要奖励将证明黎曼假设的数学家100万美元。当然,这位亿万富翁不知道黎曼假设是否正确,也不知道数学家提出证明时他是否还活着。为了克服这两个问题,这位亿万富翁决定:
- 将100万美元的黄金放进一个大宝箱里。
- 选择世界上任意一个地方,挖一个洞,藏起宝箱。
- 加密消息中宝箱的坐标,只有证明黎曼假设的数学家才能解密它。
- 在世界上所有的报纸上公开坐标的密文。
这次讲座的目的是帮助这位亿万富翁完成第三步。为了做到这一点,为了简单起见,我们将假设证明最多为10000页。后一个假设意味着语言L = {x | x是一个可接受的黎曼假设证明}属于NP。为了简化我们提出一个电路C,它的输入是x,如果x是黎曼假设的证明,则输出1;否则输出0。
我们现在的目标是设计两台PPT机器(Enc, Dec)使得:
1. Enc(C,m)输入为电路C和m∈{0,1}作为输入,并输出密文e∈{0,1}*。
2. Dec(C, e, w)输入为电路C,密文e和证据w∈{0,1}∗,如果C(w) = 1,则输出m;否则输出⊥。
并且满足以下正确性和安全性要求:
- 正确性:如果∃w使C(w) = 1,则Dec(C, e, w)输出m。
- 安全性:如果不存在w使得C(w) = 1,则Enc(C, 0)≈ Enc(C, 1)(其中,≈表示“在计算上无法区分”)
2.一个简单的语言
作为第一个示例,我们将展示如何为一种简单的语言设计这样的加密方案。设G是素数阶的群,g是群的生成元。对于元素A,B, T∈G,考虑语言。
具有第1节正确性和安全性要求的该语言的加密方案如下:
正确性:上述加密方案的正确性在于,如果存在(a, b)∈L,则:
由于m∈{0,1}且已知g, 的值即为m的值。
安全性:就方案的安全性而言,由于语言L非常简单,我们实际上可以证明消息m是信息论隐藏的。假设(a, b)∈L不存在,但敌手有能力计算除离散对数。在这种情况下,给定两个密文c1和c2,敌手可以得到这样一个系统:
,其中s1和s2分别是c1和c2的离散对数(以g为底),是中的一个元素,使得。m的每一个值都存在r1和r2,使得上面的系统都有一个解,因此m确实是信息论隐藏的。(另一方面,如果我们有ab = r,那么方程是线性相关的)。
3.一种NP完全语言
在这一节中,我们将关注我们最初的目标,即为NP完全语言设计一种加密。具体来说,我们考虑NPC问题-精确覆盖(exact cover)。
3.1 精确覆盖NPC问题
上面第2条件应该是等于空集,选出的所有子集两两互斥。
3.2 多线性映射
3.3 Decision Multilinear No-Exact-Cover问题和假设
3.4加密方案
更多推荐
witness encryption 学习
发布评论