An Introduction to Pairing-Based Cryptography学习笔记

Alfred Menezes 2005年论文《An Introduction to Pairing-Based Cryptography》。

1. DLP & DHP & BDHP &DDHP

显然地，DHP可reduce in polynomial time to the DLP，在某些特殊情况下，DLP亦可reduce in polynomial time to the DHP。

1.1 DLP

自1975年发明了公钥密码学以来，DLP(discrete logarithm problem)就被广泛研究。
DLP in an additively-written group $G=<P>$G=<P> of order $n$n为：已知$P和Q$P和Q，找到相应的整数$x\in[0,n-1]$x∈[0,n−1]，使得$Q=xP$Q=xP。
在精心选择的groups【如multiplicative group of a finite field或者是the group of points on an elliptic curve defined over a finite field】中，人们相信DLP是难以**的。

1.2 DHP

DHP(Diffie-Hellman problem)为：已知$P, aP, bP$P,aP,bP，求得$abP$abP。
DHP基于的场景为W. Diffie 和 M. Hellman 1976年论文《New directions in cryptography》构建的双方公钥交换。详细的思路为Alice拥有私钥$a$a，将对应的公钥$aP$aP发送给Bob；Bob拥有私钥$b$b，将相应的公钥$bP$bP发送给Alice，基于各自的私钥Bob和Alice可构建一致的公钥$K=abP$K=abP。对于双方传输中存在的窃听者Eva，其仅知$P, aP, bP$P,aP,bP，是否可计算获得$abP$abP值？

若想推广至三方公钥共识，则可采用two-round两轮方式来实现：

是否可将上图的Three-party two-round key agreement protocol转化为Three-party one-round key agreement protocol呢？答案是：2000年，Joux[32] 借助bilinear pairings实现很简单就实现了Three-party one-round key agreement protocol。【另外两个基于pairings的主要应用为： identity-based encryption scheme （D. Boneh和M. Franklin 2001年论文《Identity-based encryption from the Weil pairing》）；short signature scheme（D. Boneh, B. Lynn和H. Shacham 2001年论文《Short signatures from the Weil pairing》）。】

1.3 BDHP

BDHP(bilinear Diffie-Hellman problem)为：【pairing-based protocols的security依赖于BDHP的难度。】

BDHP的难度意味着DHP在$G_1$G1​和$G_2$G2​中的难度。

1.4 DDHP

DDHP(decisional Diffie-Hellman problem)为：

2. PBC——pairing-based cryptography

2.1 Bilinear pairings

Bilinear pairing定义及属性为：

2.2 Joux’s three-party one-round key agreement protocol

Alice, Bob和Chris三方共享的公钥为$K=\hat{e}(bP,cP)^a=\hat{e}(P,P)^{abc}$K=e^(bP,cP)a=e^(P,P)abc。对于窃听者Eva来说，需要解决BDHP难题才能获取$K$K值。

借助multilinear map $\hat{e}_n:G_1^{l-1}\mapsto G_T$e^n​:G1l−1​↦GT​，该协议可扩展至$l-$l−party one-round protocol。尽管当$l>3$l>3时，相应的multilinear map可能不存在。

2.3 BLS short signature scheme

大多数的discrete logarithm signature schemes（如DSA）都是EIGamal signature scheme的变种，其签名最终都是由a pair of integers modulo n组成（n为the order of the underlying group $G_1=<P>$G1​=<P>）。
BLS short signature scheme（D. Boneh, B. Lynn和H. Shacham 2004年论文《Short signatures from the Weil pairing》），其签名最终仅需由一个单独的group element组成。（而且该group element可大约以the same number of bits as an integer modulo $n$n）。采用的是a bilinear pairing $\hat{e}$e^ on $(G_1, G_T)$(G1​,GT​) for which the DHP in $G_1$G1​ is intractable。BLS short signature scheme具有可aggregated属性。

2.4 Identity-based encryption scheme

若Bob通过使用Alice的公钥对消息$m$m加密后秘密传送给Alice，Alice使用私钥对加密后的消息进行解密，其中存在如下问题：如何保证Bob所拥有的公钥真的是Alice的，而不是其它attacker的，从而避免本指定给Alice的消息不被attacker decrypt？
传统地，在大规模的公钥分发过程中，通常会引入CA（certifying authority），CA为公钥颁发证书，证书中包含Alice的标识信息、Alice的公钥以及CA对该标识信息的签名。任何具有CA公钥的人可验证证书的签名，从而可确认Alice公钥的真实性。但是在实际证书管理时，存在很多问题：如Bob如何获得Alice的证书？Bob如何确认Alice的公钥仍然有效，CA未对其证书进行撤销（如因离职或私钥泄露等原因）？
1984年，Shamir[51]首次引入了身份密码学的概念，用于解决证书管理中的各种问题。Shamir提议Alice的公钥包含其标识信息$ID_A$IDA​（如Alice的email address）。可信第三方（TTP, trusted third party）使用其私钥，基于$ID_A$IDA​来生成Alice的私钥，同时秘密将该私钥发送给Alice。Bob则使用Alice的$ID_A$IDA​和TTP的公钥来加密消息。Bob可在Alice生成其公私钥对之前对消息进行加密。标识信息$ID_A$IDA​中可包含credit rating, employment status, minimum age requirement以及date等信息，TTP可根据这些标识信息来决定是否给Alice分发相应的私钥。

D. Boneh和M. Franklin 在2001年论文《Identity-based encryption from the Weil pairing》中提出的identity-based encryption scheme，是第一个使用的identity-based encryption scheme，该scheme采用的是a bilinear pairing $\hat{e}$e^ on $(G_1, G_T)$(G1​,GT​) for which the BDHP is intractable。

上述实现，可防止窃听，但是无法抵抗chosen-ciphertext attacks：

通过以下改进，可解决chosen-ciphertext attacks问题：

Identity-based encryption scheme有以下缺陷：需要有安全通道用于私钥传输；需要TTP可信第三方来生成所有的私钥等。

Identitiy-based和certificate-based的身份管理系统的优劣势可参见论文：K. Paterson and G. Price, “A comparison between traditional public key infrastructures and identity-based cryptography”, Information Security Technical Report, 8(3) (2003), 57–72.

3. Elliptic curves

若所选择的Elliptic curve的embedding degree是小的时，采用subexponential-time index-calculus算法解决$F_{q^k}$Fqk​域内的DLP问题比采用Pollard’s rho method解决ECDLP in

更易达成。在$k\in\{1,2,3,4,6\}$k∈{1,2,3,4,6}的supersingular curves中也确实如此。
而对于大多数的prime order over prime fields的elliptic curves，其$k\approx n$k≈n，则其ECDLP并不存在Weil和Tate pairing攻击问题。
所以，自20世纪90年代初起，已达成共识，具有low embedding degree的elliptic curve不适合用于discrete log protocols中。但是，low embedding degree的elliptic curve在高效实现pairing-based protocols中至关重要。

4. Tate pairing

5. PBC 曲线的选择

现有的pairing曲线有：bls12_377、bls12_381、edwards_bls12、edwards_sw6、jubjub、mnt6、sw6等。【zexe中有针对这些曲线做过实现。】