BLS# with Random Oracle ；BLS 改进方案在随机谕言机下内容小结

向右看齐 2022-11-24 14:23 168阅读 0赞

# BLS\# with Random Oracle ;BLS 改进方案在随机谕言机下  内容小结 #

密码学安全规约推荐书目（系列博客内容为这两本书学习笔记与内容小结）:

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

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

## BLS\# 方案描述 ##

![20200806160552968.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

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

BLS\#方案和BLS、BLS+方案并不太大的区别，无非是在签名生成的过程中做出修改，这个方案与BLS+ 方案相比，是将随机盐替换成了一个随机数，并且要求这个随机数对于确定的消息是相同的。

这里需要使用这个随机数来构造一个紧规约的安全证明，在此之前，我们先考虑下BLS 和 BLS+ 方案的区别。

## BLS 方案 与 BLS+方案的区别 ##

BLS   方案是宽松规约的，规约损失为qH.

BLS+ 方案是紧规约的，规约损失为2.

BLS方案是通过将敌手发动有效攻击的时机确定为第qH次询问。而对这第qH次预选做了选择，那么敌手正好在这次发起攻击的概率就是1/qH. 但是，我们往往假设敌手是拥有无穷计算能力的，这个概率导致敌手难以密切，紧致，高概率的发起有效的能够解决潜困难问题。那么，也就是说我们安全方案规约到这个困难问题上的程度也就越浅。规约也就越宽松。

问题：能不能增大敌手发动解决困难问题的概率，如果敌手能够越大程度上发起解决困难问题攻击，那么规约也就越紧，最好是只要敌手发起攻击，就一定是可规约的签名，就一定能够解决困难问题？

答：紧规约是可能的，但是需要对方案进行巧妙的设计，从而产生出紧规约的安全性证明。

BLS+ 方案通过引入一个随机比特C，进入签名方案，从而构造出一种紧规约的方案与证明。其实这种做法是一种朴素且巧妙的方法。加入我们在敌手发起伪造时，主动给与一个发起成功有效攻击的概率，然后把这个概率降低，那么我们就能得到一个紧规约的方案与证明。

从直觉上看，如果想要实现这个目标，必须给敌手选择的机会，那么就需要敌手做出选择，而敌手单方面的选择是不够的，一旦敌手能够发现其中选择对应的可模拟签名，则一定会一直选择发起无用的攻击，那么规约将会失败。

所以，在密码方案与证明中，如果引入一个比特，即为一个选择的概率，那么，在证明中模拟者也一定要控制一个比特，以保证敌手的随机选择是有意义的。

如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

## BLS\# 方案的证明 ##

![2020080618055581.png][]

直觉上，从这个定理看出直接证明了，BLS\#方案的安全损失为L= 1. 这意味着没有损失，如果说没有安全损失，那么只有一种可能，敌手仿造时必定输出可规约的签名。模拟者在模拟协议时必定输出可模拟的签名。如何实现这个过程？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

直觉上，模拟者 敌手 谕言机三者 只有如上图这样交互，并且谕言机需要具备区分敌手和模拟者的能力，才能实现证明。但是随机谕言机往往是由模拟者控制的，但是模拟者是觉得无法假设具备区分敌手在某次发动有效攻击的。

正确的证明如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5][]

初始化阶段和其他BLS方案相同，没有任何的区别，重点是哈希询问请求与签名请求：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6][]

哈希请求：敌手发送一个（m,r）的请求给与谕言机，如果这个请求早都存在列表上了，那么模拟者就按照列表的内容回复。否则，模拟者选择随机的Z，回复一个可构成可规约签名的请求内容返回。不同的是，这里的哈希列表的表项包含此条目是由谁生成的，如果之前并不存在，则由敌手询问生成。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7][]

签名请求：敌手请求一个消息的签名，如果存在由模拟者生成的哈希请求，则模拟者使用条目回答，否则模拟者随机选择参数r,y生成一个条目，并且回复敌手。如果这条消息曾被敌手生成过，则模拟器终止。那么这里相当于强制要求敌手，只有访问签名询问得到的为可模拟的签名，如果是敌手之前做过的（m,r）哈希询问，那么终止。这是符合现实与逻辑的，这里的签名随机数r是模拟者（签名算法）随机选择生成的，敌手本身既不应该知道这个随机的数值，如果敌手知道这个随机数，那么敌手将会总是发起无用的攻击，因为敌手可以像模拟者那样输出可模拟的签名。这里是让要求两种访问的随机值不能出现相同的情况，如果哈希询问的随机值r 和 签名询问的随机值r 相同，那么敌手可以立即发现签名时刻模拟的，从而区分出与敌手交互的是模拟的协议还是真实的协议。所以，可见随机谕言机的本质是一个允许敌手任何时候访问的可编程机器，保证输出独立随机不能被敌手区分出模拟与真实的差别。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8][]

敌手伪造：伪造签名时，敌手必须访问随机谕言机，所以得到一定是一个可规约的签名。

模拟不可区分性：

容易看出，a,b,z,y,r 是独立随机的，是不可区分的。所以不能区分是模拟还是真实的攻击。

成功解决困难问题的概率分析：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9][]

规约失败的概率仅仅为敌手询问时猜测到了模拟者选择的随机数，概率等于![Pr = \\frac\{qH\}\{p\}][Pr _ _frac_qH_p]，而这个概率是非常小的。敌手猜测不中的概率是![1-Pr][].因此，当经过qs次询问后，成功模拟且敌手发动有效攻击的概率约等于1。

[20200806160552968.png]: /images/20221124/b88d9df37c0e4ca195d0d8bf6169b46b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221124/e7e0b1779f8a4779ae88934d534ecf6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221124/88953adaac384807af1214ad0cb13e00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221124/f716b5c77ada484da94e8a45ead6a6e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20221124/4edae0c59b1849ae9c477e2a61d58364.png
[2020080618055581.png]: /images/20221124/02f7768824934508925f265bfd753fc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20221124/088036e4e0054bcb9a6861ed8c7e13ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: /images/20221124/195f74205cb240e5bd5121674728d5fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 6]: /images/20221124/beb8dc8d0ec74e5eb2944550276257ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7]: /images/20221124/e93909166827462fa4c4653723a0a9b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8]: /images/20221124/697b864beb5b485e80d1b7d37f9b9c44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9]: /images/20221124/98e55a5ccf7b493ca0dff518432c6c72.png
[Pr _ _frac_qH_p]: https://private.codecogs.com/gif.latex?Pr%20%3D%20%5Cfrac%7BqH%7D%7Bp%7D
[1-Pr]: https://private.codecogs.com/gif.latex?1-Pr