基于辫群的多签名体制方案

唐建民 

（重庆工商大学派斯学院，重庆  401520）

摘  要：利用公开密钥算法对一段消息进行数字签名，这是签名方案中最常用的一种方法，它在理论上发展的已经比较完善，结合辫群中的困难问题对基于单向环同态而构造的多签名方案进行改进，把组合群论思想和多签名方案结合起来，提出一个新的多签名方案。

关键词：密码学；公开密钥；多重签名；安全性；辫群

中图分类号：G633    文献标识码：A        文章编号：

利用公开密钥算法对一段消息进行数字签名，这是签名方案中最常用的一种方法，它在理论上发展的已经比较完善，在实际应用中也有成熟的体制。比如说由RSA加密算法转化而成的数字签名、ElGamal签名方案、Schnorr签名算法、经过改进的Fiat-Shamir签名方案以及Guillon-Quisquater数字签名方案等等。这些数字签名的安全性或是建立在大整数分解的难度上，或是建立在计算离散对数的难度上，或是利用其他数论中的困难问题。不过这些方案都有一个特点，这些数字签名只是单个人对一份文件的签名，很少有签名方案可以拓展到多个人对同一份文件的签名上去。即使有，也只是简单的通过单签名加以迭代而得到的。但是由于实际应用的需要，对签名人数提出了更高的要求。现在需要一种新的签名方案，可以使多个人对同一份文件进行签名，这就是多签名。多签名有着广泛的应用，比如说一份文件必须有多个人签署才能执行，缺乏了其中任意一人的同意就不可以；或者是电子支票在银行、客户、商店之间转账时，银行、客户、商店为了使转账过程得以纪录，在每次交易时对同一份文件——支票进行数字签名，也需要利用多签名的技术。这些应用使得数字多签名方案的发展成为一种必然。为了满足着一要求，密码学家利用数学理论也构造了一系列多签名方案，其中比较实用且计算速度较快的是日本学者Eikoh Chida，Tako Nishizeki等基于单向环同态所构造的多签名方案。在本文中，除了介绍他们的多签名体制以外，我们还考虑利用辫群中的困难问题对基于单向环同态而构造的多签名方案进行改进，把组合群论思想和多签名方案结合起来，提出一个新的多签名方案。

一、数字多签名的安全性要求

多签名方案由于签名过程涉及了多个人，并且签名完成以后要求能检验所有人对同一消息的签名，所以在安全性方面比一般的数字签名有着更高的安全性要求。首先要求多签名能够抵抗外部攻击，

二、基于单向环同态的多签名体制

在文献[1,3]中，Eikoh Chida，Tako Nishzeki等首先提出了问题：在代数结构中除了群中存在单向群同态函数（即函数既是单向函数，也满足群中的同态运算）以外是否还有其它的单向函数同态，比如在环，幺半群中等。实际上，以前所构造的RSA加密算法、离散对数算法都是利用了基于单向群同态的单向陷门函数。而环同态对于这个问题的肯定回答，他们是构造了一个单向环同态来实现的。

如果A是交换环R（A，+， ），U是在加法+下的A-模，对于任意A和U，直和A U内的元素 和 ，可定义A U中的加法 ：（A U） （A U） A U和乘法*：（A U） （A U） A U如下：

= ； * = ；可以证明所得的（A U， ，*）是交换环。

利用这个交换环，Eikoh Chida等有进一步证明了单向环同态的存在性，这可以表述为下面这个定理：

定理：U，V都是有限交换群， =n，如果U和V内二进制运算是多项式内可计算的，如果存在单向群同态函数 ：U V，那么存在单向环同态F: 。（F的定义是：F( )=（ ）。）

为了构造适当的多签名体制，文献⑥中利用了 上的同态函数： : ， ，g是 的生成元，这个函数是单向的。运用上面的定理，可以得到单向环同态函数：F: ， 。关于文献中有根据上述函数而构造的多签名体制，在此不再详述。