生成无密钥数字多重签名的系统和方法

摘要

提供了一种生成无密钥数字多重签名的方法。该方法包括：从一个或多个客户端计算机接收多重签名生成请求，基于该签名生成请求构建子树，并构建包括该子树的搜索树。该方法还包括分配显式长度标记到该搜索树的叶节点以平衡该搜索树并应用哈希函数到该搜索树的每个节点。根哈希值和该搜索树的高度构成生成的总签名请求，然后接收基于该总签名请求的总签名。无密钥数字多重签名基于该总签名生成并包含隐含长度标记以验证签名生成请求的数量受到了限制。如果该搜索树的高度没有超过预定的高度限制，则该总签名被生成。

权利要求

1.一种生成无密钥数字多重签名的方法，包括：

在第一计算机接收多个签名生成请求，其中每个所述多个签名生成请求包括数据、客户端计算机标识符和树高度标记，其中所述树高度标记表示包含在签名生成请求中的树的高度；

构建搜索树，所述搜索树包括根节点和多个叶节点，其中所述多个叶节点包括所述多个签名生成请求，并且每个叶节点对应一个签名生成请求；

对每个所述多个叶节点和所述根节点应用第一哈希函数以为每个所述多个叶节点和所述根节点计算哈希值；

生成包括所述根节点的所述哈希值和搜索树高度标记的总签名请求；

为了生成总签名和所述无密钥数字多重签名发送所述总签名请求；

如果所述搜索树高度标记没有超出高度限制，接收所述总签名，所述总签名包括隐含长度标记，所述隐含长度标记用于确保接收的签名生成请求的数量在限度之内；以及基于所述总签名以及所述多个签名生成请求中的所述数据和所述客户端计算机标识符，生成对应于所述多个签名生成请求的无密钥数字多重签名。

2.如权利要求1所述的方法，其特征在于：所述发送所述总签名请求包括：将所述总签名请求发送到与所述第一计算机通信的第二计算机；所述方法还包括：如果所述搜索树高度标记没有超过所述高度限制，则基于所述总签名请求在所述第二计算机中生成所述总签名；

发送所述总签名到所述第一计算机。

3.如权利要求2所述的方法，其特征在于：所述在所述第二计算机中生成所述总签名包括：对所述根节点的所述哈希值和在所述总签名请求中的所述搜索树高度标记以及时间戳和数字签名应用第二哈希函数，其中所述时间戳标明所述总签名的生成时间。

4.如权利要求1所述的方法，其特征在于，还包括：

如果所述搜索树高度标记没有超过所述高度限制，则基于所述总签名请求在所述第一计算机中生成所述总签名。

5.如权利要求4所述的方法，其特征在于：在所述第一计算机中生成所述总签名包括：对所述根节点的所述哈希值和在所述总签名请求中的所述搜索树高度标记以及时间戳和数字签名应用第二哈希函数，其中所述时间戳标明所述总签名的生成时间。

6.如权利要求1所述的方法，其特征在于：所述总签名还包括第一哈希链，所述第一哈希链包括所述根节点和所述多个叶节点中的叶节点。

7.如权利要求1所述的方法，其特征在于：所述总签名包括公开哈希值，所述公开哈希值包括时间戳和位置信息，其中所述时间戳标明所述总签名的生成时间，所述位置信息与所述哈希值在何时和何地被公开相关。

8.如权利要求1所述的方法，其特征在于：所述构建搜索树包括：基于所述多个签名生成请求建立子树，其中所述子树对应所述多个签名生成请求中的客户端计算机标识符；

构建包括所述子树的搜索树。

9.如权利要求8所述的方法，其特征在于：还包括：基于在每个所述多个签名生成请求中的客户端计算机标识符将所述多个签名生成请求分组成在分类数据库中的分组请求，其中所述分组请求具有共同的客户端计算机标识符。

10.如权利要求9所述的方法，其特征在于：所述建立子树包括：为在所述分类数据库中的具有共同的客户端计算机标识符的所述分组请求建立所述子树。

11.如权利要求1所述的方法，其特征在于：还包括：为每个所述多个叶节点分配显式长度标记，每个所述显式长度标记基于在每个所述多个签名生成请求中的所述树高度标记，其中所述分配显式长度标记包括：分配所述显式长度标记给每个所述多个叶节点使得所述搜索树保持平衡。

12.如权利要求11所述的方法，其特征在于：所述搜索树高度标记基于所述多个签名生成请求中的所述树高度标记和被分配给所述多个叶节点的所述显式长度标记。

13.如权利要求1所述的方法，其特征在于：所述搜索树还包括在所述根节点和所述多个叶节点之间的多个中间节点。

14.如权利要求13所述的方法，其特征在于：所述应用第一哈希函数还包括：对每个所述多个中间节点应用所述第一哈希函数。

15.如权利要求1所述的方法，其特征在于：所述应用第一哈希函数包括：确定所述搜索树的第一节点是否是所述多个叶节点中的一个；

如果所述第一节点是所述多个叶节点中的一个，则应用所述第一哈希函数到所述第一节点的数据、客户端计算机标识符、树高度标记和显式长度标记以产生所述哈希值；以及如果所述第一节点不是所述多个叶节点中的一个，则应用所述第一哈希函数到左侧子节点哈希值、右侧子节点哈希值和所述第一节点的客户端计算机标识符以产生所述哈希值，其中：所述左侧子节点哈希值包括连接到所述第一节点的第二节点的哈希值；

所述右侧子节点哈希值包括连接到所述第一节点的第三节点的哈希值。

16.如权利要求1所述的方法，其特征在于：生成所述无密钥数字多重签名包括：从所述搜索树中提取最小子树，所述最小子树对应所述多个签名生成请求中的一个签名生成请求，所述最小子树包括：所述搜索树的根节点；以及

所述搜索树的所述多个叶节点中对应所述多个签名生成请求中的所述一个签名生成请求的第二节点；

从第二哈希链计算根节点哈希值，所述第二哈希链包括所述第二节点和所述根节点；

用所述第二哈希链的步骤的数量填充所述总签名的所述隐含长度标记；以及生成包括所述根节点哈希值、被填充的所述隐含长度标记和所述第二哈希链的无密钥数字多重签名。

17.如权利要求16所述的方法，其特征在于：所述计算根节点哈希值包括：应用所述第一哈希函数到所述第二节点的数据、客户端计算机标识符和树高度标记以产生叶节点哈希值；以及应用所述第一哈希函数到所述叶节点哈希值以产生所述根节点哈希值。

18.如权利要求16所述的方法，其特征在于：所述搜索树还包括在所述根节点和所述多个叶节点之间的多个中间节点，其中所述最小子树还包括：所述搜索树的搜索关键节点，所述搜索关键节点包括所述搜索树的所述多个中间节点中的位于从所述根节点到所述多个叶节点中对应所述多个签名生成请求中的所述一个签名生成请求的所述第二节点的直接路径上的一个或多个节点；以及所述搜索关键节点的兄弟节点的多个第一哈希值的兄弟哈希值，所述兄弟节点连接到所述搜索关键节点。

19.如权利要求18所述的方法，其特征在于：所述计算根节点哈希值包括：应用所述第一哈希函数到所述第二节点的数据、客户端计算机标识符和树高度标记以产生叶节点哈希值；以及应用所述第一哈希函数到所述叶节点哈希值和所述兄弟哈希值以产生所述根节点哈希值。

说明书

生成无密钥数字多重签名的系统和方法

技术领域

[0001] 本发明一般地涉及数字签名的创建。更具体地，本发明涉及生成用于数字数据的无密钥数字多重签名(keyless digital multi-signatures)的系统和方法。

背景技术

[0002] 数字签名常用来认证数字数据，比如文件、报文、财务信息以及其它数据。当一块数据被数字签名，该数据的接收者可以验证该数据来自于特定的发送者，通称为签名者，以及该数据从其被签名后没有被修改。数字签名也可以在数据被创建时或数据被发送时进行验证。现有的数字签名方案使用公钥密码，其中签名者使用私人密钥创建数字签名，与该私人密钥配对的公钥被用来验证该数字签名。公钥与使用公钥证书的签名者的身份绑定，而该公钥证书由在这种公钥基础设施(public-key infrastructure)方案中的受信任的认证机构(Certificate Authority)发布。接收者使用该公钥证书来验证该数字签名。

[0003] 但是，这些现有的数字签名方案有一些缺点。只要私人密钥被发布，签名者可以使用该私人密钥产生无限数量的数字签名。更重要地，如果该私人密钥失窃，则未被授权的实体也可以作为签名者生成并分发合法的数字签名。在这种情况下，合法的签名者可以尝试作废该私人密钥，但是很难确定在该私人密钥丢失和该私人密钥被作废之时之间的时间段内是否已经有伪造的签名被创建。验证先前创建的签名是否是有效的也变得更加复杂，因为与那些签名关联的私人密钥已经被作废。而且，由于私人密钥的创建不受签名者的控制，因此现有的数字签名方案依赖于认证机构的可信度。如果认证机构泄密，则基于该认证机构发布的私人密钥创建的数字签名将是可疑的。因此，签名者必须给予认证机构无条件的信任。

[0004] 其它的数字签名方案试图通过在合法签名者和服务器之间共享私人密钥来减少如果私人密钥失窃时未被授权的实体创建数字签名的风险。但是公钥密码仍然包含在这种服务器支持的数字签名方案中，私人密钥仍然可以被未被授权的实体泄露。还有其它的数字签名方案使用试图减少在私人密钥丢失和该私人密钥被作废之时之间的时间段内的风险的时间戳服务。但是，这种类型的方案只支持公钥基础设施和前文详述的与它相关联的风险。并且，由于可能不知道私人密钥何时丢失或被盗，因此在该私人密钥被作废之前仍然可能有伪造的签名被创建。

[0005] 此外，一些现有的数字签名方案不依赖公钥和/或私人密钥，而是使用能够一次支持来自于客户端计算机的单个签名请求的签名生成服务器。在一个方案中，无密钥数字签名服务提供商运行顶层的签名生成服务器，该顶层的签名生成服务器与较低层的服务器通信，该较低层的服务器可以被其它实体运行，比如该服务提供商的客户。该服务提供商可能希望针对在该顶层签名生成服务器中生成的签名向该较低层服务器的运行者收费。在这种方案中，一次产生的无密钥签名的数量可能不容易被追踪或限制。当验证生成的签名时可以执行检查哈希链的总长度来追踪生成的签名的数量，但是这将要求所有的客户在生成的签名的数量上有相同的最大限额。在这种方案中不同客户的需求无法被满足。

[0006] 另一种限制顶层签名生成服务器生成的签名的数量的方法是当验证生成的签名时在哈希链中的每个步骤包括一个数字标记。对生成的签名的数量的限制可以为每个客户不同地设置，因此不会所有的客户必须具有相同的最大限额。在这种方案中，当签名被验证时，为了成功地验证该签名，将检查数字标记以确保它们是严格地按升序排列的，也就是说，每个数字标记必须比哈希链中前一个步骤的数字标记大。但是，客户服务器可能在这种方法中回避检查该数字标记以避开对生成的签名的数量的限制，而剩余的签名将仍然能够成功地验证。

发明内容

[0007] 本发明提供来基于从一个或多个客户端计算机接收多个签名生成请求而生成无密钥数字多重签名。通过同时处理多个签名请求，本发明实现了更有效率和更快地生成无密钥数字签名。而且，本发明可以限制一次能够被生成的签名的数量从而追踪和/或限额客户端计算机为记账或其它目的而请求的签名。本发明一个实施例中，揭露了一种生成无密钥数字多重签名的系统和方法，其中服务提供商的计算机接收来自于客户端计算机的多个签名生成请求。构建包括每个客户端计算机的子树的搜索树。该搜索树的叶节点与每个签名生成请求对应。该搜索树通过给该搜索树的叶节点根据需要指定显式长度标记而保持平衡。通过对节点应用哈希函数，该搜索树中的每个节点的哈希值被计算出来。搜索树的根节点的哈希值和搜索树高度标记组成总签名请求。该总签名请求产生将在服务提供商计算机中被创建和接收的总签名。只有当搜索树高度标记没有超过高度限制时，该总签名才被创建。针对签名生成请求的无密钥数字多重签名基于该总签名生成。当该无密钥数字多重签名被生成并验证时，在该总签名中的为空的隐含长度标记被填充，以使得签名生成请求的数量受到限制。其它的特征和优点将通过下文中的描述和附图进行说明。

附图说明

[0008] 图1为生成无密钥数字多重签名的方法的整体流程图；

[0009] 图2为显示在图1中的生成操作中对搜索树的节点应用哈希函数的流程图；

[0010] 图3为显示在图1中的生成操作中生成总签名的流程图；

[0011] 图4为显示在图1中的生成操作中接收总签名后生成无密钥数字多重签名的流程图；

[0012] 图5A-5D显示了根据本发明实施例的签名生成请求和构建的结果的哈希树；

[0013] 图6A-6B显示了根据本发明实施例的对哈希树的节点应用哈希函数；

[0014] 图7A-7B显示了根据本发明实施例的与无密钥数字多重签名的生成关联的哈希树；

[0015] 图8显示了根据本发明实施例的与无密钥数字多重签名的生成相关的哈希链和无密钥数字多重签名。

具体实施方式

[0016] 本发明容许很多不同形式的实施例，附图中所示的和将在此进行详细描述的是本发明的优选的实施例，应当理解，当前揭露的内容将被认为是本发明的原理的实例，而不是想要将本发明的主要方面限制到这些描述的实施例上。

[0017] 图1显示了生成无密钥数字多重签名的流程100的优选的实施例。该流程100的结果是响应从一个或多个客户端计算机接收的多重签名生成请求创建无密钥数字多重签名。该流程100可以在单个的服务器上或者在相互之间电气通信的多个服务器上实现。在一个实施例中，该服务器可以由为一个或多个客户端计算机创建数字无密钥多重签名的单个服务提供商和/或其它服务提供商运行。另一个实施例中，父服务器可以由服务提供商运行而与该父服务器通信的子服务器可以由其它的实体运行。本实施例中，该子服务器可以将签名生成请求发送到父服务器。该父服务器然后可以生成无密钥数字多重签名并将该无密钥数字多重签名发送回子服务器。

[0018] 该服务器可以包括适宜的处理器，如本领域内技术人员所熟知的一样。该处理器可操作地连接到至少一个存储设备，比如硬盘或闪存或其它适宜的存储设备，这些存储设备可以包括易失性存储器元件(例如，随机存取存储器(RAM，比如动态随机存取存储器(DRAM)、静态随机存取存储器(SRAM)、同步动态随机存取存储器(SDRAM)等等))和非易失性存储器元件(例如，只读存储器(ROM)、硬盘、磁带、光盘只读存储器(CDROM)等等)中的任意一个或其结合。而且，该存储设备可以结合电子的、磁的、光的和/或其它类型的存储介质。该存储设备可以具有分布式结构，其中不同的元件彼此远离设置，但是仍然可以被处理器存取。

[0019] 本发明的步骤和/元件，和/或它们的部分可以使用源程序、可执行程序(目标代码)、脚本或任何其它包括一系列将被执行的指令的实体实现。当为源程序时，该程序需要通过可以包括在或未包括在存储器中的编译器、汇编器、解释器或类似程序进行翻译，以便连同操作系统(O/S)正确地运行。此外，实现本发明的软件可以用下述语言编写：(a)面向对象的编程语言，其具有数据类和方法类；或(b)面向过程的编程语言，其具有例行程序、子例行程序和/或函数，例如但不限于C、C++、Pascal、Basic、Fortran、Cobol、Perl、Java和Ada。

[0020] 当服务器在运行中时，处理器用于执行存储在存储设备中的软件、对存储设备进行数据存取、以及通常按照该软件控制服务器的运行。本发明的软件方面和操作系统整体地或部分地，但是典型地为后者，被处理器读出，或许在处理器中被缓冲，然后被执行。

[0021] 当本发明或其一些方面在软件中实现时，应该注意到该软件可以被存储在任何计算机可读介质上以被或连同任何计算机相关的系统或方法使用。在本文的上下文中，计算机可读介质是能够容纳或存储用于被或连同计算机相关的系统或方法使用的计算机程序的电子的、磁的、光的或其它物理的设备或装置。本发明可以在任何计算机可读介质中实现以用于被或连同指令执行系统、装置或设备使用，比如基于计算机的系统、包含处理器的系统或能够从指令执行系统、装置或设备取得指令并执行指令的其它的系统。在本文的上下文中，“计算机可读介质”可以是任何能够存储、通信、传播或传送用于被或连同指令执行系统、装置或设备使用的程序的装置。该计算机可读介质可以是，例如但不限于：电子的、磁的、光的、电磁的、红外的或半导体的系统、装置、设备或传播介质。计算机可读介质的更详细的例子(非无遗漏的清单)将包括：具有一条或多条导线的电气连接(电子的)、便携式计算机磁盘(磁的)、随机存取存储器(RAM)(电子的)、只读存储器(ROM)(电子的)、可擦除可编程只读存储器(EPROM、EEPROM(电可擦除可编程只读存储器)或闪存存储器)(电子的)、光纤(光的)和便携式光盘只读存储器(CDROM)(光的)。注意到该计算机可读介质甚至可以是程序打印于其上的纸或其它的适宜的介质，该程序可以通过例如光学扫描该纸或其它介质而被电子地捕获，然后被编译、解释或如果需要以适宜的方式不同地处理，然后被存储到计算机存储器中。

[0022] 为了在服务器之间和/或在服务器和客户端计算机之间通讯，服务器中设有网络通信设备和电路。在一个优选的实施例中，该网络通信设备包括网卡，比如以太网卡。在一个优选的网络环境中，每个服务器设置为使用传输控制协议/互联网协议(TCP/IP协议)通过网络301进行通信。但是，可以理解，还可以使用多种网络协议，比如互联网分组交换/顺序分组交换(IPX/SPX)协议、网件(Netware)、点对点协议(PPP)和其它的网络协议。无线网络连接也是可以考虑的，比如无线以太网(wireless Ethernet)、卫星网(satellite)、红外(infrared)和射频(radio frequency)网络。

[0023] 参见图1，在流程100的步骤102，服务提供商计算机可以从一个或多个客户端计算机接收多个签名生成请求502。每个该签名生成请求502可以包括数据504、树高度标记506和客户端计算机标识符508，如图5A所示。例如，在图5A中，第一签名生成请求502具有数据504：x(1)、树高度标记506：4和客户端计算机标识符508：“AA”。数据504可以表示任何类型的能够用无密钥数字多重签名签署的数字信息。数据504可以包括文件、电子邮件或任何其它类型的数字化表现的信息。树高度标记506表示包含在签名生成请求502中的树的高度。
当在流程100中的后续步骤中创建搜索树524时，该签名生成请求502中的树的高度将被考虑进去，以使得该搜索树524保持恰当的平衡的平衡。该树的根哈希值可以包含在签名生成请求502中以表示与该数据504相关的多重签名生成请求。客户端计算机标识符508是发出签名生成请求502的客户端计算机的唯一标识。该客户端计算机标识符508可以是文本、数字、字母数字混合或其它的识别客户端计算机的表征。

[0024] 在步骤104，签名生成请求502可以根据它们各自的客户端计算机标识符508进行分组。在一个优选的实施例中，该签名生成请求502可以存储在分类数据库中。在图5A的例子中显示了三个客户端计算机标识符508：AA、AB和BB。签名生成请求502被客户端计算机标识符508按字母顺序分组。如果客户端计算机标识符508使用了其它的表征，可以使用标识符508的任何顺序关系将签名生成请求502分组进分类数据库中。

[0025] 每个客户端计算机的子树可以在步骤106建立。该子树可以基于在步骤104执行的该签名生成请求502的分组而建立。特别地，每个子树的叶节点每个被分配一个签名生成请求502。如从图5B中的例子可见的一样，具有为每个客户端计算机标识符AA、AB和BB分别建立的三个子树510、512和514。在子树510、512和514中的叶节点516具有分配给它们的签名生成请求502。对于客户端计算机标识符AA和AB的子树510和512，还具有另外的节点518，该节点518将是将在流程100的后续步骤中构建的搜索树524的中间节点。

[0026] 在步骤108中，可以构建搜索树骨架522并将子树分配到该搜索树骨架522以构建搜索树524，如图5C和5D中的例子所示。图5C中的搜索树骨架522包括来自于子树510、512和514的中间节点518以及叶节点“＝BB”516。该叶节点“＝BB”516被包含在搜索树骨架522中，因为它是在步骤106中构建的客户端计算机标识符BB的子树514。搜索树骨架522被用来主要基于搜索树524的叶节点516中的客户端计算机标识符508的词典特征(lexicographical characteristics)而连接子树510、512和514。图5D中的例子所示的搜索树524基于子树
510、512和514以及搜索树骨架522构建。该搜索树524包括叶节点516、中间节点518和根节点520。通过对该搜索树524的每个节点应用哈希函数，可以生成总签名请求528，下文将进一步详细描述。在图5D的搜索树524中与中间节点518相关的标记“＝AA”、“＝AB”和“＝BB”是分配给该中间节点518的搜索关键字。每个中间节点518的子节点和孙节点具有与各自的中间节点相同的客户端计算机标识符(例如，AA、AB或BB)。例如，具有搜索关键字“＝AA”的中间节点518具有两个子节点，每个子节点具有客户端计算机标识符AA。

[0027] 在步骤110，显式长度标记526被分配到每个叶节点516以平衡该构建的搜索树524。流程100重复步骤110和112直到所有的叶节点都被分配了显式长度标记526。该显式长度标记526可以为0或不为0。搜索树524可能会由于签名生成请求502中的树高度标记506和/或由于包含在搜索树524中的单个的哈希链的长度而不平衡。由于包含在每个签名生成请求502中的树，树高度标记506增加了搜索树524的高度。

[0028] 如从图5D中的例子可见的一样，最高的高度来自于签名生成请求502：x(3)和x(4)。特别地，签名生成请求502：x(3)具有为4的树高度标记506而签名生成请求502：x(4)具有为3的树高度标记506，但是该签名生成请求502：x(4)在搜索树524中是比签名生成请求502：x(3)低的层级。由于这些树高度标记506，在分配任何显式长度标记526之前，搜索树
524的高度为7。但是，为了恰当地平衡该搜索树524，在需要时显式长度标记526被分配到叶节点516。在图5D所示的例子中，不为0的显式长度标记526需要被分配给签名生成请求502：
x(1)、x(5)和x(6)以使得从这些各自的叶节点516到根节点520的高度为7。也就是说，在步骤110和112，显式长度标记526的分配考虑了叶节点516在搜索树524中所处的层级以及在签名生成请求502中的树高度标记506。

[0029] 搜索树524的所有节点的哈希值可以在步骤114计算，这将参考图2进行进一步详细说明。在步骤202，检查搜索树524的一个确定的节点。在步骤204，取决于该节点是叶节点516还是非叶节点(中间节点518或根节点520)，步骤114中的该流程分别走向步骤206或步骤210。如果该节点是叶节点516，在步骤206，哈希函数602可以被应用到基于数据504、树高度标记506、客户端计算机标识符508和显式长度标记526的叶节点516。图6A显示了签名生成请求502：x(5)的例子。结果的哈希值604y可以在步骤208被分配给该确定的叶节点516。
但是，如果在步骤204中被检查的节点是非叶节点518、520，则哈希函数602可以被应用到客户端计算机标识符508以及连接到该非叶节点518、520的左侧子节点和右侧子节点606的哈希值。一个例子显示于图6B。该非叶节点可以包括中间节点518或根节点520。结果的哈希值
608y可以在步骤208被分配给非叶节点518、520。该哈希函数602可以包括安全哈希算法-1(SHA-1)、安全哈希算法2-224(SHA2-224)、安全哈希算法2-256(SHA2-256)、安全哈希算法
2-384(SHA2-384)、安全哈希算法2-512(SHA2-512)、成熟信息-摘要算法-160(RIPEMD-160)和其它密码哈希函数。

[0030] 最后，只要搜索树中所有其它的节点的哈希值已经计算出来，就可以计算出搜索树524的根节点520的根哈希值530r。该根哈希值530r表示并包括搜索树524中所有其它节点的哈希值。在步骤116，总签名请求528可以被计算出并包括根哈希值530r和搜索树高度标记532。在图5D所示的例子中，搜索树高度标记532为7，该“7”是搜索树524的高度，包括签名生成请求502中的树高度标记506和显式长度标记526。

[0031] 总签名请求528可以在服务提供商计算机被处理或可以被传送到与该服务提供商计算机通信的父服务器。在流程100的步骤118，总签名700可以基于该总签名请求528被生成并接收，如将参考图3进行进一步详细描述的一样。在步骤118的流程的步骤302中，总签名请求528可以如前文所述的一样在本地相同的计算机或在父服务器被接收。在步骤304检查搜索树高度标记532以确定它是否超出了预先确定的高度限制。该高度限制可以被设置用以给客户端计算机可以要求产生的签名的数量设置上限或因为效率、已有工作负荷或其它的原因限制可以被处理的签名的数量。该高度限制也可以由父服务器分配到服务提供商计算机以控制能够被服务提供商计算机卖出的服务的数量，例如，可以被服务提供商计算机生成的签名的数量。当服务提供商计算机是由父服务器提供的签名生成服务的经销商时这种情况可能发生。

[0032] 在步骤304中如果搜索树高度标记532超出了预定的高度限制，则在步骤310，该总签名请求528可以被忽略并不再处理。在这种情况下，总签名700和无密钥数字多重签名800将不会生成。但是，在步骤304中如果搜索树高度标记532小于或等于预先确定的高度限制，则在步骤306中生成总签名700。在步骤306中，该搜索树高度标记532也可以被包括在搜索树524中。在步骤308中，取决于哪个计算机处理该总签名请求528，该总签名700被在服务提供商计算机内传送或被从父服务器传送到服务提供商计算机。

[0033] 在一些实施例中，总签名700可以具有与搜索树524相同的哈希树结构。但是，哈希函数被应用到搜索树524的节点的哈希值，包括根哈希值530r和搜索树高度标记532，以生成总签名700。该总签名700还可以包括比将在无密钥数字多重签名800中出现的哈希链更短的哈希链。用于生成总签名700的哈希函数可以是与用于在搜索树524中产生哈希值的哈希函数相同或不同的确定的函数。在该总签名700中还可以混入时间戳以标明该总签名700生成的日期和时间。该总签名700可以响应总签名请求528的接收而被数字化地签署。应用到该总签名请求528的数字签名可以基于公钥加密方案、公钥/私人密钥加密方案或能证明签名的发布者的身份的任何其它方案。在总签名700中可以包括唯一的序列号。在该总签名700中还可以包括隐含长度标记732并且当该总签名700生成时该隐含长度标记732可以初始地被设为空白。当在该无密钥数字多重签名800生成和/或验证时计数哈希计算步骤的数量时，该隐含长度标记732可以被填充。该隐含长度标记732中填充的值可以与搜索树高度标记532比较以确保客户端计算机发送的签名生成请求的数量在限度之内。在其它的实施例中，总签名700可以包括具有时间戳和关于该哈希值何时和何地被公开的位置信息的公开哈希值。例如，该时间戳和位置信息可以被混入该公开哈希值中。该公开哈希值可以作为附加的数据结构被加入无密钥数字多重签名800中以实现该无密钥数字多重签名800的更好的可提取性。

[0034] 如果客户端计算机试图发送具有比在签名生成请求502中的树的实际高度小的树高度标记506的签名生成请求502，必须被填充以帮助保证对客户端计算机的签名生成的限制的隐含长度标记732将起作用。例如，如果客户端计算机试图在该树中增加具有虚假高度的外部数据结构，这将是存在故意滥用签名生成服务的证据。

[0035] 无密钥数字多重签名800的生成在步骤120执行，将参考图4进行进一步详细描述。在图4中所示的步骤120的流程的步骤402，签名生成请求502的最小子树752可以被从总签名700中提取出。该最小子树752可以基于总签名700中的树以及该树的对应特定签名生成请求502的特定的叶节点被提取。在图7A和7B中所示的总签名700包括叶节点716、中间节点
718和根节点720。签名生成请求702和显式长度标记726被分配给并混入叶节点716。如前文所述的一样，虽然该总签名700可以具有与搜索树524相同的哈希树结构，但是由于哈希函数的应用、时间戳的加入和总签名700的数字签署，该总签名700的节点的哈希值与搜索树
524的节点的哈希值不同。

[0036] 在图7B所示的例子中，显示了客户端计算机标识符AB的签名生成请求702：x(5)的最小子树752。该最小子树752包括位于从根节点720到对应于该签名生成请求702：x(5)的叶节点716的直接路径上的节点。特别地，图7B中所示的最小子树752包括中间节点718“AB”、“BB”、“＝AB”和“＝AB”。这些节点也是该最小子树752的上下文中的搜索关键节点。该最小子树752还包括连接到搜索关键节点718的兄弟节点754的哈希值756。该兄弟哈希链值756包括没有位于从根节点720到叶节点716的直接路径上但是是总签名700的一部分的兄弟节点754的哈希值。该兄弟哈希链值756是计算根哈希值730y所需要的。在步骤404，该最小子树752可以被表示为哈希链850，比如像图8所示的无密钥数字多重签名800中的一样。
该无密钥数字多重签名800包括根哈希值730y、隐含长度标记732和哈希链850。搜索树524的根哈希值530r等于根哈希值730y。

[0037] 在步骤406，检查哈希链850的节点，在步骤408，可以确定该被检查的节点是否对应叶节点716。如果该节点对应一个叶节点716，则在步骤410，哈希函数802被应用到签名生成请求702中的数据704、树高度标记706、客户端计算机标识符708和显式长度标记726。在步骤412，结果的哈希值被分配到该节点。在步骤408如果该节点没有对应一个叶节点，则在步骤418，该哈希函数802被应用到搜索关键节点718的搜索关键标识符804(“＝AB”、“BB”和“AB”)和连接到该非叶节点的左侧子节点和右侧子节点的哈希值，随后在步骤412，将结果的哈希值分配给该非叶节点。在步骤414，如果在哈希链850中还留有另外的节点，则步骤120的该流程返回到步骤406以计算剩余的节点的哈希值。该哈希函数802可以是与用来计算在搜索树524和/或总签名700中的哈希值的哈希函数相同或不同的确定的函数。在步骤
414如果在哈希链850中没有剩余的节点，则在步骤416中计算无密钥数字多重签名800。最后处理的节点是根节点720，结果的根节点哈希值730y、隐含长度标记732和哈希链850构成了该无密钥数字多重签名800。该隐含长度标记732可以通过计数该哈希链850中的步骤的数量而计算出来。

[0038] 在图8所示的例子中，完整的哈希链850从在图8底部的签名生成请求702：x(5)开始描述直到在图8顶部的根哈希值730。在哈希链850中的每个计算步骤，从签名生成请求702：x(5)中的信息开始，哈希函数802被应用。在每个连续的计算步骤，兄弟哈希值756、搜索关键标识符804和来自先前的哈希函数步骤的结果哈希值806被哈希函数802混合，直到根哈希值730被计算出来。关于该哈希链850的隐含长度标记732，在每个计算步骤，树的高度从签名生成请求702中为1的显式长度标记726开始计算。在第一个计算步骤中，加上签名生成请求702中的为2的树高度标记706产生为3的中间高度856。在图8所示的例子中，对于每个连续的计算步骤，加上另外的为1的高度以产生连续的中间高度856。该被加上的另外的高度可以是另外的值，取决于涉及的特定的节点是否具有非0的显式长度标记726。当到达根节点时，在该哈希链850中步骤的总数被置入隐含长度标记732中。在图8的例子中，该隐含长度标记被计算出为7。这样，无密钥数字多重签名800为签名生成请求702中的一个签名生成请求生成，并包含了根哈希值730、被填充了的隐含长度标记732和哈希链850。

[0039] 在一些实施例中，哈希链的计算在无密钥数字签名800的验证过程中进行。在图8中所示的哈希链850中的每个计算步骤中，当哈希函数被应用时，客户端计算机标识符708可以与搜索关键标识符804比较，以保证签名生成请求702处在总签名700的哈希树中最小子树752被从该处提取出的正确的位置。换句话说，哈希链850中的计算步骤的顺序被检查以保证它与在分类数据库中的签名生成请求702的顺序一致。如前文所述，签名生成请求702可以按客户端计算机标识符708的字母顺序或按其它的顺序关系分组。在图8的例子中，搜索关键标识符804“＝AB”和“AB”与客户端计算机标识符708“AB”比较以确定它们是相同的。搜索关键标识符804“BB”被比较以检查它是否“大于”客户端计算机标识符708“AB”。在这个例子中，基于它们的字母顺序，“BB”是“大于”“AB”的。这也可以见于总签名700的哈希树中，在其中具有客户端计算机标识符“BB”的签名生成请求702位于具有客户端计算机标识符“AB”的签名生成请求702的右边。

[0040] 在图中的任何流程描述或流程框应该被理解为表示包括一个或多个用于实现流程中特定的逻辑功能或步骤的可执行指令的模块、程序段或代码部分，替代的实现方式被包括在本发明的实施例的范围中，其中的各功能可以按照与前文所示或讨论的顺序不同的顺序执行，包括大体上并行的或相反的顺序，取决于涉及的功能，如将被本领域普通技术人员理解的那样。

[0041] 应该强调，前文描述的本发明的实施例，特别是任何“优选的”实施例，是可能的实现的实例，仅仅是在为了清楚地理解本发明的原理而描述。在不实质性地背离本发明的精神和原理的情况下，还可以对本发明的前文所描述的实施例做很多变更和修改。所有这些修改在这里都将被包括在本文和本发明中，并受后续的权利要求保护。