可证明安全的目标是为“一个方案是安全的”提供数学上的保证。
- 完美安全一般用概率上的知识来进行证明,一次一密为完美安全。
- 计算安全比完美安全稍弱,一般考虑PPT(概率多项式时间)能力的敌手,可以通过两种方式进行证明:Simulation-Based Approach、Game-Based Approach.
Simulation-Based Approach(后续可能会再写一篇详细介绍)
思想:用理想模型模拟现实模型,而无法区分出两种模型,从而证明现实模型是安全的。
Game-Based Approach
如果没有敌手能实现其目标则证明该协议是安全的。
过程为:
- 描述协议
- 描述敌手的目标(越低则方案越安全)
- 描述敌手的能力(越强则方案越安全)
- 构造安全模型(利用困难问题构造)
- 归约证明(归约到困难问题不可解上)
图:困难问题构造实例P,整合到Simulator中,Simulator伪装成Oracle来回答Attacher的问题,如果Attacher攻击成功,得到了所需的output,则归约出Simulator解决了困难问题的实例P。(但困难问题不可解,则Attacher不可能攻击成功,则方案是安全的)
- 安全模型中:Oracle
- 归约证明中:Simulator(相比于Oracle,少了私钥等)
Game-based Approach的两个例子
1、RSA签名
敌手的目标:
Total Break(完全攻破:如获得私钥)
Universal Forgery(可以对任意签名进行伪造)
Selective Forgery(可以对有选择性的签名进行伪造)
Existential Forgery(只能对存在过的签名进行伪造)
Strong Existential Forgery
敌手的能力:
No Message
Known Message
Generic Chosen Message
Directed Chosen Message
Adaptive Chosen Message(可以自适应的选择知道某些信息)
2、RSA加密
敌手的目标:
Total Break
Decrypting a given Ciphertext
Obtaining useful information from Ciphertext
敌手的能力:
Key Only Attack
Chosen Plaintext(CPA:选择明文攻击)
Generic Chosen Ciphertext(CCA:一般的选择密文攻击)
Adaptive Chosen Ciphertext 1(自适应的选择密文攻击1:有pre-challenge、challenge)
Adaptive Chosen Ciphertext 2(自适应的选择密文攻击2:有pre-challenge、challenge、post-challenge)