Principles of Modern Cryptography
Formal Definitions(正式的定义)
If you don’t understand what you want to achieve, how can you possibly know when (or if) you have achieved it?
如果你不知道你想要的做到怎样,那你怎么知道你做到了没有
what security guarantees are desired(要达到怎样的安全)
No recover the key (不能恢复出密钥)
No recover any character the plaintext(不能恢复出明文)
No recover any character of the plaintext(不能恢复出明文的任意字符)
in total,no additional information(总的来说没有额外的信息)what threats are in scope(什么样的威胁是在范围内的)
Ciphertext-only attack(唯密文攻击)
known-plaintext attack(已知明文攻击)
chosen-ciphertext attack(选择密文攻击)
chosen-plaintext attack(选择明文攻击)
Computational Security(计算安全)
Perfect secrecy requires that absolutely no information about an encrypted message is leaked, even to an eavesdropper with unlimited computational power.
完全保密要求不能有任何信息关于一个已加密的信息被泄露,尽管窃听者有无尽的计算资源
- Some Definitions
PPT:Probabilistic Polynomial Time in n(概率多项式时间)
negligible:smaller than any inverse polynomial in n(小于任何反多项式)
A scheme is computationally secure if any PPT adversary succeeds in breaking the scheme with at most negligible probability.
一个方案在计算上是安全的,如果任何概率多项式时间内的对手成功地以几乎可以忽略的概率破坏该方案。
- Definition 3.4
- Proposition 3.6
consider known-plaintext attack:c1,c2,…,cl correspond to m1,m2,…,ml
Exhausive-search attack(穷举攻击)
Time complexity: linear in |K|(linear线性的)
Successive probability: 1Random guessing(猜解)
Time complexity:O(1)
Successive probability:1/|K|
Syntax of Private-Key Encryption
- 解释:
Gen(1**n)密钥生成器生成密钥k
EncK(m)加密器使用密钥k和信息m生成密文c
Deck(c)解密器使用密文c和密钥k解密出密文m
要求对于任何k生成自Gen(1**n)以及任何m取自{0,1}比特串流,都有Deck(Enck(m))=m成立(说人话就是你自己加密的东西要自己完全恢复出来:))
Basic Defination:security against a ciphertext-only attack(针对唯密文攻击的安全性)
Adversary’s capabilities: eavesdropping adversary running in PPT(窃听者对手的能力是在概率多项式时间内的)
Security goal: unable to learn any partial information(安全目标:不能获得任意部分信息关于明文)
总结:
- PPT adversary (PPT时间内)
- advantage is negligibly better than 1/2(优势略胜于1/2)
Adversarial indistinguishability experiment PrivK
其中n表示一元的安全参数,π=(Gen,Enc,Dec)表示一个密钥加密模式
negl(n)表示将n带入后的可忽略的函数
当上式成立时,称这个π加密模式对窃听者来说具有不可区分性(indistinguishable)或者称为EAV-secure
下图是实验的模型:
An Equivalent Formulation(等效公式)
前面式子的变形,重要!
选定b的实验