Cramer-Shoup 密码系统安全证明内容小结

Love The Way You Lie 2022-11-26 12:56 231阅读 0赞

# **Cramer-Shoup 密码系统** #

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

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

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

## Cramer-Shoup 方案描述 ##

**Setup**：

存在大素数群G，模素数为q，g1,g2 为群的生成元，明文消息为群G的元素，使用哈希函数将任意长度的字符映射到群中的元素。需要注意的是：这里的明文消息不是任意的字符串，而必须是群G上的元素，这就限制了该方案的灵活性，因为需要其他的辅助编码或者明文约定。

**Keygen:**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

**Enc：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

**Dec:**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

## **Cramer-Shoup的安全性证明** ##

1.  CPA安全性

由方案可知，Cramer-Shoup方案加密是变相的EIGameal 加密方案，而EIGameal 方案是IND-CPA安全的，那么可得Cramer-Shoup 也是IND-CPA安全的。

2.  CCA安全性

由方案可知，Cramer-Shoup方案中的u2,v 这两个参数，实际上是用于数据的完整性检验，在之前学习CCA安全时，一个最为根本的问题就是如何消除密文的延展性，可以使用一次性签名保证密文的唯一与不可伪造有效性。这里用这个参数来保证密文的唯一性与不可伪造有效性。也就是说，敌手获得挑战密文后，难以伪造出与明文相关的密文，从而发动有效的攻击。所以，这个方案具备CCA2安全性。

3. 证明过程

定理声明：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

IND-CCA游戏描述如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

安全证明的本质是，如果敌手能够赢得这个游戏，那么敌手就能攻破这个方案。敌手攻破的这个方案，意味着敌手能够解决潜在的困难问题，这里的困难问题是DDH假设。但是同时，需要考虑另外的问题，解密预言机在回答敌手询问的时候，针对敌手发送的无效密文如何处理？如果预言机给敌手解密了无效的密文。敌手会不会获得相应的信息？那么敌手可能会计算无效的密文，发起主动的攻击。所以模拟者不能给与敌手无效密文回复。

这里，其实还有一个问题需要解决，就说敌手获得模拟者给与的挑战密文到底是不是正确的，如果不正确，那么意味着敌手不论有没有攻击能力都有二分之一的概率可以猜中，这是合理的。但是需要证明，敌手破解错误密文的概率与一次一密相同。才能支持上边的断言，即是是错误的挑战密文敌手也并不会具备多余的优势。

回到这个方案，敌手的成功概率描述如下：

![20200812182558506.png][]

![2020081218362625.png][]

断言3-5 意味着模拟者 模拟的协议是成功的，模拟成功是安全规约的第一步。

![20200812184126705.png][]

断言3-6 意味着如果是输出是随机的，那么敌手就会面临DDH困难问题，这要求敌手必须发起能够解决潜在困难问题的攻击。

![20200812184419916.png][]

断言3-6\` 意味着当输出四元组是随机四元组时，模拟者以不可区分概率决绝无效密文，为什么呢？无效密文其实是敌手发起的无用的攻击方式，为了安全规约成功，我们必须将敌手逼迫到尽可能发起有用攻击的地步。所以需要尽可能的拒绝无效密文。

![20200812185630800.png][]

断言3-6\`\` 意味着如果能够拒绝敌手给出的无效密文，则敌手的优势是可以忽略的，主要使用了绝对困难问题隐藏了z1,z2信息。敌手依然不能从挑战密文中获取到私钥的信息，不能发起有效的攻击。

综上所述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5][]

证明完毕。

断言的细节，在《密码学中的可证明安全性》有详细描述。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221124/69d42d750dcf415987287c6a03131985.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221124/d680a5f3ac124269b39d25f5a173338e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221124/d2fe5ee5531940689fac82e4ae5b6d35.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20221124/499e81456b72456d92dbc54479ea08e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20221124/f83579ef6fac4e76b2b5ab97dcfb8cb4.png
[20200812182558506.png]: /images/20221124/358e62b44b08427e89d00fdaff66bcee.png
[2020081218362625.png]: /images/20221124/190cd21aa38342a29b006a1781f3c2d6.png
[20200812184126705.png]: /images/20221124/04ed5a4f8a1d445fae4273aa70a6efac.png
[20200812184419916.png]: /images/20221124/ea131c09d25a4ec793fb52d069b823f9.png
[20200812185630800.png]: /images/20221124/4471a0967fc542bba13c57e188000354.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: /images/20221124/a9d481ad9cd8448b9095de23fa41e9d4.png