[笔记]计算安全

1. Computational Security

回顾一下之前的perfect secrecy，在一个perfect secrecy体系中，任何的攻击者从密文里完全获取不到任何关于明文的信息，即使他有无穷的算力。

Perfect secrecy requires that absolutely no information about an encrypted message is leaked, even to an eavedropper with unlimited computational power.

相对于perfect secrecy而言，computational security 显得稍微弱一点(weaker but still meaningful)，下面介绍它的定义：

1. Security is only guaranteed against efficient adversaries that run for some feasible amount of time.
2. Adversaries can potentially succeed with some very small probability.

那么何为efficient，何为very small probability?
可以从concrete approach和asymptotic approach两种不同角度来分析。

---

2. The Concrete Approach

具体的方法就是拿出一个具体的数据来说话。直接引用书中的原话：

A scheme is $(t,\epsilon)$-secure if any adversary running for time at most $t$ succeeds in breaking the scheme with probability at most $\epsilon$.

从这个角度看的话，$t$ 就是代表着efficient，$\epsilon$ 代表着very small probability。

---

3. The Asymptotic Approach

上面所说的太笼统，对于具体的问题不能很方便地表述。Asymptotic approach介绍了一种整数参数(integer-valued security parameter) $n$ ，通过调节这个参数，可以使得整个体系达到安全的定义。

1. We equate “efficient adversaries” with randomized algorithms running in time polynomial in $n$.
2. We equate the notion of “small probabilities of success” with success probabilities smaller than any inverse polynomial in $n$ (aka negligible).

因此efficient和very small probability都用一个参数 $n$搞定了，具体地，可以将安全(secure)定义如下：

A scheme is secure if for every PPT (probabilistic polynomial-time) adversary $\mathcal{A}$ carrying out an attack of some formally specified type, and for every positive polynomial p, there exists an integer N such that when $n \gt N$ the probability that $\mathcal{A}$ succeeds in the attack is less than $1/p(n)$.