Introduction to Modern Cryptography Reading Notes
3 Private-Key Encryption
具体安全和渐进安全
安全有两种定义，具体的(concrete)和渐进的(asymasymptotic)。简单地说，具体安全依靠具体的数值，而渐进安全依靠关于 \(n\) 的函数。
对于具体安全的定义
A scheme is \((t, \varepsilon)\)-secure if any adversary running for time at most \(t\) succeeds in breaking the scheme with probability at most \(\varepsilon\).
在实际运用密码系统时往往需要一个具体的安全保障。
我们将 efficient adversaries 视为多项式时间随机算法(randomized algorithms running in time polynomial in \(n\))；将 small probabilities of success 视为不大于某一多项式的倒数(success probabilities smaller than any inverse polynomial in \(n\))，这样的概率成为可忽略的(negligible)。
PPT 表示 probabilistic polynomial-time。
对渐进安全进行定义：