刘翔宇, 刘胜利,3, 谷大武

1. 上海交通大学 计算机科学与工程系, 上海200240

2. 密码科学技术国家重点实验室, 北京100878

3. 成都卫士通信息产业股份有限公司摩石实验室, 北京100070

1 引言

在可证明安全中, 密码学方案总是基于某些困难问题, 且其安全性是通过安全归约证明来实现的. 安全归约的思路如下: 如果存在某个运行时间为t 的敌手A 能以优势ϵ 攻击某个密码方案S, 我们通过调用算法A 构造出另一个运行时间t′的算法B, 使得算法B 以ϵ′的优势解决某个困难问题P. 参数L := (t′ϵ)/(tϵ′) 定义为安全归约中的损失因子. 在安全归约中, 一般要求L 是一个关于安全参数λ 的多项式. 因为问题P 的困难性假设认为不存在算法可以在多项式时间内解决问题P, 所以密码方案S 不存在多项式时间的敌手A, 故而证明了S 的安全性. 当t′=Θ(t) 时, 归约损失因子可等价定义为L:=ϵ/ϵ′.如果L 是一个常数, 那么此安全归约是紧致的. 如果L=O(λ) (λ 为安全参数), 归约是几乎紧致的. 在很多签名方案(Signature, 简称SIG) 中, 松散安全归约的损失因子L 与敌手得到的签名数Q 及其涉及的用户数µ 紧密相关. 假设L ≈240, 这就造成了一个很大的安全损失. 为了弥补这个损失, 在密码方案的实施过程中, 我们需要选择更大的安全参数, 导致元素尺寸的增大和计算次数的增加, 从而降低算法的效率.因此, 近些年来的许多密码方案都在追求紧致安全性[1–9].

基于身份的签名(identity-based signature, IBS) 方案最早由Shamir[10]提出. IBS 的实施通常建立在一个群组中, 群组管理员产生主公钥mvk 和主私钥msk, 并借助……