随机应变:熵安全(Entropic Security)

Contents

  1. 1. 完美安全(Perfect Security)
  2. 2. 统计安全(Statistical Security)与计算安全(Computational Security)
  3. 3. 不可区分性(Indistinguishability)与语义安全(Semantic Security)
  4. 4. 熵安全(Entropic Security)

最近,在与生成式变形金刚交流的时候,其无意间提到一个“Entropic Security”的概念,搜了搜,学习了一下,顺便复习了一下密码学中关于“安全”的理解,梳理下来,感觉挺有意思。(不禁让人回忆起本科应用密码学课上,老师关于“什么是安全”的灵魂发问。)

“安全”应该如何定义和衡量,牵扯到具体的威胁模型,这实际上并没有一个固定的答案。

请看下文:

看不懂?有错误?想看严谨表述?请咨询变形金刚或者原论文。
Russell, Alexander, and Hong Wang. “How to fool an unbounded adversary with a short key.” Advances in Cryptology—EUROCRYPT 2002: International Conference on the Theory and Applications of Cryptographic Techniques Amsterdam, The Netherlands, April 28–May 2, 2002 Proceedings 21. Springer Berlin Heidelberg, 2002.
Dodis, Yevgeniy, and Adam Smith. “Entropic security and the encryption of high entropy messages.” Theory of Cryptography Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005.
Smith, Adam Adam Davidson. Maintaining secrecy when information leakage is unavoidable. Diss. Massachusetts Institute of Technology, 2004.
Boneh, Dan, and Victor Shoup. “A graduate course in applied cryptography.” Draft 0.5 (2020).

完美安全(Perfect Security)

如果说有一个固定的答案,那就是所谓“完美安全”,达到这个要求的安全是一个什么概念呢?猜测一个密文中蕴涵的明文信息,和直接凭空猜没什么区别,并且无论在什么样的条件下都是这样。也就是说,密文和明文之间是独立的,知道密文对于推测明文的信息毫无意义,这可以用明文和密文之间的互信息为零,即来表示。

根据信息论,实现这样程度的安全有如下的结果:假设我们有一个100比特的明文,那我也需要一个来自均匀分布的(当然也是独立的)100比特密钥,来加密它,才能实现这样的完美安全。这便是一次性密码本(One-time Pad)。

这当然是一个很强的“安全”,强到一个攻击者看到这样的一个密文,和看到一些随机噪声没有任何区别。但实际上,反过来,对于信息的拥有方,这也是一个苛刻的“安全”,我要保护100比特的明文,需要同时保护100比特的密钥,为什么要多此一举?

统计安全(Statistical Security)与计算安全(Computational Security)

一个适当的放松是“统计安全”,即,我并不要求明文和密文之间是真的完全独立的,我只需要他们看起来是就好了。也就是说,只要对于攻击者来说,密文和明文之间的关联足够小,小到攻击者能窃取到信息的概率可以任意小。

比如同样100比特的明文,我现在可能只需要50比特的密钥;虽然我无法实现完美安全,但我能保证泄密的风险是可忽略的。例如,加密次,只有一次可能会被攻击者窃取到信息,那这也是一个有意义的、足够强的“安全”。

现实中,攻击者远没有那么强,即使密文中真的含有明文的信息,攻击者也提取不出来,因为攻击者的资源是有限的。这意味着,我们还可以进一步放松对于“安全”的要求,即,只要一个计算资源有限的攻击者无法提取到明文信息就好了。比如还是100比特的明文,我现在只需要20比特的密钥;虽然我无法实现统计安全(当然也就无法实现完美安全了),但我能保证对于资源有限的攻击者而言,泄密的风险是可忽略的。

这里“资源有限”应该如何准确理解呢?“有限”即在某种“界”下,然后这个“界”是现实中普遍存在的,例如,我可以说,是个多项式,对于任意一个拥有能算次算力的攻击者,都无法提取到明文信息。

注意到,计算安全依赖于对于攻击者能力的假设,需要考查现实情况,因为存在一种可能:现在是“安全”的,以后可能不“安全”。因为未来可能有更好的算法使得需要的计算大大减少,使得攻击者能在可接受的时间内从密文中提取到信息。比如,未来可用的量子计算机的出现;又或者,某个天才发现一个解决某个困难问题的妙法。

所以实际上,计算安全是在赌别人的智慧不如自己。

不可区分性(Indistinguishability)与语义安全(Semantic Security)

上面讨论的“安全”实际上并没有具体谈一个可操作化的“信息泄露”的概念?除了说明文密文互信息应该为零,或者至少可忽略之外,伴随计算安全出现的还有两个概念:不可区分性和语义安全。

不可区分性所定义的“安全”是指,攻击者无法确认一个密文的来源,具体来说,任意两个明文的密文是不可区分的。

语义安全所定义的“安全”是指,给定一个密文,攻击者无法提取到任意关于明文的信息,即,预测一个关于明文的任意函数值和瞎猜没有区别。

这两者是等价的,实际上,有些教程甚至直接把不可区分性作为语义安全的定义。

注意到,这两种“安全”并不和攻击者能力的假设绑定,比如,他们既可以作为统计安全实现,也可以作为计算安全实现。

熵安全(Entropic Security)

再次回顾上面的概念,从明文的熵的角度看看都发生了什么。实际上,我们发现,无论明文的熵是大是小,来自什么样的分布,上面的“安全”都力求保证没有任何信息泄露。或者这样说,都是假设明文来自于一个均匀分布,然后要求即使攻击者知晓了密文,明文对其而言依然几乎等同于来自于一个均匀分布。

如果我们再多考虑一个条件,即明文的熵有多大?这牵扯到这个问题本身的复杂度。比如,我们考虑两种极端情况,假设一个100比特的明文:(1)明文来自于一个均匀分布,即最小熵是最大值;(2),例如,明文只是某两个明文中的一个。

对于这两种情况,上面讨论的“安全”都能保证几乎没有新的信息给攻击者,无论明文本身的分布及其熵是什么样的。但我们想要灵活地分别处理这两种情况,因为对于(1)来说,这是一个对于防御者更为有利的条件,因为在统计上对于攻击者而言更为困难,即使密文泄露了一些信息,不意味着攻击者就能获得真正有意义的能力提升。那是不是我们可以更“简单地”实现“安全”?比如原来我需要100比特的密钥,现在只需要10个?

熵安全是考虑明文的熵足够大的情况下,例如明文来自于均匀分布(如一些特殊的数据,如key-gen生成的随机密钥),那我们可以用更短的密钥去实现某种“安全”,例如某种“不可区分”和“语义安全”。

这里我们可以牺牲的是,密文可以与明文具有相关性,但是由于明文的熵很大,这种相关性并不一定意味着密文会泄露有意义的信息。例如,考虑一个确定性加密函数,比如它实际上就是对明文空间做了一次秘密随机置换,注意到这里的明文密文互信息在防御者看来甚至等于。这肯定是不满足经典的不可区分性和语义安全的要求。

然而,对于一个来自均匀分布的明文来说,这确是足够的,因为其加密的密文也是均匀分布的。甚至,从不可区分性来说,两个不同的来自均匀分布的明文的密文也是统计上也是不可区分的。

因此,在明文熵足够大的情况下,某种程度的信息泄露(以互信息衡量)是可接受的,这是继统计安全、计算安全之后,又一个考量不同情况下需要的“安全”的条件。