在信息安全领域,数字签名(digital signature)可以提供身份认证、数据完整性保护和数据不可否认等诸多服务,因此它是密码学领域的一个重要研究方向。数字签名方案的标准安全性是自适应选择消息攻击下的签名不可伪造性(unforgeability under adaptive chosen message attacks,简称cma安全性)。其安全性证明是通过构造安全规约,将数字签名方案的cma安全性规约到某些公认问题的困难性上。现有的大部分标准模型下的数字签名方案及安全性证明具有如下特点:·安全规约松散。在一般数字签名方案的安全性证明中,其安全性规约的损失因子一般与签名查询次数qS有关。此时为了达到目标安全性水平,我们必须选择更大的安全参数,这直接增长了密钥及签名长度,增加了方案的运行时间,给方案的效率带来巨大影响。如果安全性规约的损失因子仅为常数或是安全参数的线性因子,我们称这样的安全性规约为(几乎)紧致的,因此设计具有紧致安全性的数字签名方案具有更重要的研究价值。·安全性证明仅考虑单用户环境。一般数字签名方案的安全性只刻画了签名方案在单用户环境下的安全性,此时敌手仅得到一个验证密钥,只需输出针对此密钥的消息签名伪造。但是在现实场景中,一个签名方案通常有多个用户使用,故而敌手实际可以得到多个用户的验证密钥。通过混合论证,可以将多用户cma安全性规约到cma安全性,但其规约更加松散,会额外损失一个因子n,其中n为用户个数。因此考虑数字签名方案在多用户环境下的紧致安全性(unforgeability under adaptive chosen message attacks in the multi-user setting,简称m-cma安全性)具有更强的实际意义。·不能抗量子攻击。随着量子技术的发展,大规模的量子计算机可能在不久的将来得到广泛应用。在量子时代来临后,恶意的敌手会拥有量子计算能力,因此很多经典密码学方案也将随之被攻破,例如许多数论问题,如大整数分解问题、离散对数问题等,可以被Shor算法轻易破解,因而许多基于数论假设的数字签名方案都将不再适用。因此构造基于抗量子攻击的困难问题(如LWE问题,子集和问题等)的数字签名方案成为了一个重要的研究方向。针对上述数字签名方案及安全性证明的特点和问题,本文对多用户环境下紧致安全的数字签名进行了深入研究,并设计了两个数字签名方案的通用构造。我们对通用构造进行了实例化,得到了基于DCR假设,矩阵DDH假设的数字签名方案,以及基于LWE假设和子集和问题假设的后量子安全的数字签名方案。这些方案均可在标准模型下证明其在多用户环境下的紧致安全性。此外,我们还针对特殊性质的数字签名方案,如基于身份的数字签名方案的构造和线性同态签名方案的应用进行了深入研究。我们的研究成果如下:·在标准模型下设计了第一个多用户环境紧致安全的数字签名方案的通用构造。我们首先给出了第一个基于DCR假设的紧致安全数字签名方案。然后我们将其扩展为多用户环境和标准模型下紧致安全数字签名方案的通用构造,其安全性基于子集成员判定问题(subset membership problem,SMP)。最后我们将SMP问题假设分别实例化为DCR假设和矩阵DDH假设,得到基于DCR假设和矩阵DDH假设的多用户环境下紧致安全数字签名方案。·基于LWE假设设计了多用户环境紧致安全的后量子数字签名方案。我们首先给出了一个新的多用户环境和标准模型下紧致安全的签名方案的通用构造,其基本构件为一个安全性很弱、具有不完美正确性的局部一次签名(partial one-time signature,POS)方案。我们给出POS方案的两个实例化:一个基于Ring-LWE假设,一个基于子集和问题假设。将基于Ring-LWE假设的POS方案应用到我们的通用构造,我们得到了第一个在多用户环境和标准模型下紧致安全的基于LWE假设的签名方案;将基于子集和问题假设的POS方案应用到我们的通用构造,我们得到第一个在标准模型下几乎紧致安全的基于子集和问题假设的签名方案。·设计了多个紧致安全的基于身份的数字签名方案。根据Bellare等人提出的从标准数字签名方案到基于身份的数字签名方案的通用构造,将我们的基于DCR假设,矩阵DDH假设,Ring-LWE假设和子集和问题假设的紧致m-cma安全签名方案应用到通用构造中,分别得到基于DCR假设,矩阵DDH假设,Ring-LWE假设和子集和问题假设的紧致(弱)安全的基于身份的数字签名方案。·使用线性同态签名,设计了第一个可公开验证,支持动态更新且在标准模型下安全的可取回证明方案的通用构造。我们基于线性同态签名,给出了第一个可公开验证、支持动态更新且在标准模型下安全的可取回证明方案的通用构造。然后,将通用构造中的线性同态签名实例化为Kiltz等人所提出的的数字签名方案,我们得到了标准模型下基于矩阵DDH假设的可公开验证的动态可取回证明方案。除此之外,我们进一步拓展我们的可取回证明方案,使其支持编码过程的外包,进一步减轻了用户的本地计算负担。