Computational Security
Perfect Security在拥有无限算力的eav(窃听者)情况下是可证明安全的，不会泄露任何有关明文的信息，因此被称为信息论安全。然而，该方法具有密钥长度必须和明文长度等长、密钥不能复用，且加密方案有着不必要的强安全性。因此，便有了更弱安全意义上的计算安全性。
计算安全性（Computational Security），这种安全性有着两个特点：
- 它可以抵御任何拥有有限但庞大算力的敌手。
- 有着极其微小的可能性被攻破。
因此，理想状况下，这种安全性的攻破方法只有暴力穷举所有的密钥。
有两种描述计算安全性的方法：具体/渐进方法。
Concrete Approach
通过精确确定最大的被成功攻破的概率界限来描述计算安全性。敌手被认为是概率性的（randomized）。
形式化而言，有：
$(t,\xi)-secure$
A scheme is $(t,\xi)-secure$ if any adversary running for time at most $t$ succeeds in breaking the scheme with probability at most $\xi$.
具体的安全性在实际问题十分重要，但在抽象讨论上的意义而言，精确的具体安全性很难进行讨论。
在直觉上，我们可以这样认为：$t$应当足够的大，且该方法是有效的（多项式而非指数）算法；$\xi$是一个渐进等于0的值。于是，我们将重点投向渐进安全性。
Asymptotic Approach
涉及知识：图灵机，以及计算复杂性。
由之前Ⅰ里头的介绍，需要尽可能地构造出来图灵机（准确来讲是确定性图灵机）意义上的难解问题，从而构造出渐进意义上的计算安全性。
Assumption and PPT（概率意义上多项式能力）
在计算复杂性上讨论渐进安全，需要有以下假设：
- 安全参数 $n\in N$必须被任何人所知。安全参数就是具体密钥的长度。
- Honest parties（非敌手）拥有可以进行概率意义上的多项式算法能力（PPT），概率意义是指所有的PPT算法都可以无条件获取无偏的、独立的序列，多项式则是：
$\exists ~ polunomial~p(n)$,所有的honest parties都可以run in time $p(n)$ - efficient adversary也被定义为拥有PPT能力，被称为PPT adversary。
Why PPT?
- 获取无偏独立的序列数据是密码学所必需的（例如生成随机数），非敌手用此生成随机密钥，则敌手也应当具有该能力。
- PPT敌手可能还有证明里无法体现、但相较真实世界的敌手具有的附加能力。为了证明能够更加严谨完善，假定敌手具有PPT能力。
Strong Church-Turing Thesis
用类似讨论计算复杂性的方法讨论渐进安全性的另一个原因便是Ⅰ中讨论的如小标题所示的理论。任何目前实际上的模型都可以划归到多项式的算法上，也因此我们可以讨论布尔表达式、图灵机、随机预言机等可以归约到多项式上的模型。
Definition
Definition:negligible function
$\forall~polynomial~p(.),\exists N~s.t. \forall n>N:$ $$f(n)<\frac{1}{p(n)}$$
即，随着n增加，f(n)下降的的较任意的1/p(n)更快。
接下里给出形式化的渐进安全定义：
Definition: Asymptotic Approach
A scheme is secure if any PPT adversary succeeds in breaking scheme with at most negligible probability.
形式化一点？
Definition: abstract
A scheme is secure that for every PPT adversary $\mathcal{A}$，其进行特定的攻击；for every positive polynomial $p$,there exists an integer $N$ such that when $n$（被选定的一个常数）>$N$,the probability that $\mathcal{A}$ succeeds in the attack is less than $1/p(n)$。
因此，安全参数n的大小和渐进安全性息息相关。其中，honest parties一般而言运行的是固定的多项式算法，如$O(n^2)$，而防御的敌手需要针对所有多项式，也就是“有效的”算法。
Computationally secure encryption
Definition
$Gen(1^n)\rightarrow k,assume~~~~|k|\geq n$
$Enc_k(m)\rightarrow c(maybe~~probabilistic)$
$Dec_k( c)=m(deterministic)$
其中，Gen运行多项式时间，且若消息空间是固定的，可被称为fixed-length private-key encryption，与之后的操作模式相对应。
该定义是无状态的（无上下文的状态消息）
最后，该定义也满足之前类似的定义中的Correctness。
EAV security experiment(oracle)
讨论计算安全性时，有以下性质：
要求敌手具有有限算力，允许敌手有小概率获胜的机会，以及加密的消息长度可以任意长（与先前的perfect encryption区别）。
密钥仍然不可复用。
也因此，计算安全性相比于信息论安全性，具有以上的“松弛”。
oracle：
- 敌手向预言机发送两条消息$m_0,m_1$.
- 预言机按定义生成k，随机选择$b\leftarrow \{0,1\}$并生成密文c返回敌手。
- 敌手采取策略，返回b’，若$b=b’,output~~1$，否则为0.
其实预言机过程和完美加密很像，但其具体定义不同。
也因此，有以下定义：
Definition: $PrivK_{\mathcal{A},\prod}^{eav}$
$\prod=(Gen,Enc,Dec)$在以上实验若具有以下性质，则在EAV（窃听者）存在的情况下具有不可区分性： $$Pr[PrivK_{\mathcal{A},\prod}^{eav}(n)=1]\leq1/2+negl(n)$$ 换句话而言：for every PPT 敌手$\mathcal{A}$: $$|Pr[out\mathcal{A}(PrivK_{\mathcal{A},\prod}^{eav}(n,0))=1]-Pr[out_\mathcal{A}(PrivK_{\mathcal{A},\prod}^{eav}(n,1))=1]|\leq negl(n)$$
第一和第二的定义虽然等价，但敌手获胜的概率不可能小于1/2（乱猜也能1/2对吧），而第二种定义是绝对值式的定义，因此特地点明。
在上面的定义过程中，oracle实验只进行了单个密文的过程，敌手除了单个密文外没有得到任何的信息。
Plaintext length
发送密文的过程中，基本肯定会泄露的信息除了密文被发送这个行为本身外，还有一个看上去不太敏感的地方：明文长度。很多情况下，明文长度的泄露不会造成什么影响，但仍然存在着攻击手段。例如：
Crime attack：很多明文在加密前会进行压缩，假设有两条信息X,Y，拼接后的字符串为X||Y,若X与Y相像，压缩算法会将其压缩，长度缩小从而暴露X,Y的相关信息。
遇到这种情况，一般而言需要对消息填充至固定长度，但无法完全避免长度消息的泄露。
Semantic Security（语义安全）
在这之前，我们讨论的computational security notion建立在不可区分性（indistinguishability）上。在上一节的讨论中，明文长度的泄露不可避免。因此，我们希望除此之外不再泄露任何消息。
也因此有了 Semantic Security（语义安全） 以及其十分诡异的定义：
偷懒贴PPT
Definition Semantic Security
A private-key encryption scheme $Enc,Dec$ is semantical secure in the presence of an eavesdropper if for every PPT algorithm $\mathcal{A}$ there exists a PPT algorithm $\mathcal{A'}$ such that for any PPT algorithm $Samp$ and poly-time computable functions $f$ and $h$, the following is negligible: $$|Pr[\mathcal{A}(1^n,Enc_k(m),h(m))=f(m)]-Pr[\mathcal{A'}(1^n,|m|,h(m))=f(m)]|$$
其中的h(m)可以看作附加的信息以函数的方式展现；而f(m)可以看作进行验证所需的谓词（或者说行为）。
太绕了？所幸的是，有以下性质：
info
private-key encryption scheme 的不可区分性和语义安全是等价的，该性质对于任意的威胁模型都成立。
Pseudorandomness（伪随机性）
真随机数的生成开销巨大（虽然是可以生成的），密码学的伪随机性意味着：该生成分布无法有效的（也就是有限算力）和真随机分布相区分。
Definition: a Sequence of Pseudorandom Distributions
A sequence of distributions $\{Dist_n\}_{n\in N}$ where$\{Dist_n\}=l(n)$ for some polynomial $l$ is pseudorandom, if for every PPT distinguisher $\mathcal{D}$:
$$|Pr[\mathcal{D}(U_{l(n)})=1]-Pr[\mathcal{D}(Dist_n)=1]|\leq negl(n)$$
也因此，可以将其作为上述加密方案中的Gen，用于生成密钥：
Definition Pseudorandomness Generator(PRGs)
A (deterministic) poly-time algorithm $$G:\{0,1\}^n\rightarrow \{0,1\}^{l(n)}$$ is a pseudorandom generator if:
- (Expansion)$\forall n,l(n)>n$.
- (Pseudorandomness)$\{G(U_N)\}_{n \in N} $ is a sequence of pseudorandom distributions.
需要注意的是： PRG 的暴力破解方法具有以下被破解的优势：
$$|Pr[\mathcal{D}(U_{l(b)})=1]-Pr[\mathcal{D}(G(U_n))=1]|\geq 1-2^{n-l(n)}$$
虽然说PRG无法被有效的区分，但PRG的输出并不是uniform的。本质上，PRG可以看作从长度较小的uniform数据映射到长度较长的伪随机性密钥。
不做证明的：PRG存在当且仅当单向函数（暂时不做说明）存在。
Encryption where |$|\mathcal{M}|>>|\mathcal{K}|$|
基于 One-time pad，这里提出一个加密方案。
using PRG $G:\{0,1\}^n\rightarrow \{0,1\}^{l(n)}$
选择安全参数 $n\in N,\mathcal{K}=\{0,1\}^n,\mathcal{M}=\mathcal{C}=\{0,1\}^{l(n)}$
Gen(非$G$) 生成随机性密钥k：
$$Enc_k(m)=m\oplus G(k)$$
$$Dec_k( c )=c\oplus G(k)$$
于是有：
info
在上述的加密方案中，若Gen是本节定义的PRG，则该fixed-length private-key encryption scheme 在EAV下具有不可区分性。
Reduction（归约性证明）
归约的概念在计算机科学中十分重要。
其本质是对上述构造的加密方案进行证明，若要攻破其方案，必须要攻破其内置的已被证明安全性的模块。通过反证法即可证明构造的加密方案安全性。
而如何构建这种反证？既然我们将加密方案的安全性归约到了其底层构件的安全性，而如今我们所讨论过的证明安全性的方法只有预言机，那么答案呼之欲出：
构造一个敌手$\mathcal{A}$去攻破构建的加密方案。而攻破过程中，可以将通过一系列过程，将敌手输入转化为抽象的敌手$\mathcal{A’}$，其对底层的构件进行预言机实验，再将预言机输出转化后返回给$\mathcal{A}$.由于底层的构建已被证明安全性,那么便可以证明加密方案安全性。
需要注意的是模拟抽象敌手的过程。对于该归约过程而言，对敌手$\mathcal{A}$的唯一了解就是他期望与预言机进行挑战，那么归约过程必须模拟地和预言机行为一致。
具体而言还有许多算式，但这里略了。懒。
本节实际上是对上节的warning进行证明，但由于其重要性单开一节，又因为懒了所以等之后有空了写博客里头。
本质上这份博客还是一份复习的，但写博客耗费的时间超出了我的预期。之后要尽可能简略写了。
Stronger security notions(CPA Security)
之前讨论的都为单消息的加密过程，这里开始讨论选择明文攻击，即可以选择多个明文，得到对应的密文（都是用单个密钥加密）来试图获得相关信息，而选择明文攻击又可以分为适应性和非适应性攻击。
非适应性CPA：在上述的预言机实验中，敌手第一步选择了一对明文进行实验；而这里的CPA则是在第一步将选择多个明文，和这一对明文同时发出，并获得用相同密钥加密的密文回应。敌手获得了多余的信息，并仍然对选定的一对明文进行甄别。
适应性CPA：无需在意多个明文的选择是否需要在第一步就全部完成。敌手可以根据上一次的回应而改变下一次发送的明文，从而获得更多的信息，敌手的能力也因此较非适应性CPA增强。适应性攻击可以在发送选定的一对明文前进行发送/收到回应，也可以在之后进行发送/收到回应，且仍然需要对该选定的明文进行甄别。
需要注意的是，两种CPA发送的多余明文，其长度都必须和选定的一对明文长度一致。
这里还有一个Left-or-right Security，不做多余介绍。
Definition
Private-key encryption scheme Π has indistinguishable multiple encryptions under a chosen-plaintext attack, or is CPA-secure for multiple encryptions, if for all probabilistic polynomial-time adversary A there is a negligible function negl such that $$Pr[PrivK_{\mathcal{A},\prod}^{LR-cpa}(n)=1]\leq 1/2+negl(n)$$ where the probability is taken over the randomness used by A and the randomness used in the experiment.
info
Any private-key encryption scheme that is CPA-secure is also a CPA-secure for multiple encryptions.
