《Introduction to security reduction》区分性困难假设下的加密方案安全证明内容小结

柔光的暖阳◎ 2022-11-30 12:46 136阅读 0赞

## 《Introduction to security reduction》 区分性困难假设下的加密方案安全证明  内容小结 ##

密码学可证明安全推荐书目（系列博客内容为这两本书学习笔记与内容小结):

《密码学中的可证明安全性》杨波 ：清华大学出版社

《Introduction to Security Reduction》Fuchun Guo;Willy Susilo;Yi Mu ：Springer

### 安全规约组织结构 ###

模拟阶段：模拟者将困难问题放入挑战密文当中，并且模拟者在整个规约过程中，不能中断。

解决问题阶段：模拟者使用敌手的猜测结果c解决区分性困难假设问题。

分析阶段：对于整个规约过程的相关概率分析，包括模拟不中断概率，攻破正确挑战密文概率，攻破错误挑战密文概率，敌手优势与攻击时间消耗等等。

### 密文的分类 ###

正确密文：依照加密算法能够得到的密文。

错误密文：不能依照加密算法得到的密文，与正确的密文相比，错误密文往往是结构上的臆造。

非法密文：解密谕言机无法解密，直接输出终止符号。

正确/错误密文关注的是密文的生成结构是否能够由加密算法正常计算得到，合法/非法密文关注的是对应的解密谕言机是否能够正确的回应解密请求。

在规约算法中，必须对每种密文的解密请求都合理正确的返回相应结果，这样的设计是比较困难的，特别是对于挑战密文的处理，如果挑战密文是错误的密文，那么又当如何应对？下文对于挑战密文进行了分类，因为并非所有的挑战密文都是正确合法的密文，如果挑战密文是错误的，或者挑战密文包含的判定性元素是错误的，那么敌手是否能够依靠破解错误的密文达到攻破方案的效果？如果是这样，那么敌手总是可以在不攻破困难问题的情况下攻破加密方案，这将直接导致规约失败，所以在加密方案中，我们要对不同种类的密文请求做对应的回复设计才能将敌手的攻击尽可能限制在对潜在困难问题的攻击上。

### 挑战密文分类 ###

正确的挑战密文：当挑战密文的挑战元素是正确的，挑战密文也是正确的。

![20200824215438816.png][]

敌手将会正确的猜测挑战密文的明文，以不可忽略的优势，因为这里我们假设敌手是具有无限计算能力的。

错误的挑战密文：生成挑战密文的挑战元素是错误的，那么挑战密文就是错误的。

![20200824215416663.png][]

敌手将不能正确的猜测挑战密文的明文，除非以一种可忽略的概率，也就是说，在敌手在面对错误的密文时，敌手不具有额外的优势猜测挑战密文。例如，正确的挑战密文和错误的挑战密文是一次一密相当的，那么敌手实质上也没有什么额外的优势解密，错误的挑战密文也不能帮助敌手攻破方案。

独立的挑战密文：如果挑战密文和苦难问题没关系，那么规约是直接失败的，因为无法将敌手的攻击归约到困难问题上。

### 敌手优势的概率描述 ###

解决困难问题的宏观概率描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

模拟成功/失败的概率描述：

![20200824215617934.png][]

![20200824215637626.png][]

解决困难问题的进一步概率描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

解决困难问题的最终概率描述：

![20200824215846603.png][]

由上式子可知，敌手的优势只与模拟成功的概率，敌手能攻破正确挑战密文的概率，敌手能攻破错误挑战敏文的概率。这三个概率有关，模拟成功的概率是非常明确的，即为不中断，敌手不可区分的概率，敌手能攻破正确密文的概率也是明确的，敌手能够攻破错误密文的概率尚且还没有讨论。

### 敌手攻破正确/错误挑战密文的概率描述 ###

敌手攻破正确挑战密文的概率描述：

![20200824215915756.png][]                         ![20200824220021852.png][]

敌手攻破错误挑战密文的概率描述：

![20200824220042606.png][]

如果生成挑战密文的困难问题元素是错误的，那么敌手的挑战密文也就是错误的，这样的密文如果能够解密，那么最终的解密明文也不会是m0,m1中的任意一个。对于敌手而言，将毫不费力的知道与他交互的协议是一个模拟协议，而不是一个真实的协议，那么规约直接失败，由于敌手是恶意的敌手，所以敌手并不会“声张”他发现了端倪，而是将会尽一切可能去猜测正确的结果，进一步导致规约成功的概率为0，可怜的模拟者最终得到了一个失败的规约，可能还美滋滋的认为自己的规约算法是正确的。

### 敌手的优势进一步描述 ###

接着上文的分析，我们进一步得到敌手不可忽略的优势描述如下：

![20200824220153899.png][]

可见，当敌手攻破错误明文的概率约等于二分之一时，敌手攻击方案的概率将是不可忽略的，不失一般性的，我们发现当模拟成功的概率为1，优势为1，攻击错误密文的概率为二分之一时，敌手优势的最大概率为二分之一，这是符合我们预期的，因为敌手有可能得到错误的密文，但是敌手依然还有有二分之一的概率可以猜中。

### 一次一密 ###

一次一密的定义：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

对于错误的挑战密文，我们要实现“从敌手的角度看，错误的挑战密文是对消息\{m0,m1\}做一次一密的。” 只有这样，才能保证敌手攻破错误挑战密文的概率是二分之一。

### 一次一密 对 方案安全性证明的影响 ###

我们必须证明攻破错误的挑战密文相当于攻破一次一密的困难性，也就是说，从敌手的角度看来，错误的挑战密文以及其收到的其他参数是一次一密的。当我们讨论错误挑战密文相关的内容时，一定要考虑到错误密文是否是一次一密的。

### 解密谕言机设计 ###

和挑战密文相关的还有一个重要的内容，就是解密谕言机的设计，当挑战元素是正确或者错误时，模拟者必须要保证敌手能够获得一个合理的解密结果。

当Z是正确时，解密谕言机需要接受正确的密文，拒绝错误的密文，这点和真实情况是一样的。一种方法是模拟者在解密时生成一个合法的秘钥。（我们知道，模拟者本身不应该掌握私钥）

当Z是错误时，我们需要证明敌手不能再解密询问的帮助下攻破错误密文，因为这种攻击是无用的，是不能破坏潜在困难问题的，但是，如何阻止敌手发动这样的攻击是安全规约中比较困难的地方。CCA安全模型下，敌手可以尝试使用挑战密文的延展性，然后使用解密询问来帮助自己攻破挑战密文，但是CCA2则可以避免这种情况。

### 解密秘钥 ###

在加密协议的安全规约中，模拟者并不是必须被设计成不知道挑战秘钥的。这里有两种不同的方式，考虑挑战秘钥。

第一种方法：模拟者知道挑战秘钥，解密询问直接使用解密秘钥模拟，但是，难点在于，对挑战密文的模拟，要求敌手以可以忽略的优势攻破错误的挑战密文。因为敌手将能够询问错误密文相关的密文，模拟者将会给与正确的解密，需要考虑错误密文对敌手的一次一密效果。

第二种方法：模拟者不知道挑战秘钥，如果Z是错误的，也就是说挑战密文是错误的，那么由于模拟者不掌握私钥，很容易做到错误的密文一次一密效果，但是，如何解密正确的密文不使用私钥将会成为一个问题。

这两种方法的选择依赖于被提出的协议与依赖的困难问题，这两个方法并不是通用的。

### 错误挑战密文的概率分析 ###

面对错误挑战密文时，我们至少要证明敌手攻破错误密文的概率是可以忽略的，不一定要证明一次一密。其中，主要包括以下的几个概率与优势需要考虑：

![20200824225004891.png][]

在CPA模型下，由于没有解密询问，则敌手攻破错误挑战密文的概率只有二分之一，如果有解密询问帮助，那么错误的挑战密文则可能会产生一定的帮助，所以CPA模型下，不需要继续考虑错误的挑战密文情况。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

在上文我们讨论过，模拟者可能具有秘钥，也可能不具有秘钥，这里的优势描述的就是这种情况，如果敌手能够借助秘钥的解密询问，则此项为1，否则为0。原因很简单，因为如果敌手在解密询问中不能借助真实的秘钥，那么无论敌手怎么询问，都不能获得任何的挑战密文相关信息，则无法使用密文延展性，故，不需要继续分析，否则还要继续分析。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5][]

进一步，敌手是或否能够询问解密错误密文，如果敌手能够询问解密错误密文则还要继续分析，因为敌手总是希望能够解密错误挑战密文的相关信息，所以总是想要修改错误挑战密文发动CCA2攻击，但是，如果模拟者对错误密文的询问不予理会，则敌手没有办法继续，否则还要继续分析。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6][]

这个概率描述的是模拟者能够接受错误密文解密的概率是可忽略的，或者说是敌手能够生成一个错误密文并被接受解密的概率。因为一旦敌手能够自己伪造密文并给模拟者解密，那么模拟者将要泄露太多的消息。敌手甚至可以直接区分是模拟协议还是真实协议。因为真实协议对于错误密文往往不能解密，直接终止。

最终形式化描述：

![20200824230204568.png][]

根据这几个概率分析，我们可以得到CPA  CCA模型下，错误挑战密文如何分析的流程图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7][]

### 安全模型的概率描述 ###

![20200824230707399.png][]

上式为全部的描述，对于CCA和CPA来看，有如下的分析：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 10][]

[20200824215438816.png]: /images/20221123/4e4cef0ba63e44caa5228675864c6f56.png
[20200824215416663.png]: /images/20221123/e89c01005f3f44519f55320927fd0105.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221123/ccdad7be7a864ffd98228e421739dae8.png
[20200824215617934.png]: /images/20221123/e539916e555745dc955797e3f1264d52.png
[20200824215637626.png]: /images/20221123/f322e81167134c1da9374587abc223df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221123/5e72e00680c844df8a30b4464a39b11a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221123/243abece80b848b59e2e617bb1cab3db.png
[20200824215846603.png]: /images/20221123/454d6e740e0f4f9c96baa7b75dd1ec0d.png
[20200824215915756.png]: https://img-blog.csdnimg.cn/20200824215915756.png
[20200824220021852.png]: /images/20221123/8cee116089004f00bcfe12593a367aaf.png
[20200824220042606.png]: /images/20221123/ebd7268b00a1492eba7105413bbb06f2.png
[20200824220153899.png]: /images/20221123/62de5d43d2b8439abf155cbe4758f0a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20221123/8677e493413f4614a983f7f8840eb3bf.png
[20200824225004891.png]: /images/20221123/757a2c36f8bf4880b4236429df407c39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20221123/58250f08981a419ea8b6530948ef526f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: /images/20221123/1410c368241f435683cb5e3927f3a1ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6]: /images/20221123/011f64cff1f94be29df465c0846bbd43.png
[20200824230204568.png]: /images/20221123/3d5cf1b1d065457bbf106da36b127655.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7]: /images/20221123/5bf8722df9bb41a0b4976d268bfb038e.png
[20200824230707399.png]: /images/20221123/e74ea9f236d54c388464bbcd11107237.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8]: /images/20221123/6edf1790b5e946c988fe83417bb822b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9]: /images/20221123/6f3f921ccc154e1bb7ef8e8c3d18a290.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 10]: /images/20221123/0aee00fc237c4e17817791577fc75c2a.png