@RunZhi 2017-03-28T14:30:09.000000Z 字数 10292 阅读 1244

IBE阅读1

IBE 密码学 阅读

过去一个月，我在导师的指导下，精读了十篇关于IBE(Identity-based encryption)的论文。重在掌握其中的思想，证明方法及其发展历程。

IBE简介

Shamir在1984年提出了把任意串当做公钥的公钥加密(PKE)方案。这样一个方案包含四个算法：
1. setup：生成全局的公共参数params和一个master-key(mk)
2. extract：使用mk生成一个密钥(sk)，这个密钥对应于这个算法的输入ID $(\in \{0,1\}^*)$
3. encrypt：用公钥 $\text{ID} \in \{0,1\}^*$ 对明文m进行加密
4. decrypt:用相应的私钥对密文进行解密。

Shamir提出这样一个PKE scheme的最初动机是简化邮件系统的证书管理。比如，当Alice想要发email给Bob的时候，他只要得到Bob的邮箱(Bob@company.com)，然后用这个邮箱字符串作为公钥对所发的邮件进行加密。注意此时Alice并不需要得到Bob的公钥及对应的证书，而在传统PKE下，我们是需要关于Bob公钥的证书的。Bob受到邮件后，他和一个称为Private Key Generator(私钥生成器?简称PKG)的第三方进行通信。Bob向PKG认证自己的身份（和Bob向CA证实自己身份的方法类似），然后从PKG那里得到对应于它邮箱（公钥）的私钥，最后解密。

而扩展开来，Shamir所提出的这样一个PKE scheme不仅仅可以用在email中，还可以用在普通的通信中。然而，从1984开始到2000年，一直没有具有可靠安全性的IBE scheme提出来。这个open problem持续了16年之久，不过有趣的是，具有类似概念的Identity-based Signature（也是由Shamir提出）却有了不少好的成果。在2001年，Boneh和Franklin[BFIBE]发表了第一个具有高安全性并且更具有实用价值的IBE scheme。之前的IBE scheme具有各种限制，而BF的成果避免了这些局限。这篇成果发表在美密2001(Crypto 2001)。

安全模型

BFIBE提出了第一个在Random Oracle(RO)下抗CCA（选择密文攻击）安全的IBE。IBE的语义安全和抗CCA类似于原有的PKE安全模型。IND-ID-CCA的攻击定义简述如下：

首先，挑战者根据安全参数运行Setup，并且给予公共参数给攻击者Adv，游戏进入阶段1(Phase I)。

在Phase I，攻击者可以向Challenger发起query。query包括两种：

Extract query(ID):挑战者生成ID对应的密钥返回给攻击者。

Decryption query(ID,C):挑战者根据ID生成对应密钥，然后用该密钥对C进行解密(可能会解出"乱码")并把结果返回给A.

Challenge阶段：攻击者发送两个明文 $M_0,M_1$ 和一个公钥ID给挑战者，挑战者随机选取其中一个明文 $(b \in_\text{uniform} \{0,1\})$ 进行加密并且发回给攻击者。

Phase II:攻击者继续进行Extract query和Decryption query，但是不能对challenge的ID进行Ext query，也不能对challenge ID和challenge密文进行Dec query.

攻击者返回一个bit b'。如果 $b' == b$ 则攻击者胜出。

攻击者的优势定义为: $\text{Adv}_\mathcal{A}(k) := |Pr[b=b']-\frac{1}{2}|$ 。
语义安全类似，但攻击者不能进行Dec query。语义安全在IBE中又被称为fully security.

IBE 与 Bilinear map

从BFIBE开始，大部分的IBE scheme构造都是基于pairing(Bilinear map)的。

Bilinear map

设 $G_1,G_2$ 为两个阶为q（大素数）的群，定义双线性映射 $\hat{e}:G_1 \times G_1 \to G_2$ . $\hat{e}$ 必须满足如下性质：

Bilinear(双线性): $\hat{e}(aP,bP)=\hat{e}(P,Q)^{ab}$ 对于所有 $P,Q \in G_1$ 和所有 $a,b, \in Z$ 成立。

Non-degenerate（非退化性？）:该映射不会把任意的来自 $G_1 \times G_1$ 的对映射到 $G_2$ 的单位元上。（注意，如果map始终把所有的对映射到单位元上，那么它肯定满足Bilinear属性但没有意义。另外，由素数阶群的特性，若 $P$ 是 $G_1$ 的生成元，那么 $\hat{e}(P,P)$ 是 $G_2$ 的生成元。）

computable(可计算性)：存在算法可以高效计算 $\hat{e}(P,Q)$ ，对于任意 $P,Q \in G_1$

Bilinear Diffie-Hellman Problem

类似于normal的DH问题，可以定义关于Bilinear map的DH问题。问题简述如下：给定攻击者 $(P,aP,bP,cP)$ ，要求计算 $\hat{e}(P,P)^{abc}$ 。BDH假设则是：不存在PPT（概率多项式时间）攻击者以可忽略概率解决以上问题。

Bilinear map在IBE中的直观

在PKE的setting下，所有的确定性加密都是不安全的（不抗选择明文攻击）。也就是说，PKE的加密算法必然是随机化的，并且把其中的随机性嵌在密文当中。一个很显然的例子就是ElGamal加密：

随机性 $y$ 被嵌在密文的 $c_0$ 部分。而 $h^y$ （盲化因子）起的作用就是对明文m进行盲化。而在解密算法中，通过 $c_0$ 和sk计算出盲化因子，从而能够进行解密。

而在IBE中，由于还需要有Extract（有些地方又称为KeyGen）算法，并且在攻击模型中，攻击者是可以访问Extract Oracle的。因此,Extract Oracle必须也是随机化的，因此Extract算法必然也是个概率算法。在产生的sk中嵌入相应的随机性。

IBE的解密算法需要以私钥sk和密文C作为输入。两个输入都是带有对应的随机性（并且相互独立）的，c中的盲化因子无法直接由sk计算出来。而通过借助Bilinear map的Bilinear属性，把密文和sk所带有的随机性“转移”到一起，然后通过sk中所带有的mk的信息，把相应的盲化因子计算出来，从而达到了解密的功能。

一个问题是：Bilinear map的计算是不小的开销。因此也有一些文章提出了without blinear map的IBE构造，如[BGH07]（基于QR假设），但这方面的工作较少。

HIBE

Hierarchical IBE比前面提到的IBE多了一个算法：Derive.它以一个未分配私钥的 $\text{ID}^+$ ，和一个ID向量 $\vec{\text{ID}}$ （包含多个ID）及其对应的私钥向量作为输入，输出一个新的私钥向量。该新的私钥向量可用于解密用 $\vec{\text{ID}}||\text{ID}^+$ （也是个ID向量）加密的信息。

HIBE的一个直观是：对已分配ID的用户进行授权。假设A有“广东省|深圳市”对应的私钥，那么A可以自行派生出“广东省|深圳市|宝安区”的私钥并分配给下层。这样某种意义上讲减轻了PKG的负担。注意，A无法计算出“广东省”对应的私钥。

Anonymous IBE

Anonymous是指，在challenge阶段中，攻击者要给出两个明文和两个ID，Simulator随机选取一个ID去加密随机其中一个明文。AIND-ID-CPA安全是指攻击者无法区分用了哪个ID加密了哪个明文。易知，AIND-ID-CPA安全可推导出IND-ID-CPA安全。

论文简记

这几篇论文的选择是沿着一条主线而进行的，这条主线主要IBE安全性证明的发展。本节介绍其相关的证明方法。

BF01

[BF01]使用了partition reduction。它证明的大概思路如下：首先根据对应的假设构造reduction的相关参数，然后，把ID划分为两类：一类是可以用于应答Extract query，另一类(个）则是可以用于应答challenge query。

在[BF01]中，每当攻击者进行Random oracle的query时，simulator会进行掷币。若coin=1，则H(ID)的结果可用于应答challenge query而不能用于Extract应答。而coin=0则相反。通过精心选取 $Pr[coin=1]$ 的值，可以使得Simulator以一个不可忽略的概率利用攻击者的优势。由于这一切都是在ROM(random oracle model)下进行，因此只要证明该IBE是ROM下语义安全的，则通过IBE和PKE的转换与FO(Fujisaki-Okamoto)转换，可以得到一个ROM下CCA的IBE scheme。

BB04a

[BF01]后，IBE的证明慢慢发展到了需要在standard model下证明的阶段。[BB04a]提出了standard model下安全的HIBE scheme( $\text{BB}_1$ )。其基于DBDH假设，然而是stdM(standard model)下的selective-ID CPA model下安全。sID即是，攻击者事先需要告诉simulator其想要challenge的 $\text{ID}^*$ 是什么。借助sID模型，simulator可以根据 $\text{ID}^*$ 来适应性的构造出对攻击者各种query的应答。显然，sID-CPA模型弱于ID-CPA模型。而两者之间的规约会带来巨大的因子，导致规约丢失紧致性。

[BB04a]还提出了一个stdM下IND-sID-CPA的IBE scheme( $\text{BB}_2$ )。其基于较强的假设:Bilinear Diffie-Hellman Inversion Assumption(Decision-BDHI)。 $\text{BB}_2$ 具有较高的效率，但是基于的假设并不标准。

BB04b

[BB04b]也是使用了partition reduction的方法。其构造出了stdM下IND-ID-CPA安全的IBE，基于DBDH假设。其提出了新的概念：Admissible hash function(Admissible HF)，并借助其和带偏移的伪随机函数(PRF with bias)构造出安全的IBE。其证明用Admissible HF对输入的ID进行partition，借助Admissible HF的特性，使得攻击者在此模拟环境下的输出，和在模拟biased PRF的环境下输出的分布是一致。然后通过biased PRF的伪随机性，完成规约证明。

Waters05

[Waters05]提出了在stdM下fully secure的IBE(WatersIBE)，其基于DBDH假设。相对于BB04b来讲，Waters的构造相对高效简单。并且值得一提的是，该论文引出了Waters Hash的概念，简要地说，WatersHash大致如下:

$\text{WatersHash}(\text{ID})=u'(\prod_iu^{ID_i}_i)^r$

关于WatersHash还有大量工作。借助WatersHash，规约的构造变得简单。WatersIBE的构造证明也是使用了partition reduction的方法，把ID分成了两类，如果可用于Extract的ID被用于当challenge ID，则simulator会abort。在BF01,BB04b中，Simulator abort的概率是由simulator自身选取的值所决定的，与攻击者的query无关。然而，在WatersIBE的规约中，Simulator abort的概率不仅仅取决于其随机选取的值，还取决于攻击者选取的ID。存在一些ID会使得无论攻击者有怎样的优势，Simulator都没有任何优势。整个模拟环境成功(不abort)的概率下界变得十分难计算。

为了使abort的概率独立于攻击者，WatersIBE加入了artificial abort环节，对失败概率进行estimate，从而使得abort概率独立于攻击者。但artificial abort的加入又使得整个概率分析变得非常复杂。

BR09

能否使WatersIBE的安全性证明去除artificial abort阶段成为了一个open problem.[BR09]的出现解决了该问题。他们使用了code-based game等证明方法和技巧，使得WatersIBE的安全性证明更加自然简洁。然而这在一定程度上丢失了规约的紧致性，但也能获得较高的具体安全性(concrete security)。

和[Waters05]不同，[BR09]不进行“显式的”abort。他们使用了一个boolean标记。若遇到了在WatersIBE中要abort的情况，那么该标记就会设成bad，而不会abort。通过巧妙的game之间的转移，可以使得该标记被设成bad的概率和攻击者选中某个ID query set的概率无关。

Gentry06

[Gentry06]提出了效率很高且在stdM下fully secure（还有CCA secure）的IBE scheme，其规约紧致性也高。然而其基于的假设并不标准，而且该假设的强度依赖于攻击者。攻击者query的次数越多，该假设就越强。具体来讲，文章提出的两个IBE(分别是AIND-ID-CPA安全和AIND-ID-CCA安全)都是基于Decisional augmented bilinear Diffie-Hellman exponent (D-q-ABDHE)假设。该假设的参数q为攻击者query(Extract和Decrypt)的次数。具体证明所用的假设是truncated版的D-q-ABDHE假设，若D-q-ABDHE假设成立则其truncated的版本也成立。

其提出的第一个IBE达到了AIND-ID-CPA安全，证明方法相对简单。而第二个AIND-ID-CCA安全的IBE则是使用了[CS98]的方法。将攻击者从公钥、queries得到的知识用simulator的私钥来表达，再将攻击者想要产生的值（如，可以通过simulator dec oracle密文合法性检查的不合法密文）用一个目标等式表达。通过证明目标等式与攻击者的知识是independent的，从而证明出攻击者通过Dec oracle区分成功的概率是无条件可忽略的。

Waters09

Waters在此工作中提出了称为Dual System Encryption的安全性证明方法。通过使用该方法其构造出了在stdM下基于DBDH和DLin(Decision Linear)假设的fully secure (H)IBE scheme，并且该IBE的公共参数、密文，私钥的群元素数量都是常数个。而前面的工作，要么是基于的假设不标准，要么是参数的群元是线性多个。

基于Waters的Dual System Encryption的IBE scheme不仅包含必须得四个算法，还包含semi-functional extract算法和semi-functional encrypt算法。这两个算法不用在实际构造中，但用于安全性证明。两个semi-functional算法的特点是：用sf extract产生的密钥可以用于解密normal encrypt产生的(用了对应ID加密)的密文；用sf encrypt产生的密文可以被normal extract（一样是对应ID）产生的私钥解密。然而，不能用sf extract产生的私钥解密sf encrypt产生的密文。

整个证明基于Game Sequence方法，简述如下：
$\text{Game}_\text{real}$ 是real scheme，即模拟出的环境与real attack相同。
$\text{Game}_i$ 在 $\text{Game}_0$ 的基础上，修改了两处：(1)challenge ciphertext不再是normal的，而是semi的。(2)前面i次extract queries将返回semi的私钥，后面照常。
$\text{Game}_\text{Final}$ 在 $\text{Game}_q$ 的基础上（q为query的次数上限），不对攻击者提交的明文进行加密，而是返回一个随机值给攻击者。在此game下，攻击者的优势为0。

通过证明攻击者可区分 $\text{Game}_\text{real}$ 与 $\text{Game}_0$ 、 $\text{Game}_{i-1}$ 与 $\text{Game}_i$ 、 $\text{Game}_q$ 与 $\text{Game}_\text{Final}$ 的优势都是可忽略概率，从而证明了IBE的安全性。显然，这样总共转移q次game会导致规约紧致性丢失。

semi-functional的作用.在此IBE中，为什么需要semi-functional的两个算法呢？它们的作用是什么？显然，用到semi-functional算法必然是因为助于证明。在攻击者与simulator的交互中，如果想让攻击者没有任何优势，必须要保证攻击者从queries(Extract、challenge等)中得到的信息与模拟者选择的bit（决定哪个明文被加密）相互独立。而通过对所有Extract query和challenge query进行semi化，保证了若simulator的输入实例是随机值，则其所有与攻击者交互的信息都与其选择的bit无关，即攻击者没有得到任何关于该bit的知识。如此一来，攻击者就没有任何优势去猜中模拟者选中的bit。

[Waters09]提出的IBE scheme有一大问题：在Extract和Encrypt中会产生一个随机tag（两个算法独立产生互不相干），若生成私钥的tag和生成密文的tag相等，则解密失败，无论它们对应的ID是否相同。因此整个scheme会带来 $\frac{1}{q}$ 的error概率。

Waters使用随机产生tag的动机是避免simulator规约的失败。在 $\text{Game}_{i-1}$ 转移到 $\text{Game}_i$ 的过程中，必须避免simulator自行区分第i次Extract query( $\text{ID}_i$ )应答是normal的还是semi的，如果simulator能够自行区分，则规约出现错误。攻击者区分的方法是:用应答第i次 Extract query的方法生成 $\text{ID}^*$ 的私钥，尝试去解密 $M_\beta$ 对应的semi密文，成功则该私钥是normal的，否则是semi的。

Waters通过使用tag从而避免了simulator自行区分的情况，因为tag时相等则无论私钥是normal的还是semi的都无法解密。而在规约构造中，对于相同的ID，其产生出的tag是相同的，而不同的ID产生的tag是两两独立的，这样保障了规约的正确性。

LW10

[LW10]的工作建立在[Waters09]的基础上。其去除了Waters09中tag的使用，使得整个scheme变得更加自然，并且提高了效率（压缩了密文、私钥的长度）和证明的简洁度。

该工作首先提出了基于合数阶(该合数是三个大素数的乘积)群的，在stdM下IND-ID-CPA安全的IBE。其基于的三个假设并不标准，但是可以证明，在generic group model下，如果找到该群阶的一个非平凡因子是难的，则该三个假设都成立。

该IBE构造借助了素数阶子群的"正交性"，简单来说，设 $G$ 的阶级为 $N=p_1p_2p_3$ （三大大素数）,令 $G_{p_1},G_{p_2},G_{p_3}$ 为 $G$ 的真子群并且其阶各为 $p_1,p_2,p_3$ 。则对于任意的 $h_i \in G_{p_i},h_j \in G_{p_j} ( i \neq j)$ ，有 $e(h_i,h_j) = 1$ 。( $e:G \times G \to G_T,ord(G_T) = N$ )。

其规约证明一样是使用Dual system encryption的方法，然而相对[Waters09]而言，整个证明相对更简单。

CW13

Waters提出的Dual System Encryption在一定程度上方便了规约证明，然而其也带来了代价：规约紧致性的丢失。而[CW13]在dual system encryption的基础上，借鉴Naor-Reingold PRF的思想，构造了具有规约证明高紧致性的IBE scheme，该scheme在stdM下满足fully secure.

该工作的IBE使用了Nested Dual System Groups结构，该结构具有多种属性。基于该结构的IBE的安全性证明相对简单，然而想证明某一构造是Nested dual system groups则相对困难的多。文章提出了两种Nested dual system group的实例化构造：一种基于合数阶双线性群，用的假设并不标准。另外一种是基于素数阶群，所用的假设是DLin，但其证明相对复杂。

该工作一大亮点在于：使用了dual system encryption的同时，避免了其规约紧致性的丢失。在[Waters09]和[LW10]的工作中，game是按照攻击者的Extract query而转移的；而在[CW13]中，Game是按照ID各个bit进行转移的，而不是按照Extract query进行转移。由于scheme中ID的长度相当于常数，因此整个规约变得紧致。

具体来讲，与[Waters09]相比，这里的 $\text{Game}_i$ 不是指前i次Extract query用semi-functional的Extract应答。此时的 $\text{Game}_i$ 是指：对Extract query的应答和challenge query的应答都是"type i"的：使用一个随机函数，其输入为ID的前i个比特，把该随机函数输出的结果混淆到normal版本内的类似于Naor-Reingold PRF的结构中。攻击者以可忽略的概率区分 $\text{Game}_{i-1}$ 和 $\text{Game}_i$ （基于Nested system groups的一些不可区分的属性）。而在最后的 $\text{Game}_n$ 中，对应的随机函数的输入为整个ID，因此不同的ID该随机函数的输出不相关，保证了在Extract应答中simulator不泄露关于该随机函数的信息；而在Challenge应答中，simulator（以大概率）相当于对一个随机明文进行加密（而不是目标明文），因此攻击者在此模拟的环境下优势为0。

由于只转移了n次的game，因此规约相对更紧致。

BKP14

[BKP14]提出了一种通用转换:由任意的Affine Message Authentication code(报文认证码，MAC)出发可得到IBE scheme（其双线性群的群阶是素数）。如果该Affine MAC是unforgeability against chosen-message attacks(抗选择明文攻击的不可伪造性，UF-CMA)安全的，那么其得到的IBE是full secure的。

Affine MAC的输出包括两部分：一部分与输入的明文无关，另一部分与输入的明文有关（即偏移部分,affine）。在Matrix Diffie-Hellman Assumption(MDDH)下，可以构造两种满足UF-CMA安全的Affine MAC：一种使用了随机化的Naor-Reingold PRF的方法；另一种使用了Hash proof system(HPS)的方法。前者具有更高的规约紧致性，但基于其之上的IBKEM不具有Anonymity属性；后者规约相对松散，但是其构造的IBKEM具有Anonymity属性。

在具体构造中，此工作的Affine MAC使用了攻击者能力更强的攻击模型：pseudorandom against chosen-message attacks(PR-CMA)。其基于Naor-Reingold PRF思想的Affine MAC安全性证明类似于[CW13]的方法，因此达到紧致规约（game转移了n次，n为明文长度）；而基于HPS的Affine MAC则是用了[CS98]的方法，但是其game转移了q（攻击者query的次数）次，因此规约紧致性不如前者。

而在Affine MAC $\to$ IBKEM的证明中，规约使用了MDDH一个特别的属性：random self reducibility。通过MDDH假设和Affine MAC的PR-CMA属性，可以构造出抗pesudorandom ciphertexts against chosen plaintext and identity attacks(PR-ID-CPA)的安全的IBKEM。而PR-ID-CPA secure可以推出IND-ID-CPA和ANON-ID-CPA。

MDDH在一定程度上方便了规约，尤其是其random self reducibility性质。（由于对MDDH的理解还很肤浅，因此对此论文的理解还很不足。）

阅读收获

一定程度上了解了IBE的发展，同时也从侧面理解了一些可证明安全的发展。

对可证明安全更加熟悉，对DH指数的运算、pairing指数的运算、协议correctness的验证等计算的熟悉度也提高了很多。

了解了不少假设

领会了一些藏在论文里的方法论

开始自己的思考