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

本文主要是介绍《Introduction to security reduction》区分性困难假设下的加密方案安全证明内容小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

安全规约组织结构

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

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

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

密文的分类

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

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

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

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

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

挑战密文分类

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

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

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

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

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

敌手优势的概率描述

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

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

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

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

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

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

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

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

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

敌手的优势进一步描述

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

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

一次一密

一次一密的定义：

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

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

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

解密谕言机设计

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

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

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

解密秘钥

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

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

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

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

错误挑战密文的概率分析

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

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

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