密码学可证明安全CCA1

蔚落 2023-03-05 08:29 48阅读 0赞

## 密码学可证明安全CCA1 ##

安全规约推荐书目:

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

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

首先，关于密码学中的可证明安全放一张老图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

证明方法大类是两种：基于游戏的证明，基于模拟的证明；

基于游戏的证明又分为 安全规约，游戏跳跃。

安全规约部分在这本书中有比较详细的描述：

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

CCA1 安全方案及证明 在《密码学中的可证明安全性》有一个较好的游戏跳跃的例子如下：

## Noar-Yung CCA方案 ##

方案描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

证明：

安全定理描述如下：

![20200804172052696.png][]

证明思路：

按照CCA安全模型，有以下的两个实验即为敌手输出两个等长消息m0,m1 模拟者随机选择加密，敌手不可区分，这里分别独立出这两个实验路径如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

如果能证明这两个实验不可区分，那么就能证明这个方案是CCA安全的。实验的不可区分这里是使用一个一个不可区分游戏传递的。通过将逐步的修改实验1的参数，生成一个一个游戏，然后逐步证明这些游戏不可区分，最终就能证明这两个游戏不可区分。与安全规约不同的是，安全规约这里一般直接将区分方案规约到敌手拥有解决某个困难问题的能力上来。

《可证明安全性》对这两个实验不可区分证明动机描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

7个游戏主要特点如下：

![20200804174337700.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

最终证明的图示如下：

![20200804174918896.png][]

1. Exp0与 Exp1 不可区分：由于零知识证明的零知识性可得。

2. Exp1 与 Exp2 不可区分：对于敌手而言，这相当于区分CT1是M1的密文还是M0的密文，由该方案的CPA安全，可得不可区分，并且此处不需要解密CT1。

3. Exp2 与 Exp3 不可区分：如果敌手能伪造一个不同明文的合法挑战密文，则就可以区分这个两个实验，因为解密结果会变得不同，但是由于零知识系统的可靠性，敌手不能伪造出整个证明，所以不可能发生敌手使用不同秘钥鉴别出区别的情况，所以不可区分。如果对应明文相同,那么CT0.CT1 用任意秘钥解出内容没有差别。

4 Exp3与Exp4 不可区分：由于加密方案的CPA安全，所以不可区分。

5.Exp4与Exp5 不可区分：与第三项实验2 与3 的不可区分原因相同。

6.Exp5 与 Exp6 不可区分：与第一项实验0与实验1的不可区分原因相同。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20230208/8a7deda44b394e0db77bf489b2f10ee6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20230208/e964a56ce2ac4135b9240a07ffaa1ac7.png
[20200804172052696.png]: /images/20230208/38d3b85f08634c56a6793194990d69d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20230208/4ddd5b763a8044f79b98dc5fcb6a4226.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20230208/7104ee1b42a3468fbd5d2ae3d141661d.png
[20200804174337700.png]: /images/20230208/97c9e4cd7804408c90a77654a942b8f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20230208/98fc441a919a4c5c8c08a4f396f0564b.png
[20200804174918896.png]: /images/20230208/d0fdd1b086734a8fa75e964f233658e1.png