第四章 短签名和基于身份的签名（ 2 学时）【讲授内容】1． 双线性对2． 短签名3． 基于身份的签名4．1 双线性对（pairing ）为什么能够签名长度短？就是利用了双线性对的原因。

（现在是一种趋势。

）假设21,G G 是两个群，阶数都是素数q 。

1G 为加法群，2G 为乘法群。

P 是1G 的任一生成元，aP 就是a 个P 相加。

假设离散对数问题在21,G G 都是困难的。

满足以下条件的映射211:G G G e →⨯叫做双线性映射（bilinear map ）（1） 双线性性：*∈∈=qab Z b a and G Q P all for Q P e bQ aP e ,,,),(),(1 （2） 非退化性：如果P 是1G 的生成元，则),(P P e 是2G 的生成元，也即1),(≠P P e（3） 可计算性：容易计算1,),,(G Q P all for Q P e ∈。

Bilinear map 也叫做Pairing 。

椭圆曲线上或超椭圆曲线上的Weil 对和Tate 对可作为pairing 使用。

（椭圆曲线上加群的离散对数问题，可构造数字签名。

）而基于椭圆曲线上的加法群的离散对数问题建立的方案，具有长度短，安全性高的优点。

现在再结合双线性对的特性，可使方案具有长度短和证明简便的结合的优点。

计算DH （CDH ）问题：给出一个随机生成元g 和随机元素G h h ∈21,，计算))(log (log 21h h g g g ，也即如果y x g h g h ==21,，计算输出xy g 。

如果这是困难的，就说CDH 假设在G 成立。

对应于加法群：1G 上的DDH （Decisional Diffie-Hellman ）问题：给出*∈qZ c b a cP bP aP P ,,),,,,(，判断ab c =。

这一问题可以在多项式时间解决（验证),(),(cP P e bP aP e =）。

习惯写法：),(),(),,,(B A e Q P e B Q P A V DDH =→1G 上CDH （Computational Diffie-Hellman ）问题：给出*∈q Z b a bP aP P ,),,,(，计算abP 。

Gap Diffie-Hellman group （GDH ）：计算DDH 容易，计算CDH 困难。

Pairing 的原象域domain 就是GDH 群的例子。

),,(21e G G 上Bilinear Diffie-Hellman （BDH ）问题：给出*∈qZ c b a cP bP aP P ,,),,,,(，计算abc P P e ),(。

4．2 短签名（short signature ）一些场合需要短签名，例如移动通信的认证、电子机票、软件序列号。

BLS 短签名：（D. Boneh ，Lynn ，Shacham 在2001年提出），假设GDH 成立。

（1）密钥生成：不同的是21,G G 都是乘法群，>=<g G 1，211:G G G e →⨯是双线性映射。

1}*1,0{:G H →，*∈qZ x 是私钥，q g y x mod =是公钥。

（2）签名过程：对于*}1,0{∈m ，计算x m H )(=σ（3）验证过程：对于),(σm ，验证))(,(),(m H y e g e =σ，若成立则接收。

正确性：))(,())(,())(,())(,(),(m H y e m H g e m H g e m H g e g e x x x =====σ短到何长度？160bit 。

ZSS 短签名（Zhang ，Safavi －Naini ，Susilo ，2004）（比BLS 签名有效。

）假设（k ＋1）指数问题是困难的。

（给出*∈q k Z y P y P y yP P ),,,,,(2 ，计算P y k 1+）（1）密钥生成：),,,,,(21H P e q G G 是公共参数。

*→qZ H )*1,0(:，*∈q Z x 是签名者的私钥，xP P pub =是其公钥。

（2）签名过程：对于*}1,0{∈m ，计算P x m H S +=)(1（3）验证过程：对于),(S m ，验证),(),)((P P e S P P m H e pub =+，若成立则接收。

正确性：),())(1),)(((),)((P P e P xm H x m H P e S P P m H e pub =++=+4．3 基于身份的签名（identity-based signature ）公钥的分发、认证和管理是一件繁琐的事。

为此Shamir 提出基于身份的概念，就是公钥为个人的身份。

这一概念在D. Boneh 提出基于双线性对的方案之后，得到了广泛实现。

Paterson 的基于身份的签名（2002）：假设：扩展的ElGamal 签名是安全的。

（1）密钥生成：),,,,,,,,(32121H H H P P e q G G pub 是公开参数。

其中sP P pub =（TTP 的公钥），s 是随机选择的，称为主密钥。

211:G G G e →⨯是双线性映射。

用户的公钥)(1ID H Q ID =，私钥是ID ID sQ D =。

（2）签名过程：为了对*}1,0{∈m 签名，随机选择*q Z k ∈，计算))()((,321ID D R H P m H k S kP R +==-签名为（R ，S ）。

（3）验证过程：验证者验证：)()(32),(),(),(R H ID pub m H Q P e P P e S R e =正确性： )()(323232132),(),())(,())(,())()(,())()((,(),(R H ID m H ID ID ID Q sP e P P e D R H P e P m H P e D R H P m H P e D R H P m H k kP e S R e ==+=+=-但是由于基于身份的签名（或加密）中，用户的私钥也在TTP 的掌握之中（即所谓密钥托管escrow ），这是有隐患的，因此现在又出现了无证书（certificationless ）的签名和加密技术。

无证书技术中的私钥是用户和TTP 合作完成的，TTP 不会知道最终的用户私钥。

【课后练习】1．基于身份的概念，可以扩展到其它类型的签名，试分析基于身份的加密方案。

2．无证书的签名的公私钥对是如何形成的？3．基于双线性对的方案的实用性如何？【参考资料】1．双线性对的特点是证明简便，因此它的应用很广泛。

存在基于双线性对的各种签名和系统，例如以后所讲的基于双线性对的盲签名、群签名、代理签名等，其应用领域都有深入研究和进展。

双线性对的选取和计算速度问题是实用中应考虑的，目前双线性对的计算速度提高很快。

2．基于身份的概念，可以扩展到其它类型的签名，还有基于身份的加密等。

可参见印度学者R.Dutta, et.al. Pairing-based cryptography:a survey,（eprint-2004），概括比较全面。

第五章 盲签名和群签名（ 2 学时）【讲授内容】1． 盲签名和电子现金2． 群签名和环签名、电子投票5．1 盲签名（blind signature ）和电子现金（e －Cash ）为了完成一些特殊的目的，需要增加安全功能，这是就是附加功能的签名。

首先是能不能附加，其次是如何附加的？例如最开始进行这方面努力的是盲签名。

现在网上交易多用信用卡，但缺少匿名性，任何交易都是实名的。

所以人们需要匿名性。

盲签名就是可以实现某种匿名性的签名。

盲签名（blind signature ）：和基本签名不同，盲签名是两个参与者：发送者A 和签名者B 的协议。

a 、发送者A 首先将消息m 进行盲变换，再将变盲的消息m ’送给签名者B ；b 、签名者B 对盲消息m ’进行签名S ’，送给发送者A ；c 、发送者A 对签名S ’进行脱盲变换，得到对原来消息m 的签名S 。

A 可以得到原来消息m 的签名。

而签名结束后，B 既不知道消息m ，也不知道m 对应的签名。

盲签名就像将消息放在一个信封里，送给签名者签名，签名者在信封上用复写纸签名，之后将信纸取出，得到签名。

f 为盲化函数，g 为脱盲函数，满足((()))()B B g S f m S m = 盲签名的目的是防止签名者了解签名的真正消息及对应的签名，可用于许有某种匿名性的地方，例如电子现金和选举等。

在电子现金方案中，电子现金就是银行所做的盲签名，此时银行并不了解用户取走的实际钱币（签名）内容，保证了消费者进行消费时的匿名性。

典型盲签名方案：RSA 盲签名：假设RSA 的公私钥对为d e n ),,(。

（1）blinding ： A 选择一个随机数k ，1),gcd(,10=-≤≤k n n k ，计算n mk m e mod *=，将其送给B ；（2）signing ： B 计算n m s d mod *)(*=，将其送给A ；（3）unblinding ：A 计算n s k s mod *1-=，s 就是B 关于m 的签名。

当然，还有其它类型的盲签名。

电子现金方案（e-Cash ）：要求：（1）电子信息容易复制，因此需要防止重复花费；（2）防止伪造；（3）防止暴露匿名性；金额大小的问题？固定每次只能取100元，或者每种金额采用不同的公钥。

（现在有可分的）；或者采用cut-choose 策略（game ，博弈论方式）：用户盲化100个20元的消息，交给银行；银行任选99个，让用户脱盲；用户将99个脱盲的结果交给银行检查；银行检查无误后，说明用户99％是可信的。

（你切蛋糕，我选择哪块）防止重复花费，可以利用在线系统on-line 查询，每次交易商家询问银行，电子现金是否是重复的。

也可以采用以下off-line 系统。

其中为了防止重复花费，用户需要使用随机数RIS （random identity string ），用以确定电子现金的一次性。

简单的电子现金方案（离线的）（D. Chaum, A. Fiat, and M. Naor. Untraceable electronic cash. CRYPTO’88）：（1）取款协议a ． 用户准备100个20元的单据，形式如下：)',,',,',,4527#,20'(,,2,2,1,1,K i K i i i i i i y y y y y y i yuan m I M =其中)(,,j i j i x H y =，)'(',,j i j i x H y =，其中',,,j i j i x x 是随机选择的，满足j i all name user x x j i j i ,',,∀=⊕b ． 用户盲化i M 为'i M ，送给银行；c ． 银行随机选择99个，让用户脱盲；d ． 用户脱盲的同时，提供相应的',,,j i j i x x ；e ．银行检查是否是20元面值、)(,,j i j i x H y =、)'(',,j i j i x H y =、name user x x j i j i =⊕',,；f ． 成立后，银行对剩下的一个盲化消息进行签名；g ． 用户脱盲后得到M ，s 。