基于格的密码体制作为后量子密码的主要候选者,具有广阔的应用前景和理论研究价值。除了具有抗量子计算特性以及能够实现全同态加密以外,基于格的密码体制的另一重要优势在于格密码能够提供worst-case下的安全性证明。具体来说,我们能够基于格中随机选取的困难问题实例Ⅱ来构造一个格密码方案,但攻破该方案与求解格中worst-case下的问题一样困难。而大整数分解和离散对数等经典问题则不具有这样的特性。本文主要研究基于格的Fiat-Shamir类数字签名方案。需要注意的是,由于格特殊的代数结构,此类格签名算法中签名的直接输出会导致签名密钥的信息泄露。因此,Fiat-Shamir格签名带有“异常终止(Aborts)”这个特有属性。其背后的思想是:为了隐藏签名密钥,签名者选择性地输出消息的签名。通过这样的处理,使得签名的输出服从某个已知的、与签名密钥无关的概率分布,或者服从某个更小范围的均匀分布。也就是说,当签名的输出可能会泄露签名密钥时,称之为异常,进而终止并重启签名算法。目前,与基于离散对数的数字签名相比,Fiat-Shamir格签名的研究存在下面两个问题:首先,格基签名的研究进展离实际应用还有一定的距离。其差距主要体现在两个方面:一是在效率上,格基签名的密钥长度、签名长度较大,而且异常终止的存在意味着在平均意义下,重复多次签名算法才能得到一个有效的签名。因此,如何减少签名的重复次数也是需要进一步研究的问题。二是格基签名涉及安全的参数较多,以及随着各种攻击算法的不断发展,这给评估在给定参数下具体安全强度造成较大的困难。其次,格签名常常面临另一个问题:由于Fiat-Shamir格签名存在异常终止,即允许签名者重启签名算法,这会对一些具有特殊性质的签名带来一些问题,甚至安全隐患。例如,对于在线/离线签名方案,由于重启签名算法会增加签名生成的运算时间,因此在构造这类签名算法时,要尽可能地把异常终止放在签名算法的离线阶段,以成倍地减少签名的在线运算时间。再比如对于Fiat-Shamir格基盲签名方案,用户在签名异常时有权利要求签名者重启签名协议。但此时需要防止一些恶意的用户尽管已经得到了一个有效的签名,但仍然要求签名者重启签名协议。鉴于格签名目前在上述两个方面仍存在一些挑战,因此,本文以此作为切入点,重在设计具有较小签名长度、公钥长度和重复次数的Fiat-Shamir格签名方案。与此同时,并着重解决异常终止在格签名(尤其具有特殊性质的签名)中所带来的新的问题。具体地,本文的研究内容主要包括以下几个方面:1.首先总结了两类Fiat-Shamir格签名的一般构造:涉及均匀分布和窄分布的拒绝抽样格签名。这两类签名的主要区别在于隐藏签名私钥时所使用的技术手段不同。一般而言,涉及均匀分布的拒绝抽样格签名只需要均匀抽样,因此比较容易实现,但其签名长度较大。而涉及窄分布的拒绝抽样格签名常常使用“窄”的概率分布,因此具有比较小的签名长度。但相对而言,其概率分布的抽样变得更加困难,如高斯抽样容易受到侧信道攻击。本文在第四章提出的涉及中心二项分布的拒绝抽样算法则是一个较为理想的替代者,不仅容易抽样,还不易受到各种算法攻击。2.提出了一个新的涉及中心二项分布的拒绝抽样算法,并以此提出了第一个涉及中心二项分布的拒绝抽样格签名方案。从一定程度上来说,该签名方案兼具两类Fiat-Shamir格签名各自的独特优点。这是由于它不仅能够较容易地实现安全抽样,而且在所有不使用高斯分布的格签名中,该方案在128比特量子敌手强度下有最小的签名和公钥长度。3.利用本文格签名一般构造的底层身份认证协议,本文还构造了一个格基后量子盲签名方案。相对于之前的格基盲签名方案,本文方案的签名长度在同一安全强度下减小了近一半。在构造此类格基盲签名方案时,由于交互协议各个阶段的输出均存在异常终止,因此用户在异常时有权利要求重启签名协议。但此时会出现另外一问题:某些恶意的用户尽管已经得到了一个有效的签名,但仍然要求签名者重启签名协议。因此在交互协议的最后,用户无论是否已经得到了有效的签名,都需要发送某些信息(不能泄露消息和对应的盲签名)给签名者。然后签名者验证该用户是否已经真正地得到了一个有效的签名,以决定是否重启签名协议。4.异常终止的出现给格上的Fiat-Shamiir在线/离线签名带来了新的问题,即一个格签名方案要尽量减少异常终止在在线签名阶段出现的次数,以此来减少在线阶段的签名时间。为了解决这个问题,本文提出了第一个基于格的r-签名方案,且这类签名在缩短在线阶段的签名时间方面有显著的内在优势。该方案的最大优势是在签名算法的在线阶段只存在一个异常终止,因此成倍地减少了签名的在线计算时间。方案的构造技巧部分参照了 qTESLA签名方案,但我们的设计思路不同于qTESLA签名,而是利用了r-签名的思想,把qTESLA的一个在线异常终止移除到了离线签名阶段。另外,相对于一般的签名,Γ-签名还具有更强的可证安全性、签名聚合性以及隐私保护认证功能。