荔枝成为BLS短签名糕守

Posted on Edited on

BLS短签名是什么？先用一天的时间突击一下

发现《Introduction to Security Reduction》整个第五章都是......

英语不好，先学BLS再看论文（诶嘿

罐装芝士

简介

开篇论文：Lynn B . Short signatures from the Weil pairing[M]// Advances in Cryptology — ASIACRYPT 2001. Springer Berlin Heidelberg, 2001.

BLS签名由Boneh、Lovász和Shamir等人提出，所以叫BLS（和RSA一模一样.......）

BLS签名基于椭圆曲线上双线性映射的数字签名方案，具有短签名的优点，保证签名的安全性和不可伪造性

开篇论文的灌装芝士

摘要：面向椭圆曲线和超椭圆曲线，基于计算的Diffie–Hellman假设提出了一种短签名方案。对于标准安全参数，签名长度大约是同样安全级别的DSA签名长度的一半。这个短签名方案是为人工输入签名或通过低带宽传播签名的系统设计的。对于签名聚合和批处理验证的性能进行了研究。

思考：这篇BLS签名算法的老论文有很多晦涩的定义和证明，但是其中提出的BLS 签名算法带来的签名聚合功能有助于把一个区块中不同人不同算法的签名聚合成一个签名，能够节省区块中存储空间和交易费，也能简化验证签名的过程，在多个参与方合作的联盟链场景中可以考虑使用。

补充：BLS签名算法主要需要进行曲线配对和签名聚合两项工作，具体内容如下：

  1. 曲线哈希：BLS签名算法是一种可以实现签名聚合和密钥聚合的算法，它修改了哈希算法，结果不再是一个数值而是对应到椭圆曲线上的一个点。
  2. 曲线配对：需要一个特殊的函数把曲线上的两个映射为一个数，需要满足的属性是无论哪个点乘以未知数，结果必须相同。论文中论证过这种函数是存在的，并且不会暴露x的任何相关信息（安全性）。
  3. 签名方案：为了计算签名，先对消息求曲线哈希，再将获取的结果（曲线坐标点）乘以私钥即可：。签名结果是一个曲线上的点，用压缩的序列化格式保存，只占33个字节。
  4. 验签方案：只需验证公钥和消息的哈希值（曲线上两个点）与曲线生成点和签名（曲线上另两个点）是否映射到同一个数，如果是就说明这是一个有效的 BLS 签名。
  5. 安全隐患：BLS签名也不是完美无缺的，它的复杂度要比ECDSA高上一个数量级。在验证区块中1000笔交易的聚合签名时，仍需要进行1000次配对计算，这可能比使用ECDSA时对1000个单独签名进行验证还要慢。唯一的好处在于，可以在区块中放更多笔的交易，毕竟聚合签名只占32字节。另外还有一种针对椭圆曲线加密体系的MOV攻击，利用配对函数来危害系统安全。

对ECDSA、schnorr和BLS签名算法的资料整理如下表：

ECDSA schnorr BLS
验证多重签名 每个签名和公钥 每笔交易的合并签名和公钥 每个区块的合并签名和公钥
随机数生成器 指定随机点 依赖随机数生成器 不需要随机数生成器
签名者通信 需要 不需要
签名长度 320比特 320比特 160比特

[1]schnorr签名算法可以把一笔交易中的所有签名和公钥合并成单个签名和公钥，而且无从追溯是否合并过，一次性对合并后的签名验证，加快区块验证速度

关于ECDSA和schnorr的学习挖了个坑，还没填完，抽空学习一下

原理

  1. 初始化：选择两个素数 阶乘法循环群和，以及一个双线性映射。生成元和，公开参数为。
  2. 密钥生成：选择一个随机数作为私钥，计算作为公钥。私钥需要妥善保管，而公钥可以公开。
  3. 签名：消息的签名，其中是一个安全哈希函数。
  4. 验证：验证签名的有效性可以通过计算是否等于来实现。如果相等，则签名有效；否则，签名无效。

对于双线性群，哈希函数 ，私钥，公钥，消息

签名：

验证：

安全性证明

https://blog.csdn.net/CCCYYY090/article/details/116660613

CDH问题

https://blog.csdn.net/zmrlinux/article/details/107729245

https://www.cnblogs.com/shirleyya/p/16776893.html

https://www.cnblogs.com/lsgxeva/p/12021659.html

https://zkfold.ing/blssig-secure

基于BLS签名的门限签名

门限签名是一种数字签名方案，其中多个签名者合作生成一个签名，只有当超过一定数量的签名者同意时，该签名才有效。基于BLS签名的门限签名利用了BLS签名的短签名和高效验证算法的优点，同时还提供了门限签名的安全性。

基于BLS签名的门限签名通过以下步骤实现：

  1. 初始化：与BLS签名相同，选择合适的素数p阶乘法循环群、和，以及双线性映射: 。同时选择公开参数。
  2. 密钥生成：每个参与者随机选择一个私钥和一个公钥。每个参与者保留其私钥并公开其公钥。
  3. 签名：当消息M被提出时，超过个参与者共同对消息进行签名。每个参与者i使用其私钥计算，然后将广播给其他参与者。所有参与者共同生成一个元组，该元组作为最终的签名。
  4. 验证：验证签名的有效性需要检查是否满足，其中。如果所有参与者的公钥都满足这个等式，则签名有效；否则，签名无效。

应用场景

BLS签名和基于BLS签名的门限签名在许多安全敏感的应用场景中得到了广泛应用，例如电子投票、数字版权保护、身份认证等。由于它们的短签名和高效验证算法的优点，它们在保证数据完整性和防止伪造方面具有出色的性能。

总结：本文深入探讨了BLS签名和基于BLS签名的门限签名的工作原理和应用场景。通过了解这两种签名的原理和实现步骤，我们可以更好地理解它们在保护信息安全方面的重要作用。随着技术的不断进步，相信BLS签名和基于BLS签名的门限签名将在未来的信息安全领域发挥更加重要的作用。

reference：

https://cloud.baidu.com/article/3084711

https://blog.csdn.net/weixin_42120773/article/details/104394223

《Introduction to Security Reduction》的介绍

论文中的展现

《Short Signatures from the Weil Pairing》

Weil Pairing挖个坑，之后学习一下这些配对

作者：BLS三个人，Stanford University

需求和贡献：

在要求人类手动输入签名的环境中，需要短数字签名

RSA的签名长度为1024位，DSA的签名长度为320位

BLS的签名长度是DSA签名的一半，仅有160位，

感谢师兄的讲解

讲解BLS系列论文，流程是 算法模型安全证明 （有时先模型后算法）

其中，算法指的就是算法（废话

安全模型指的就是安全模型（废话*2

BLS中，安全模型用到的是 EU-CMA

然后证明，我觉得是最难的部分，感谢师兄讲解

（后面是付费内容了，太珍贵了

Short Signatures from the Weil Pairing

BLS是个GDH问题，所以需要证明 CDH是困难的， DDH是简单的

首先定义两个集合 ，以及参数

是时间，是签名询问的次数，是哈希询问的次数，是某个限制但是不重要（bushi

A是敌手，B是挑战者

哈希询问

A每次给B一个的，B返回给A对应的哈希值（一一对应）

挑战者每获取一个，会保存一个四元组

其中和是随机数

， （这个概率公式是时间最优的，可以使用函数来证明）

，，其中是到的一个映射

这也就意味着，时，包含；反之则不包含（嵌入困难问题）

签名询问

A每次给B一个的，B返回给A对应的签名（一一对应）

对于每个询问的，如果生成（包括已生成或即将生成）的，则被判定为失败

1
2
问题：为什么要有哈希询问，如果只进行签名询问，还能避免生成会导致失败的c
回答：但是这样子就不是c=0/1都有了，就无法在output环节可以有c=0保证不会失败了（即必然失败）；故在一定范围内，哈希询问尽可能多

输出结果

B询问 ，如果 ，则被判定为失败；否则

检查

Efficiency Improvements for Signature Schemes with Tight Security Reductions

算法

是哈希函数，是反哈希函数（满足双射，互为逆运算）

生成密钥

签名

  • 之前询问过：直接返回输出；否则计算并返回

验证

  • 计算 ，如果 则接受，否则拒绝

证明

哈希询问

  • 记一个三元组列表，满足 （同样的， ）

    \