可证明安全An Introduction to Provable Security

时间:2024-05-23 19:38:14

可证明安全的目标是为“一个方案是安全的”提供数学上的保证。

  • 完美安全一般用概率上的知识来进行证明,一次一密为完美安全。
  • 计算安全比完美安全稍弱,一般考虑PPT(概率多项式时间)能力的敌手,可以通过两种方式进行证明:Simulation-Based Approach、Game-Based Approach.

Simulation-Based Approach(后续可能会再写一篇详细介绍)

思想:用理想模型模拟现实模型,而无法区分出两种模型,从而证明现实模型是安全的。

可证明安全An Introduction to Provable Security

 

Game-Based Approach

如果没有敌手能实现其目标则证明该协议是安全的。

过程为:

  • 描述协议
  • 描述敌手的目标(越低则方案越安全)
  • 描述敌手的能力(越强则方案越安全)
  • 构造安全模型(利用困难问题构造)
  • 归约证明(归约到困难问题不可解上)

可证明安全An Introduction to Provable Security

图:困难问题构造实例P,整合到Simulator中,Simulator伪装成Oracle来回答Attacher的问题,如果Attacher攻击成功,得到了所需的output,则归约出Simulator解决了困难问题的实例P。(但困难问题不可解,则Attacher不可能攻击成功,则方案是安全的)

可证明安全An Introduction to Provable Security

可证明安全An Introduction to Provable Security

 

  • 安全模型中: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)