前言：在学校读书的时候，连续多日的口译后，感觉大脑里堆砌了很多非结构化的信息，于是会找一些强逻辑性的材料，打通打通脉络。一般会选择像抽象代数、理论计算机、密码学等相关领域的材料进行阅读，通过上下紧密的连贯性，获得思维切换的舒适感。
今天分享一篇旧文，是我在初步接触密码学的时候，以一知半解的角度成文的。本文完成于2010年，那个时候处在似乎什么都不懂，但似乎又有点明白的过程中，所以行文仍然较糙。密码学我在那个时候跟进学术前沿很紧，结合当时学术界刚刚兴起的社交网络分析的背景，还提出了几个不错的研究题目。不过后面由于机缘巧合，我转战到一个新的研究领域，从零开始，密码学这块就没有再跟进了。今天也算是一次重拾。
我觉得不管是从事什么领域，对其他的领域，如果有机会，都不要排除简单了解或者直观感受的机会。而且我以前也说过会写一些学术性的文章，就让这篇写的不是特别好的文章，作为我年久失修的领域研究工作相关写作的开局吧。
===分隔线===
可证明安全是在攻击者模型下描述的，攻击者通常拥有足够的计算资源。安全性的证明通常基于一些假设。例如，攻击者能够接触到密码系统，某些问题在计算上是困难的。
可证明安全的研究有两条主线，第一是对于一个给定的直观任务，建立正确的安全定义；第二个是尽可能在一般性的假设和猜想上完成构建和证明，例如单向函数是否成立的问题。一个重要的悬而未决的问题是如何把证明建立在P≠NP的基础之上，因为目前单向函数的成立和P≠NP的猜想不得而知。
有些证明基于一些安全模型，例如randomoracle model
可证安全采用渐进的方法，根据多项式时间归约对难题进行分类，如果一个计算能力有限的攻击模型针对某种体制攻击的优势(advantage)是可以忽略的，则认为这个体制是安全的。这个在理论上尽管有很重要的保证，但是在实践当中由于需要对安全参数进行初始化，需要知道安全参数的具体情况，不恰当的归约会造成攻击模型成功的概率增大，或者对计算资源的要求比预期的增多。
concrete security所有攻击者可用的资源参数化，例如运行时间、内存消耗以及其它系统资源，如可以获得的明文的数目、对oracle可用的查询次数。如此则可以得出攻击者的优势上限。
语义安全，在公钥密码体制中应用广泛。一个语义安全的密码系统要求计算能力有限的攻击者无法仅仅从密文和公钥中得到明文的重要信息。
语义安全实际考虑的是被动意义下的安全，即攻击者只能根据自己设计的明文通过公钥得到密文，并且考察密文的特性。文献[1]中给出的语义安全的定义：即使攻击者可以得到除y外任意密文对应的明文，但也无法得知m(y的明文)除长度外的任何信息。
语义安全没有考虑选择密文攻击的情况，在选择密文攻击的情况下，攻击者可以得到所选择密文对应的明文，许多语义安全的体制在选择密文攻击的模型下是不安全的。所以，对于通用的加密体制而言，语义安全的标准已经不够了。
Goldwasser/Micali于1982年提出语义安全，后面又证明了语义安全与密文不可区分性的等价性。文献[1]表示，不可区分性指即使攻击者可以得到除y外任意密文对应的明文，但是无法以远大于1/2的概率确定y来源于哪一个mb的密文。
由于对手也拥有公钥，因为加密算法必须引入随机性，否则攻击者可以直接加密m0以及m1,直接和输出进行对比，成功猜测oracle的选择。
语义安全的加密算法有Goldwasser-Micali,El Gamal，Paillier，它们都是可证明安全的，同时它们的语义安全可以归约到一些数学难题上，例如DDH，二次剩余等。
其他一些非语义安全的算法如RSA可以在某些增强的假设下语义安全，例如OptimalAsymmetric Encryption Padding(OAEP).
在选择密文攻击模型下，攻击模型下攻击者可以选择任意密文，在一个未知的密钥下得到它的明文，有许多安全的体制在密文攻击的背景下是不安全的，
适应性选择密文攻击，攻击者根据前一次交互得到的结果，构造下一次的密文以作为解密的输入，简称为CCA2
References:
[1]. Koblitz, N. and A.J. Menezes, Another Lookat” Provable Security”. Journal of Cryptology, 2007. 20(1): p. 3-37.
我的100小时计划进展
时间4.22
训练时长2小时,交传英中
累积时间41.5小时
剩余天数32天
喜欢我的文章的么？那就分享到朋友圈让更多人看到吧。
想看更多相关文章，关注公众号 ScalersTalk 回复m查看。或者去我的站点 ScalersTalk.com 查看历史文章。
有任何问题随意留言，与我分享你的阅读感受。也可以给我提问题哦。
欢迎任意调戏，但不可以恶意灌水，否则小心我顺着网线找到你。