随机语义安全与双射PRGs

Question

我正在研究Boneh和Shoup的“应用密码学研究生课程”，刚刚读完了关于流密码和PRGs的章节。

本章的第一个练习介绍了随机明文消息密码的语义安全性的概念。形式上，对于定义在$(\mathcal{K}，\mathcal{M}，\mathcal{C})$上的密码${E}=(E，D)$，我们定义了一个攻击游戏，其中挑战者(而不是对手$\mathcal{A}$)从消息空间中随机选择两个消息$(m_0，m_1) \$\mathcal{M}$，在实验$b中加密$m_b$，在{0，1}$中向对手发送密码。$\mathcal{A}$然后发回一位$\hat{b} \in {0，1}$来结束游戏。$\mathcal{A}‘S在这个游戏中的优势被定义为

$$ SSRadv =\左Pr-Pr\右\ $$

$\mathcal{E}$在语义上对随机明文是安全的，如果$SSRadv$对于任何有效的对手$\mathcal{A}$是可以忽略不计的。

问题的主体询问如何在$(\mathcal{K}'，\mathcal{M}'，\mathcal{C}')$上定义密码{E}=(E‘，D')$，该$在“正常意义上”语义上是安全的(即在攻击游戏中，敌手选择$m_0$和$m_1$)，使用SSR安全(如上文所定义的)密码{E}$作为起点。对于完全上下文，该问题还声明$\mathcal{K}=\mathcal{K}'，\mathcal{M}=\mathcal{M}'$。

考虑到上一章的主题，这里的一个自然解决方案是使用安全的PRG $G$。特别地，设$G$是定义在$(\mathcal{M}，\mathcal{M})$上的安全PRG，然后对于给定的密钥$k \in \mathcal{K}$和消息$m \in \mathcal{M}$，定义$E'(k，m) = E(k，G(m))$。直观地，G将任意选择的明文$m$转化为$\mathcal{M}$的本质随机元素，$\mathcal{E}$的随机语义安全性隐含了$\mathcal{E}'$的语义安全性。为了简洁起见，我不会试图在这里详细说明实际的安全证据。

当我试图定义解密算法$D'$在这里会是什么样子时，我主要关心的是。为了撤销$G$的应用程序，我们需要$G$有一个逆，并且由于$G$定义在$(\mathcal{M}，\mathcal{M})$上，这意味着$G$是一个双射。这似乎与$G$的假定安全性相矛盾；如果我们能够很容易地为$G$定义一个逆，那么我们就可以从$G$中的相应映像中检索任何种子。

1. 是否可能有一个安全的PRG $G$也是双射的，如果是的话，对$\mathcal{M}$是否有限制(例如，$\mathcal{M}$在安全参数中是超聚的，等等)？
2. 是否有不同的方法来构建$\mathcal{E}'$来克服这个潜在的安全漏洞？

Answer 1

您的方法有几个基本问题：

• 当您在标准CPA游戏的上下文中使用构造$m \mapsto E(k，G(m))$时，您正在将敌对选择的值输入PRG $G$。在这种情况下，PRG安全并不保证任何关于PRG输出的内容。只有当PRG输入被一致选择，并且在系统中没有其他地方使用时，才能应用PRG安全性(特别是，它不能为对手所知/被对手选择)。
• 正如您所提到的，解密需要$G$具有高效的可计算逆，这与PRG安全性不兼容。另一种选择是，$G$没有弹性，这基本上违背了PRG的目的。如果您放宽了PRG的拉伸要求，那么即使是标识函数也是安全的PRG，因为它的输出看起来是随机的。显然，在构造中使用标识函数时，实际上还没有对$\mathcal{E}$做任何事情。

是否有不同的方法来构建$\mathcal E‘$来克服这个潜在的安全漏洞？

是的，但我不知道如何在不忽视问题的情况下给出合理的提示。您不需要在原始方案$\mathcal{E}$之外引入任何附加的密码原语。