Boneh-Boyen Scheme 在标准模型下的安全性证明内容小结

浅浅的花香味﹌ 2022-11-29 11:50 154阅读 0赞

# Boneh-Boyen Scheme 在标准模型下的安全性证明  内容小结 #

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

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

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

标准模型有时也被描述为without oracle modle:

### Boneh-Boyen Scheme 协议描述 ###

系统初始化阶段：

![20200820120839390.png][]

秘钥生成阶段：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

签名阶段：

![2020082012110522.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][]

安全证明初步分析：

首先，在这个签名算法中，并没有使用哈希函数，对于每一个明文消息使用随机数 r 作为掩盖消息m的因子，并且要求对于每个消息M选用相同的随机数，则同一消息在秘钥对不变的情况下，生成的签名相同。签名形式类似于《ITSR》中提及的第“I”型。

不使用随机谕言机意味着，在规约算法设计中没有哈希询问，那么就不能采取将困难问题 放入哈希询问的方法。

那么在EUCMA的安全模型下，就只有签名询问这一种询问方式，多项式有界次询问后，敌手发起挑战伪造一个没有询问过消息的数字签名。但是，之前的随机谕言机模型要求规约算法此处必须为签名询问构造的签名构造成可模拟的，而敌手伪造的签名是可规约的。这里缺少了谕言机的帮助，该如何做？这就是标准模型和随机谕言机模型的区别。

安全定理：

![20200820211322597.png][]

q-SDH困难问题:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

嵌入困难问题思考，q-SDH问题，是一个计算性困难问题，输入的元素为多个关于a的指数元素，将这些元素做乘积运算，得到关于底数为g, 指数是a的多项式的元素。

规约参数设置：

![20200820214058711.png][]

注意这里h项往往这样设计，因为最终敌手是能拿到h的，所以这里h算是困难问题的实例，因为能分别掌握各个元素项数，也一定能掌握所有元素的乘积。

签名询问设置：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

显然这个签名设计的是可模拟的。

伪造签名设置：

![20200820214645610.png][]

这里对c是有要求的，c的取值将决定这个签名是可规约的还是可模拟的，如果c的值在之前询问中得到过，则整个签名就是可模拟的，因为敌手此时不需要发动能够潜在困难问题的攻击，依然能够得到合法的签名。

![20200820214928441.png][]

规约算法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5][]

存在一个问题：

如果说按照敌手进行QH次询问，那么上述的规约算法已经足够，无非是得到一个比较宽松的规约罢了，并且，如果存在这样的情况，C的值在之前请求得到过，因为C并非是签名请求，C的确有可能被请求过，这是一种合理的符合现实的猜测，是否还能模拟成功？

为了进一步实现规约损失L = 2的效果，我们做一个随机比特coin, 当coin = 1时，运行上面的规约算法，当coin = 0时，运行下面的规约算法：

规约参数设置2：

![20200820220810614.png][]

签名询问2：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6][]

伪造签名2：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8][]

由于可以解出a的值，那么也就能解出q-SDH问题。

规约算法2：

以上两种规约算法对于敌手来说是不可区分的，敌手并不能分辨模拟者是选用Coin为多少。但是不论模拟者选择哪一个规约算法，模拟者都以二分之一的概率可能发生中断。模拟成功的概率为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9][]

[20200820120839390.png]: /images/20221124/c33e5cd8ef924ce08dbb828bb8b68a5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221124/db5168f0377444a09768ac91be1984c5.png
[2020082012110522.png]: /images/20221124/3e766a79b2ee4a6dae32b0985e64ff46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221124/fc79ee0fddca4a149ecc885d55ecd9b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221124/a4eebfd32dff483c9276933abba56ba9.png
[20200820211322597.png]: /images/20221124/6511b40ca04a4d1f9faafea2b3210703.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20221124/0acee9484fec4d0f8bdbcf7a9cbaed13.png
[20200820214058711.png]: /images/20221124/b0093dd7a9774b4a8f4a98f74148d88d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20221124/2d19b390159249dbacb8a9ccf27f0f6d.png
[20200820214645610.png]: /images/20221124/b1c0061c78e54710a24ba61c3666c55f.png
[20200820214928441.png]: /images/20221124/10d49e4a61814a98adee4376dd6611de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: /images/20221124/25c4b92ed88c416a95e37b46431b6d93.png
[20200820220810614.png]: /images/20221124/d57bdad9d9ca46528ade707fef3ef6e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6]: /images/20221124/dc49bbce1d6a4ef2b1d69e6b43d7723b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7]: /images/20221124/918ff036fbe24e0fa2ba2d626439c75c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8]: /images/20221124/3019cae1747b4b5e84d53b2b2f3d058d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9]: /images/20221124/d27c92dd6eec4c43a29d0fab11f67cb8.png