谁能科普一下witness encryption是什么样的加密机制？ 第1页

Witness Encryption（证据加密）在 [STOC:GGSW13] 首次提出。传统加密里解密的条件是知道私钥，保密的条件是完全不知道私钥；证据加密里解密的条件是知道证据，保密的条件是没有证据。下文考察 WE 的定义。

令 为字符串上的二元关系，为了方便起见，关系中的第一个串叫做“命题”，第二个串叫做“证据”。适用于 的 WE 是指两个概率多项式时间算法：

• 加密算法 ，输入命题 和消息 ，输出密文 ；
• 解密算法 ，输入密文 和证据 ，输出解密结果 。

这 WE（完美）正确，是指对任意 和 有

这 WE（计算意义下非一致）安全，是指对任意命题和电路组成的序列 ，若 且 ，则

其中 是指使坏者 (adversary)， 叫做挑战命题 (challenge statement)。电路的规模可以以电线根数计。

通常考虑 ，此时它诱导的语言 ，下文只考虑这种关系。

习题 1. 证明若 ，则对任意 ，存在着适用于 的正确、安全的 WE。

注意习题 1 蕴含着一个重要推论：在现有的技巧下，WE 不蕴含困难性，这一点和不可区分混淆 (indistinguishability obfuscation) 很像。扩展阅读 [FOCS:WicZir17]：在 LWE 假设下，适用于 3SAT 的 WE 蕴含 niO。

习题 2. 回顾哈希证明系统 [EC:CraSho02] 的定义，你能找到一个具有统计意义下安全性（请自行定义）的 WE 吗？它适用于什么关系？

习题 2 的反方向很有趣，[STOC:GGSW13] 证明了：若 WE 统计意义下安全，则 。

习题 3. 证明上面提到的这个命题。提示：。

WE 怎么构造？

[STOC:GGSW13] 里也给出了第一个适用于任意 的 WE 的构造：先构造了一个 WE，用于某带有 Levin 归约的 NP-完全关系（具体来说是精确覆盖问题），然后利用 Levin 归约扩展到任意 NP 关系。

事后诸葛亮来说，这个构造其实并不是很有趣，因为它就是假设这个构造是安全的，并且也没有在一般多重线性群模型 (generic multilinear group model) 里证明假设成立。（注：一般多重线性群和一般线性群没关系。）

更有趣一些的构造可见于 [C:GenLewWat14]，也可以直接用 niO 或者 iO 构造。前者的证明方法和主流标准模型 iO 的证明方法是差不多的，需要通过一系列过渡分布枚举所有的证据。

一个最近的工作是 [C:BIOW20]，不过我还没细看。

WE 怎么用？（错误示范）

非常朴素的用法是按照想当然的直觉使用，但通常事与愿违。

一个错误用法如下：

• 令 是非平凡倍数关系，即 理解为两个二进制数，而 当且仅当 。
• 加密的时候生成两个随机大质数 ，然后令 。
• 解密的时候输入 或者 。正确性显然。
• 错误直觉下的安全性：假设因数分解困难，因为使坏者不知道正确答案，所以无法解密。

这个直觉的错误之处在于 WE 安全性不谈论“有证据，但不知道证据”的情况，只有“没有证据”的情况才具有安全性。

习题 4. 构造适用于上述关系且正确、安全的 WE，使上面的用法完全不安全。提示：不要看 ，看 。

扩展阅读：“有证据，但不知道证据”情况下安全的那种叫做可提取证据加密 (extractable witness encryption)，见 [C:GKPVZ13] 和 [C:GGHW14]。

WE 到底怎么用？（正确示范）

[STOC:GGSW13] 里一个例子是如何通过 WE + 单向函数 (one-way function) 构造公钥加密 (public-key encryption)：令 为一个输出长度是输入长度两倍的伪随机发生器 (pseudorandom generator)，令 ，令 为适用于 的 WE，定义

• 抽取 并令 。
• 就是 。
• 就是 。

可以验证这是正确的算法。IND-CPA 安全性分两步走：

1. 利用 PRG 的安全性，可以把 更换为真正随机的字符串（此时我们丧失了 ，它既难以计算出来，又经常不存在）。
2. 此时 ，可以用 WE 的安全性证明加密的消息被隐藏。（形式化的论证需要先考虑每个 下的安全性，然后再取平均数。）

注意第一步把公钥切换为“损坏版本”很重要，因为公钥就是 WE 的命题，这样做可以让 WE 的命题以几乎总是没有证据，从而利用 WE 之安全性。

WE 也可以用来构造 IBE、ABE [STOC:GGSW13]。目前还不知道如何用 WE 构造 FE，这实际上是个很有趣的问题：如果 WE 蕴含着（有趣的）FE，则 WE 蕴含着 iO。