茉莉花新闻网

中華青年思想與行動的聚合地

有没有一种密码方式,如果破译者持有错误的密钥,那么会解译出错误但是意义通顺的明文?

Gee Law的回答

这种类型的对象通称可抵赖 (deniable) 加密,风格多种多样,其中一些是适应性安全多方安全计算的重要工具之一。风格的维度包括公钥/私钥、公开/非公开抵赖、发送者/接收者/二者之一/二者协调/完全抵赖、有准备/无准备、多重算法/单一算法、交互/非交互,这个回答里不可能完全介绍每一种,我就挑其中一个简单说说。

公钥、公开抵赖、非交互、发送者、单一算法可抵赖加密. 是指这样一组概率多项式时间算法:

  • 密钥生成算法 输出一对公私钥 (\mathsf{pk},\mathsf{sk})
  • 加密随机数长度算法 \mathsf{EncRandLen}(\mathsf{pk},1^{\ell}) 是确定性算法,输出 1^L
  • 加密算法 \mathsf{Enc}(\mathsf{pk},m;r) 输入 m\in{\{0,1\}^{\ell}},使用随机数 r\in{\{0,1\}}^L,其中 1^L=\mathsf{EncRandLen}(\mathsf{pk},1^{\ell}),算法输出密文 \mathsf{ct}
  • 解密算法 \mathsf{Dec}(\mathsf{sk},\mathsf{ct}) 输出一串消息。
  • 解释算法 \mathsf{Explain}(\mathsf{pk},\mathsf{ct},m') 输出一串随机数 r'

(指数误差)正确性是说对任意 \lambda\in\mathbb{N}m\in{\{0,1\}^\ast} 都有
\rule[2.2em]{0pt}{0pt}\Pr\left[\begin{aligned} (\mathsf{pk},\mathsf{sk})&\overset{\smash{{\,}_\$}}{\gets}\mathsf{Gen}(1^{\lambda})\\ \mathsf{ct}&\overset{\smash{{\,}_\$}}{\gets}\mathsf{Enc}(\mathsf{pk},m)\\ \end{aligned}\::\:\mathsf{Dec}(\mathsf{sk},\mathsf{ct})\neq m\right]\leq 2^{-\lambda}.

IND-CPA 安全性取通常定义。解释不可区分性是指 E_0\approx E_1,其中 E_b 是这样的:

  1. 运行 (\mathsf{pk},\mathsf{sk})\overset{\smash{{\,}_\$}}{\gets}\mathsf{Gen}(1^{\lambda}) 并把 \mathsf{pk} 发送给使坏者。
  2. 使坏者选择 m,运行
    \begin{aligned}\rule[1.4em]{0pt}{0pt} 1^L&{}\gets\mathsf{EncRandLen}(\mathsf{pk},1^{|m|})\\ r_0&{}\overset{\smash{{\,}_\$}}{\gets}\{0,1\}^L\\ \mathsf{ct}&{}\gets\mathsf{Enc}(\mathsf{pk},m;r_0)\\ r_1&{}\overset{\smash{{\,}_\$}}{\gets}\mathsf{Explain}(\mathsf{pk},\mathsf{ct},m)\rule[-1em]{0pt}{0pt}\end{aligned}
    然后把 r_b 发送给使坏者。
  3. 使坏者输出 b',这就是 E_b 的输出。

下面是使用方法:已经传输了密文之后,如果被要求公开加密时曾经使用的随机数,可以找另一条相同长度的消息,用 \mathsf{Explain} 算法编造随机数。当然,由于使坏者已经知道我们在使用这个算法,要求交出随机数是无意义行为——它自己也可以编造出随机数的。

我挑这个版本主要是它的定义简单且不平凡,研究这个对象的重要文章之一就是 How to Use Indistinguishability Obfuscation: Deniable Encryption, and More

现在说说各个维度的含义:

  • 公钥/私钥:这很好理解,就是对称加密还是非对称加密。
  • 公开/非公开抵赖:仅对公钥加密适用,即上面的 \mathsf{Explain} 算法只用公钥,还是需要私钥。
  • 发送者/接收者/二者之一/二者协调/完全抵赖:发送者就是指可以编造加密随机数;接收者是指可以编造密钥生成算法的随机数;二者之一是指可以选择要编造哪个,但是只能选一个;二者协调是指都可以编造,但是编造的时候要用同一条假消息 m';完全抵赖是指都可以编造,且编造加密随机数和编造密钥生成算法随机数的时候的假消息不需要有特殊关系。
  • 有准备/无准备:有准备是说需要被编造随机数的密文需要特殊准备(例如通过加密算法的一个开关控制);无准备没有特殊要求。
  • 多重算法/单一算法:多重算法是指允许有两套完全不同的密钥生成、加密算法,其中一套是日常使用的,另一套是专门用来编造的(这样不好,因为使坏者或许不相信用户使用的是用来编造的那一套);单一算法是指只有一套算法。
  • 交互/非交互:这也很好理解,就是发消息和接收消息的是否需要多轮交互。

考虑接收者、准备、单一算法、非交互可抵赖加密,可以证明此时算法必然是私钥、非公开抵赖,而且密钥长度和明文长度一样长,也就是说只有一次一密。

考虑接收者、准备、单一算法、非交互可抵赖加密,此时算法依然需要私钥和明文一样长,但是可以用任何(定长消息、单密文)模拟安全的加密算法,这类算法很多,例如用 ALS IPFE 就可以(这里打个广告 Succinct and Adaptively Secure ABE for ABP from k-Lin)。

在多方安全计算里,参与者互相通信的时候通常会用加密算法,在适应性安全里,使坏者可以动态(在查看了一些加密过的消息之后)查看参与方的内部状态(包括它使用的所有的随机数),这样就会揭示之前发的密文里面包含了什么消息。如果从模拟算法的角度考虑,模拟算法需要先给出密文,然后使坏者会选择消息,然后模拟算法需要给出随机数,让这些密文看起来是使坏者所选择的消息加密而来的,这个需求正好就是可抵赖加密的功能(模拟算法需要编造随机数)。当然,在这里可以用交互式加密。

同类信息

查看全部

茉莉花论坛作为一个开放社区,允许您发表任何符合社区规定的文章和评论。

茉莉花新闻网

        中国茉莉花革命网始创于2011年2月20日,受阿拉伯之春的感召,大家共同组织、发起了中国茉莉花革命。后由数名义工无偿坚持至今,并发展成为广受翻墙网民欢迎的新闻聚合网站并提供论坛服务。

新闻汇总

邮件订阅

输入您的邮件地址:

linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram