【温故】BLS签名(上)

本次回顾的论文是“ShortSignaturesfromtheWeilPairing”...



本次回顾的论文是“Short Signatures from the Weil Pairing”

发表于2004 年《Journal of Cryptology》

数字签名是一种基本的密码学原语，包括密钥生成、签名和验证三个算法，用于保障消息完整性、真实性和不可抵赖性。实践中常见的数字签名方案包括RSA 和DSA 两种。以80 比特的安全强度(现在推荐使用更高强度的加密算法) 为例，RSA 算法的签名长度为1024 比特(即模数长度为1024比特)，DSA 算法及其椭圆曲线上的变体——ECDSA 算法的签名长度均为320 比特(ECDSA 的公钥长度更小)。

然而，上述算法产生的签名都较长，并不适合人工输入或带宽受限的情形，因此需要在同样安全强度下生成更短的签名。

短签名

这篇论文提出了一种新的数字签名方案，该方案与320 比特的DSA签名强度相近，但签名长度约为170 比特。该方案在CDH(Computational Diffie-Hellman) 假设及随机谕示模型(Random Oracle Model) 下被证明是不可伪造的。

细节说明




这篇论文的方案基于GDH(Gap Diffie-Hellman)群，即该群上的CDH问题是困难的，但DDH(Decision Diffie-Hellman)是容易的。



CDH问题是困难的即表明没有敌手能在时间t内，以大于ε的概率求解CDH问题。DDH问题是容易的即表明存在算法在较短时间内求解DDH问题。
这篇论文利用双线性映射来求解DDH问题，即若最后，本文要求存在可高效计算的群同构：本文BLS签名


下面介绍这篇论文的方案——BLS签名

其中
是一个全域哈希函数。



由于签名是群G1上的元素，因此若要使得签名长度较短，则需要G1上的元素有较短的表示。设
是一条椭圆曲线，
是椭圆曲线上的点构成的群，
的阶为素数p。当q的长度为168比特时，其安全强度大约与320比特的DSA签名相近，令
，则签名长度约为170比特。

扩展应用1



扩展应用2



扩展应用3

    关注 珞珈之戍