如果TDP存在，那么CCA-安全的PKES存在吗？

Question

我的密码学幻灯片描述了密码问题之间的几个关系。关于以下几点，我仍然没有一个很好的理由：

如果陷阱门排列存在，那么CCA-安全的公钥加密方案存在。

这有什么道理呢？

幻灯片引用了这个文章。我想知道对此是否有一个简短的解释。

Answer 1

对于这个答案的上下文，我将假设作者想说的是加倍增强的TDP，因为这是我目前所能想到的唯一途径。(见定义7)

构造CCA安全加密

相关施工应归功于Dolev，Dwork和Naor。它基于一个CPA安全公钥加密方案、一个一次性签名方案和一个非交互式零知识参数。我们将在下面演示如何实例化这些内容。

该加密方案的基本思想是采用2\ell公钥(\mathsf{pk}_1^0,\dots,\mathsf{pk}_\ell^0)和注册会计师安全密码体制的(\mathsf{pk}_1^1,\dots,\mathsf{pk}_\ell^1)，其中\ell是一次签名方案的验证密钥长度。为了加密消息，我们将消息分别加密在\ell公钥下，在i位置，无论使用\mathsf{pk}_\ell^0还是\mathsf{pk}_\ell^1，都由一次签名方案的新验证密钥的i位来确定。然后，我们使用NIZK证明所有的密文都是同一条消息的加密，最后用一次签名方案对所有内容进行签名。

安全证明的主要思想是：

1. 由于我们有许多相同消息的加密(由NIZK的健全性强制执行)，我们可以降低到CPA安全性，同时仍然能够解密，因为我们可以使用其他密钥之一。
2. 向解密甲骨文查询的任何新密文要么使用相同的验证密钥，在这种情况下，对手需要伪造签名。或者它使用不同的验证密钥，在这种情况下，至少一个密文使用与质询密文不同的加密密钥，并且我们能够使用相应的解密密钥进行解密。

当然，仍然需要实例化所有这些构建块。

构建块.

CPA安全PKE

如果一个陷阱门排列族\mathcal{F}存在，那么由于Goldreich-Levin定理的存在，也存在一个带有硬核谓词的陷门置换家族。给定一个带有硬核谓词的TDP，存在一个用于bits的CPA安全PKE的简单构造，其中一个键盘由公钥的f_i\in\mathcal{F}描述和秘密密钥的相应陷阱门组成。密文就是简单的(f_i(r),\mathsf{hc}_i(r)\oplus m)，其中r是来自f_i's域的一个一致选择的元素，\mathsf{hc}_i表示f_i和m\in\{0,1\}的核心谓词。

如果有必要，这种加密方案可以通过对每一位单独加密来构造用于较长消息的CPA安全加密。安全性是通过标准的混合参数来实现的。

一次性签名

兰波特的构造给出了一种针对任意单向函数的固定长度消息存在的不可伪造的一次签名方案。特别是，可以从一系列陷阱门置换中实例化该构造。

非交互式零知识证明

\mathsf{NP}的NIZK可以是双增强陷阱门置换的建好 .该构造本质上是通过对哈密顿循环问题执行\mathsf{NP}-reduction和构造哈密顿循环的NIZK来实现的。在Goldreich的“密码学基础:第1卷，基本工具”的原始结构中，错误地声称该结构可从任何TDP中实例化，这在上面链接的文件中得到了纠正。