英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
并行哈希树模型的优化：个案研究
Kevin Atighehchi and Robert Rolland
摘要 - 本文侧重于基于内部可变输入长度函数的树形操作模式的并行散列函数。
该内部函数可以是单块长度（SBL）和无前缀MD散列函数，也可以是基于海绵的散列函数。 我们讨论了在设计基于所有树叶具有相同深度的树的并行散列函数时可以获得的各种形式的最优性。第一个结果是优化树形拓扑以减少运行时间的方案。 然后，在不影响最佳运行时间的情况下，我们显示我们可以稍微更改相应的树形拓扑结构以尽量减少
所需处理器的数量也是如此。因此，所得到的方案首先降低运行时间，然后降低所需处理器的数量。
关键字：哈希函数，哈希树，梅克尔树，并行算法
引言
哈希运算模式是一种迭代（操作）底层函数的算法，该算法针对散列的操作模式的部分是在特定组合方法下的算法迭代消息，以便计算摘要。哈希函数是通过将这种模式应用于具体的底层函数而获得的，我们说前者是建立在后者之上的。
通常，当目的是处理任意长度的消息时，底层函数可以是固定输入长度（FIL）压缩函数，分组密码或置换。但是，也可能有兴趣使用顺序（或串行）散列函数作为基础函数，以便为其添加其他功能，如粗粒度并行。由此产生的哈希函数必须满足通常的抗原像攻击性（给定一个摘要值，很难找到产生该摘要值的任何前图像），抗第二原像攻击性（给出消息m1，很难找到产生相同信息的第二个消息m2摘要值）和抗碰撞性（很难找到两个不同的消息产生相同的摘要值）。序列哈希函数只能使用指令级并行（ILP）和SIMD指令[1]，[2]。加密散列函数有许多应用程序，其中主要的用途是签名算法在签名之前压缩消息。
最著名的顺序散列模式是Merkle-Damgaring;rd [3]，[4]结构，它只能利用操作的细粒度并行性压缩功能。如果这样的低级“原语”可以从指令级并行性中受益，那么通过使用SIMD指令，迭代此构建块的外部算法也可以受益于粗粒度并行。这种并行性可以在多线程实现中使用。假设我们有一个无碰撞压缩函数以一个固定大小的数据作为输入。通过使用平衡二叉树结构，Merkle和Damgaring;rd [3]，[5]表明我们可以扩展这个函数的领域，使得新的外部函数表示为，具有任意大小的域，并且仍然是抗碰撞的。请注意，如果函数是顺序散列函数，则此树结构的目的仅仅是粗粒度并行的添加。
使用平衡二叉树的结构允许同时处理树中同一层的多个部分数据，从而使得哈希消息运行时间从减少到（如果我们有个处理器）[3]，[5]。如果希望进一步减少资源的占用，可以使用以下重排技术：
- 每个处理器都分配了一个子树的处理（在数据结构意义上）具有叶。有近似个这样的子树。剩余的祖先结点在树的每个剩余级别上的处理在处理器之间尽可能公平地分配。例子如图1。
- 另一种解决方案是，在树的每一层，尽可能公平地在个处理器之间分配结点计算。
处理器的数量按照因子减少并且渐近运行时间是守恒的（使用乘法因子2）。在在本文中，我们对使用资源的数量与运行时间之间的权衡不感兴趣，而是研究有限距离的最优算法。更确切地说，我们确定为有限的消息长度提供了最佳的具体（并行）时间复杂度的哈希树结构。
图1 使用个处理器耗费时间计算根结点的例子。哈希的消息大小为n=16。在第1阶段，将每个包含叶子的哈希子树分配给每个处理器进行计算。第一子树被分配给处理器、第二个处理器、第三个处理器到处理器和最后一个分配给处理器。然后在阶段2中执行细粒度分配。
树状结构在Shin[6]、BLaKe2[7]、M6[8]的并行哈希模式中更为显著，最近在KangarooTwelve[9]和RuleHash中提出，这是NIST[10]提出的建议。举一些例子，Skein使用一棵树，其拓扑结构由用户控制，这要归功于三个参数：基级结点的权力，它是二的幂;其他内部结点的形式也是2的幂，并且是限制树高度的最后一个参数。MD6使用完整的（但不一定是完美的）第四层树，意思是内部结点总是有四个孩子。添加填充0的虚拟叶子或结点，以便最右边的结点具有正确数量的子级。像Skein一样，MD6提供了一个参数来限制树的高度。
一些提案[11]，[12]，[13]认为覆盖所有消息块的树不是一件好事，因为处理器的数量不应随消息的大小而增长。例如，Sarkar等人的域扩展并行算法[11]，[12]，[13]使用处理器的完美二叉树，具有固定大小。这个压缩/散列函数调用的完美二叉树可以被看作是一个大的压缩函数，依次迭代大部分的消息。换句话说，只有在树中执行的结点计算可以并行完成。可用处理器的数量是散列消息时由加密表单的发布者选择的系统参数。该参数的值必须由收件人重新使用，例如在验证忽略时。因此，这个限制了可扩展性和潜在的加速。在本文中，我们认为可扩展性和潜在的加速应该独立于发送计算机的特性（配置）。
Bertoni等人[14]，[15]给出了基于树的散列函数的充分条件，以确保其随机预言的不可分性。他们针对不同的用途提出了几种树哈希模式。例如，我们可以使用高度为2的树，按以下方式定义：我们将消息分成与处理器数量相同的部分（大小大致相同），以便每个处理器散列每个部分，然后将所有结果都由一个处理器顺序散列。为了将消息分成几乎大小相同的部分，算法需要事先知道消息的大小。Bertoni等人还提出了一种仍然使用具有两个级别和固定数量的处理器的树的变体，但是该变体交错了消息的块。这种交织提供了许多优点，因为它允许流式消息的高效并行散列，由第一级树中的每个处理器处理的数据的相当均匀分布（没有事先知道消息大小）以及正确对齐处理器寄存器中的数据。这种解决方案适用于多线程和SIMD实现[16]。在本文中，我们研究理论上的最优加速，因此，散列消息应该已经可用。
我们在本文中关注的是使用基本变量输入长度（VIL）函数的哈希树模式，该函数需要l个较低级别基元的调用来处理l个块的消息，其中块和散列输出具有相同的大小。为了使这种复杂性具体化，我们选择使用单块长度（SBL）散列函数作为基础函数，并关注Coron等人[17]提供的无前缀Merkle-Damgaring;rd构造。我们做出这个选择的原因有两个：首先，我们需要一个散列函数，其操作模式被证明是随机预言无法区分的（当其底层基元被假定为理想时）。其次，假设我们已经应用了前缀自由编码[17]和另一种编码[14] [15]来标识树中输入的类型，则可以预先计算恒定数量的散列状态，从而使上述复杂性可能。请注意，即使我们以此构造为例，也会讨论基于海绵的功能的可能用途。在这项工作中，我们的目标是通过修改树形结构的电路拓扑来证明我们可以提高散列树操作模式的性能。虽然我们专注于树木的叶子深度相同的情况，但我们希望尽量减少电路的深度（平行时间）和宽度（涉及的处理器的数量）。这种工作已经在有限域中的平行指数运算中完成[18]，[19]，[20]，[21]，[22]，其中乘法运算符是关联和交换的。在并行散列的情况下，所考虑的运算符可以是固定输入长度压缩函数。这是非常不同的，因为我们没有这两个属性，我们需要处理其他问题（填充规则的空间消耗，长度编码或其他信息位）。据我们所知，这是第一次解决优化哈希树的问题。本文的主要兴趣是所提供的方法。结果可以如下表示：
- 第一个结果是优化树形拓扑以减少深度的算法。首先，结点度大于5是不可能的。进而我们证明我们仅可使用层次中结点度为2和3构造一个最优树。
- 在不影响此最佳深度的情况下，我们显示我们可以更改相应的树形拓扑以尽可能减小宽度。 特别是，我们表明对于一些消息长度，宽度可以减少到。
- 我们还提供了一种算法，用于优化散列计算每一步中的处理器数量。 我们证明十一种树拓扑是可行的。
- 假设消息大小为帕累托分布，我们使用Monte Carlo方法估计每个树拓扑的相对频率。
- 最后，我们表明，通过使用SBL哈希函数作为基础函数，并假设预计算值的数量不变，这些优化可以安全地应用并导致更为大复杂度。
图2 6块消息6-block消息的树形哈希。左边的哈希树需要2个单位的时间来处理每个层次。右边的哈希树需要3个单位的时间处理最低层次和2个单位的时间来处理根结点。
假设由底层函数处理消息的一个块花费一个单位时间。 二叉树不一定是给出最佳运行时间的结构。 图2显示了用于散列6块消息的两种不同的树拓扑。图2(a)中描述的二叉树给出了6个单位的（平行）运行时间，而图2(b)中描绘的树的每一层具有不同的度，最右边的一个运行时间给出了5个单位的运行时间。 此外，可以注意到，对于长度小于5个块的消息，与纯序列模式（即完全退化的二叉树）相比，拓扑的使用图2(a)没有实用性。
在下文中，我们假设使用具有域空间(其中)和固定长度范围空间的可变输入长度（VIL）压缩函数（或散列函数）。我们还假设当压缩个大小为位的块时，这样的函数具有个单位的理想计算成本。 换句话说，如果我们考虑这个函数的调用树，具有个子元素（即，个块）的结点的计算具有个单位的成本。这样的计算成本是现实主义的。 例如，散列函数族Skein [6]中使用的UBI转换函数[1]执行调用可调整块密码Threefish以压缩长度为块的数据。假设一个哈希树高度为，第()层的度为，那么获得根结点值的并行运行时间为。
本文按以下方式组织。 在第2节中，我们给出了背景信息和定义。 在第3节中，我们首先描述了最小化哈希函数运行时间的方法。 然后，我们给出一个算法来构造一个哈希树拓扑结构，它在达到相同的最佳运行时间的同时需要最佳数量的处理器。 我们还表明，我们可以在散列计算的每一步中优化处理器的数量。 这导致了十一种可能的树拓扑，其概率分布在第4节中经验性分析。我们在第5节中提出了一个具体的基于树的哈希函数，它可以安全地实现这些优化。最后，在第5节中，我们总结了这篇论文。
2初步
2.1树结构
在本文的整个过程中，我们使用约定[2]，结点是由一个由结点的子结点组成的数据调用的函数的结果。
然后，结点值（或链接值）一致于在这个函数之前的图像，并且该结点的子结点可以是其他图像或消息块。 我们称一个底层节点为第1层的一个节点，指向表示消息数据块的叶子结点。 然后叶子结点处于第0层。然后，高度的节点树具有个级别。 我们将树中某个层的度定义为这个层中最大的结点度。
叉树是结点的度最多为的一个树。例如，一棵只有一个结点的度为的树也被认为是叉树。 每个结点都有个孩子的叉树叫做满叉树。完全叉树是所有叶子都具有相同的深度的满叉树。
我们还定义了其他“精炼”类型的树。若一棵树有n层（不算第0层），第1层最大结点度为，第2层最大结点度为，以此类推。我们将这棵称为拥有度的树（称为-叉树）。如果一颗这样的树的第一层的所有结点恰好有个子结点，第二层的所有结点恰好有个子结点，以此类推。那么称之为满-叉树。同样地，如果一棵树是满-叉树，并且所有的叶子结点在同一深度，称之为完全-叉树。
结点树存在有相应的具有少一层的-input树。例如，高度为1和结点度为3的简单树有2层和四个结点：一个根结点和三个子结点，它们是消息块。其相应的-input树具有单层并且该层只包含单个-input。 这个-input由消息块和一些元信息位的连接组成。这种表示方式在下面的第2.2节中进一步定义。
2.2基于树的哈希函数的安全性
在本节（和第5.2节）中，描述-input树，假设在外部散列函数中操作单个内部函数，表示为H。这是[14]、[23]中采用的表示形式来证明所需的安全属性。 我们记得，与结点树相比，-input树少1层。
一个-input是来自以下元素的有限比特序列：消息比特，链接值比特（即，来自-image的比特）和帧比特（由散列算法和消息大小完全确定的比特）。在一个-input树中，有从子结点到他们相应的父结点的指针。当链接值存在于格式化的-input中时，它被另一个被认为是其子结点的-input指向。每个-input都有一个关联的索引，将其定位在树中。另外，对于-input树，我们需要定义相应的树模板，其具有相同的拓扑结构，其中相应的-input具有相同的长度并且帧位与中的对应位相匹配，但是消息和链接值位未评估。因此，树模板完全由消息大小和树模式算法的参数决定。该树模板被树哈希模式用来实例化-input树，通过逐步评估消息比特和链接值比特。
如果后者可以生成一个-input树，并且其对应的树模板与其兼容，则-input树被认为符合树散列模式（其拓扑结构，帧比特和其-input的大小与的输入匹配。）。如果后者可以生成一个-input树, 其适当的子树具有与 兼容的相应树模板，则-input的树被称为与具有最终子树兼容性。
Bertoni等人 [14]，[23]给出了一些准则，以正确设计操作内部哈希（或压缩）函数的树哈希模式。 它们定义了三个充分的条件，它们确保使用理想散列（或压缩）函数的构造散列函数从理想散列函数是无法区分的。 此外，他们建议使用特定的帧位以满足这些条件。 我们参考[14]，[23]的详细定义，我们在这里对这三个条件给
全文共6189字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11706]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
