1必备的数学知识

1.1单向函数

f:{0,1}->{0,1}

• 存在多项式算法输入x属于{0,1}，输出发f(x)

1.2可忽略函数

f(l)对于任意多项式p(.),f(l) < 1/p(l)

1.3多项式时间算法

O(l^c),l为算法的输入规模，c是一个常数，算法A为多项式时间算法

1.4单向同构函数

2哈希函数：

2.1通过余数定理将一个任意长度的消息，生成较短的固定的消息摘要，提高签名速度

2.2哈希函数的介绍

哈希函数是一个有效的确定性，将任意长度的比特串x{0,1}映射为固定长度的比特串，

2.3哈希函数安全：

2.1原像稳固

2.2第二原型稳固

2.3强抗碰撞

同态哈希函数

3.双线性及其基本困难问题

3.1双线性对：

(1)定义：令G1,G2和Gt为3个q阶的循环群，q是一个大素数，双线对e:G1*G2->Gt,满足以下性质：

4.基本困难问题

4.1离散对数问题

4.2DL困难性假设

4.3计算Diffie-Hellman问题

4.4CDH困难性假设

4.5co-CDH问题

4.6判定Diffie-Hellman问题(DDH)

4.7DDH困难性假设

4.8双线性Diffie-Hellman问题(BDH问题)

4.9BDH困难性假设

4.11判定双线性Diffie-Hellman问题(DBDH问题)

4.12DBDH困难性假设

数字签名的形式化定义

1.传统公钥系统的数字签名的形式化定义

依赖于公钥密码系统

1.1传统数字签名基于公钥密码系统主要由三个算法构成

1.密钥生成算法
2.签名算法
3.验证算法

正确性约束

基于身份的数字签名形式化定义

1.2基于身份的数字签名主要有四个算法构成

• 系统设置算法
• 私钥提取算法
• 签名算法Sign(sk,m)

• 验证算法Verify(ID,params,m,Q)->0或1：输入用户身份ID,系统签名params,消息m的签名Q,验证通过，则签名有效，输出1,否则输出0

  
  

正确性约束

签名方案的安全性需求

需要确定一个攻击模型和攻击者的目标，攻击模型确定了敌手进行攻击时所拥有的信息，

唯密钥攻击:对签名进行攻击

已知消息攻击：攻击者拥有一系列以前有签名

选择消息攻击

适应性选择消息攻击

5本文用到的数字签名方案

5.1传统公钥体制下的数字签名方案-BLS短签名

5.2基于身份的数字签名方案-Hess签名方案

1.系统设置算法Initialization->(params,sk):参数生成器以安全数为k作为输入，生成阶为q的循环群G1,G2以及一个对称性对e:G1 * G1 ->G2

2.依赖于co-CDH问题的困难性问题

5.3线性同态签名方案

基于身份的线性同态签名形式化定义与安全模型

线性同态化签名的形式化定义和安全模型

任何用户可以通过合并算法计算出某个消息的签名而不需要使用签名方的私钥

线性同态签名有如下特点：

定义一个线性同态签名方案

线性同态签名的安全模型

1.一般攻击者A询问子空间的签名，算法C会返回子空间的一组基向量v1,v2,v3,vm的签名,攻击者A的攻击方式一般分为两种：

A攻击成功

2.第二种攻击方式中：

线性同态签名方案LHS的安全性通过攻击者A和挑战者C之间的交互游戏来定义：

系统建立

询问

伪造及定义

3.3基于身份的线性同态签名的形式化描述

PKG的由来：用来生成私钥的，为系统的用户分发用户公钥和私钥

基于身份的线性同态签名密码系统结合了基于身份的公钥密码系统和线性同态签名的密码系统的特点

五个算法构成

• 系统设置
• 私钥提取
• 签名算法
• 合并

• 验证

  
  

一个基于身份的线性同态签名方案由以下算法构成：

3.4基于身份的线性同态签名的安全模型

系统建立

伪造

4引言

4.2线性同态签名方案IB-LHS1

4.3IB-LHS1的方案由如下算法组成：

1.Initialization(1^k,N)->(params,msk):
2.KeyExt(ID,msk)->sk
3.Sign(ID,Q,sk,v)->(r,Q)
4.Combine(ID,r,Q1,Q2,Q3,Q4,f)->(v,Q)
5.Verify(ID,Q,r,v,Q)->0或1

方案的正确性分析

私钥提取询问

签名询问

主要分为V

伪造

优势分析