基于身份的密码体制 BF IBE 2001 方案及安全性证明内容小结

亦凉 2022-11-29 00:56 201阅读 0赞

# 基于身份的密码体制 BF IBE 2001 方案及安全性证明 内容小结 #

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

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

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

### **IBE安全模型 与 普通安全模型的异同** ###

普通安全模型即为我们常说的CPA，CCA安全模型，针对普通的加密解密协议而言。IBE 基于身份的密码体制因为KGC的存在，增加了用户密钥生成阶段。这里的密钥并非由用户生成，而是由KGC生成用户私钥。所以，对KGC生成用户私钥的安全性需要纳入安全性考量。

KGC需要保证敌手不能获取主私钥，如果敌手获取主私钥，那么敌手可以为任意KGC管控的用户生成伪造私钥，则所有的相关用户密文信息将失去安全保证。

因此，在普通安全模型中增加一个“ID询问”，敌手可以伪装成普通用户向KGC发起私钥询问，从KGC的角度看来，这是合法的询问，所以将会把相关生成的ID私钥发送给敌手，只要敌手不能从这样的询问中获取关于主密钥的信息即可保证KGC安全性，根据是否允许敌手进行适应性询问与选定ID进行询问，敌手的攻击又被分为适应性攻击与选择ID攻击。

并且，需要相应的修改解密询问，敌手在进行解密询问时，需要同时指出指定的解密ID，即提交(ID,CT)。这里允许敌手对挑战身份进行解密询问，限制是：不能获得挑战身份私钥，不能询问挑战密文，只能获得挑战身份的非挑战密文解密结果。

### IBE CCA安全模型描述 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70][]

### BF01 方案描述 ###

证明思路：

在《密码学中的可证明安全性》一书中对BF01是这样证明的，首先构造一个非基于身份的方案BasicPub，然后将B01 方案规约到BasicPub方案上，接着证明BasicPub方案可以规约到BDH困难问题上，最终，根据规约的传递性，可以证明BF01方案可以归约到BDH假设上。

BDH假设：

已知< P , aP , bP , cP >,

需要计算e < P, P > ^abc.

方案到方案的规约：

方案到困难问题的规约，其实比较好解释，很多教材有详细的讲解。而方案到方案的规约则比较复杂。目前，除了论文外，我掌握的教材也就《密码学中的可证明安全性》中有相关描述。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1][]

图1  将方案B规约到方案A

方案到困难问题的规约指的是，将敌手对方案发起的攻击转化为解决一个困难问题。

方案到方案的规约，以上图1将方案B规约到方案A为例，敌手对于方案B的攻击被转化为对方案A的攻击，敌手不可区分他是在攻击方案A还是方案B，由于模拟者的存在为实现敌手的不可区分提供了可能，模拟者是可编程的一个算法，将敌手对方案B的攻击转化到对方案A的攻击上，并且这种模拟在本质上必须合理的，合法的。

BF01 方案描述

初始化阶段：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2][]

主私钥: s, 主公钥：Pub = sP。主私钥用来生成KGC实际控制用户的私钥，主公钥用来加密，其实想想也是很现实的，用户的私有由KGC使用主私钥生成，那么解密怎验证？只有在加密的时候把主公钥使用进来，才能在解密时，验证主私钥的真实性。

KGC秘钥生成阶段：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3][]

加密阶段：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4][]

gID 包含的就是收信方的公钥 和 主公钥，这是一种对身份与KGC的效验。

解密阶段：

![20200819181908223.png][]

正确性：

![20200819181949990.png][]

### BF01 CPA安全 ###

为了证明其CPA安全性，顺着《密码学中的可证明安全性》的证明思路，首先证明BF 01 可以规约到Basicpub方案上：

BasicPub 方案描述

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

![2020081919402893.png][]

这个方案和BF01的区别在于，这里没有设置KGC这个角色，用户的QID是随机取的元素。

证明BF01 可以规约到 Basicpub上：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7][]

详细证明过程在《密码学中的可证明安全性》有详细的说明。

这里我们主要讨论，在方案到方案的规约过程中，随机谕言机的应用。

模拟者在模拟BF01方案时，并不具备哈希函数H1（），所以建立一个可编程的随机谕言机列表，并设计如下的哈希询问：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8][]

![20200819215011845.png][]

这里有两点需要注意：

1.这里的coin 实际上是一种紧规约的设计构造，以猜测概率来实现紧规约。

2.模拟者B此处并不是随机选取一个元素，因为Basicpub 方案这里是随机选取的元素，而BF01方案这里是哈希函数计算得到，为了保证随机性与独立性，这里选择一个随机数bi 维持随机性与独立性。

3.最终规约的目的是，让敌手A攻击BF01的攻击能够转化为对BasicPub的攻击，所以当coin = 0 时，即为敌手发动挑战的时刻，我们给与谕言机的回复设定为biQID, 这是可规约的设置。而其他时候设定为biP, 这是可模拟的设置。

秘钥询问阶段：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9][]

这里需要注意的点有：根据哈希询问知道，只有敌手发起攻击时，QID的设置是BasicPub算法的，而其他时候给与的私钥是配套BasicPub的，即，当敌手不可区分时，敌手并不能分清是在攻击哪一个方案，攻击的可传递性下文介绍。

敌手挑战阶段（规约阶段）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 10][]

规约的不可区分性:

H-query 阶段：所有的回复都是随机数bi 乘以点值，敌手是不可区分的。

规约的中断性：

除非敌手询问挑战ID的私钥，否则不会中断。

规约的成功性：

在不中断模拟，且敌手不可区分真实协议与模拟协议，所以，规约是成功的。

敌手的优势：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 11][]

总结：

方案到方案的规约要点，一共两点：

1. 敌手不可区分真实还是模拟，保证规约的成功。

2. 模拟者能够建立起两个方案密文之间的联系。

BF01 规约到BDH假设

由上文的证明过程，我们现在只需证明basicpub 到BDH假设即可，这里是把加密方案规约到计算性困难问题上。

在随机谕言机下，只需要将困难问题放入哈希询问即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 12][]

### BF01  CCA安全 ###

为了实现BF01的CCA安全方案，《密码学中的可证明安全性》提及了一个方法，使用Fujisaki-Okamoto 定理。

该定理的描述及作用如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 13][]

CCA 安全的BF01方案描述

初始化阶段：

![20200819231831789.png][]

加密阶段：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 14][]

KGC秘钥生成阶段，与原方案相同。

解密阶段：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 15][]

宏观上，从解密阶段看起来为了避免CPA的挑战密文延展性导致CCA不安全，所有增加了一个验证步骤，保证这个消息值M只能通过随机值r诞生，不存在一个另外的密文能够通过这个U ！= rp 的验证，但是明文不同的情况。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70]: /images/20221124/14c9145ed7024cb4b403186da0626d7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 1]: /images/20221124/c34556de625d42fe8a73607cdefd072b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 2]: /images/20221124/acfcf9392a22464da14bb2dcabf2a5a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 3]: /images/20221124/a6e899ed461748229b320d2d742be9da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 4]: /images/20221124/897aa14fa5c74214984fa0827247b8dd.png
[20200819181908223.png]: /images/20221124/9f5cef63fe22470ab88d94a462f08f1d.png
[20200819181949990.png]: /images/20221124/f46190ad0cd7491c85a84dcef95898c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200819193849985.png?x-oss-process=image/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 6]: /images/20221124/cf264a91338341b6b4889d48c0f2f794.png
[2020081919402893.png]: /images/20221124/577e45ca6a814cf3815ba2be6c2b2dc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 7]: /images/20221124/bbdf10ac3f7842beb5d40ed3aca673f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 8]: /images/20221124/87a5385ae82b4c05a2ed1ba5725fdc05.png
[20200819215011845.png]: /images/20221124/3cca631446fa42e79b099ce1cfd10699.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 9]: /images/20221124/56d054a1791c44bbb583d4660a78463c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 10]: /images/20221124/97eee207e2754b188360ef86d694b190.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 11]: /images/20221124/ea009216dce0491ea2849405db87aa53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 12]: /images/20221124/edfb81a2c77344019de4b7050a3befe7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 13]: /images/20221124/a902a82e4698461b887ad6223cf46056.png
[20200819231831789.png]: /images/20221124/234b66ef60e64741aefd04505315d752.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 14]: /images/20221124/d786ac3d804447afac22240398ad99ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ptcmxpbnV4_size_16_color_FFFFFF_t_70 15]: /images/20221124/5886e0947438490381f6bce3c2c455fe.png