On the Construction of Practical Key
Predistribution Schemes for Distributed
Sensor Networks Using Combinatorial
Designs
JOOYOUNG LEE
National Security Research Institute and
DOUGLAS R. STINSON
University of Waterloo
In this paper, we discuss the use of combinatorial set systems (combinatorial designs) in the design of key predistribution schemes (KPSs) for sensor networks. We show that the performance of a KPS can be improved by carefully choosing a certain class of set systems as “key ring spaces”. Especially, we analyze KPSs based on a type of combinatorial design known as a transversal design. We employ two types of transversal designs, which are represented by the set of all linear polynomials and the set of quadratic polynomials (over some finite field), respectively. These KPSs turn out to have significant efficiency in a shared-key discovery phase without degrading connectivity and resiliency.
Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks]: General— Security and protection; C.2.1 [Computer-Communication Networks]: Network Architecture and Design—Wireless communication General Terms: Security, Design, Algorithms
Additional Key Words and Phrases: wireless sensor networks, key predistribution, security
A preliminary version of this paper was published under the title “A combinatorial approach to key predistribution for distributed sensor networks,” IEEE Wireless Communications and Networking Conference (WCNCrsquo;05), vol. 2, pp. 1200–1205.
Authorsrsquo; addresses: J. Lee, National Security Research Institute, Gajeong-dong 161, Yuseong-gu, Daejeon, 305-350, Korea; email: jlee05@etri.re.kr. D.R. Stinson, David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada; email: dstinson@uwaterloo.ca. D.R. Stinsonrsquo;s research is supported by the Natural Sciences and Engineering Research Council of Canada through the grant NSERC-RGPIN #203114-06.
Permission to make digital/hard copy of all or part of this material without fee for personal or classroom use provided that the copies are not made or distributed for profit or commercial advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior specific permission and/or a fee. Permission may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701, USA, fax 1(212)869-0481, or permissions@acm.org.
2008 ACM 1094-9224/2008/05-ART5 $5.00 DOI: 10.1145/1330332.1330333. http://doi.acm.org/
10.1145/1330332.1330333.
ACM Reference Format:
Lee, J. and Stinson, D. R. 2008. On the construction of practical key predistribution schemes for distributed sensor networks using combinatorial designs. ACM Trans. Inf. Syst. Secur. 11, 2, Article 5 (May 2008), 35 pages. DOI = 10.1145/1330332.1330333. http://doi.acm.org/10.1145/ 1330332.1330333.
1. INTRODUCTION
Distributed sensor networks (DSNs) are ad-hoc networks that are comprised of sensor nodes with limited memory as well as limited computational and communication capabilities. Recently, sensor networks have been widely studied due to their applications in civilian areas as well as in military operations. As an example of military applications, sensor nodes might be distributed in a random way in a hostile territory in order to monitor and collect various information (e.g., acoustic, seismic, magnetic). For example, they might be spread from airplanes or carried by soldiers. Once deployed, the sensor nodes operate unattended for extended periods without any movement. They have no external power supply during their operation. Therefore one essential requirement is that each sensor should consume as little power as possible. For additional discussion of this model, we refer to Carmen et al. [2000] and Roman et al. [2005]. A formal security framework for this model is described in Du et al.
[2005].
The nodes in distributed sensor networks should be able to communicate with each other in order to accumulate secret information and relay it to a base station. Because this communication is taking place in a hostile environment, encryption should be used to achieve confidentiality. This requires the establishment of secure keys between the various sensor nodes in the DSN. As discussed in Du et al. [2005], there are three ways to establish pairwise secret keys between sensor nodes, which we briefly review now.
One method is to establish secret keys using public-key protocols such as key agreement schemes. However, public-key cryptography is generally regarded as being unsuitable in this setting due to expensive computational costs [Eschenauer and Gligor 2002]. Furthermore, public-key cryptographic protocols such as authenticated key exchange require a public-key infrastructure (PKI) which would impose additional computational overhead as well as increased storage requirements [Du et al. 2005].
Another strategy is to have a trusted server (also called a base station), which can communicate with all the nodes in the network. The trusted server shares a long-lived key with every node and transmits session keys to sensor nodes on request, e.g., using Kerberos. This method can result in expensive costs for message relay, and it may not be feasible to maintain a secure trusted server.
The third approach, which is the approach most commonly recommended for DSNs and which we follow in this paper, is to employ key predistribution schemes (or KPSs), where secret keys are installed in each node before the sensor nodes are deployed.
Two trivial e
全文共80283字，剩余内容已隐藏，支付完成后下载完整资料
基于组合设计的分布式传感器网络的
密钥预分配方案构造
JOOYOUNG LEE 国家安全研究所
DOUGLAS R.STINSON 滑铁卢大学
在本文中，我们将讨论把组合结构系统（组合设计）应用于传感器网络的密钥预分配方案（KPS）设计中。 通过我们的研究表明，选择特定的系统作为“钥匙环空间”，然后基于一种我们称之为横向设计的组合设计方法来分析KPS，这样可以提高KPS的性能。 我们采用两种不同类型的横向设计，分别由线性多项式集合和一组二次多项式（在有限域上）表示。 这种密钥预分配方案在共享密钥发现阶段具有显著的效果，而且不会降低传感器的连接性和安全性。
1. 引言
分布式传感器网络（DSN）是由具有有限内存的传感器节点以及有限的计算和通信能力组成的自组织网络。近年来，由于传感器网络在民用领域以及军事行动中被广泛应用，所以已经被深入研究。以军事应用为例，传感器节点能够随机的分布在敌方的领土上，以便监测和收集各种信息（例如，声音信息，震动信息，磁性信息）。传感器节点可以从飞机上随机传播，也可以由士兵携带，充当传感器节点的载体。一旦部署完毕，传感器节点将无需移动且无人值守地长时间运行。因为它们在运行期间没有外接电源供电，所以一个基本要求就是每个传感器要消耗尽可能少的能量。有关此模型的其他讨论，请参考Carmen和Roman等人的相关文献。
分布式传感器网络中的节点能够相互通信，从而积累秘密信息并将其传送给基站。由于此通信是建立在敌方控制的地域环境中，因此应使用加密来实现保密。这需要在DSN中的各个传感器节点之间建立安全密钥。正如Du等人所讨论的那样，这里有三种方法可以用于传感器节点之间建立双密钥，我们简要说明一下。
第一种方法是使用公钥协议（如密钥协商方案）建立密钥。但是，由于昂贵的计算成本，公钥密码技术通常被认为是不适合的。此外，公共密钥加密协议，如认证密钥交换需要一个公共密钥基础设施（PKI），这将增加额外的计算开销以及存储需求。
第二种方法是建立一个可靠的可以与网络中的所有节点进行通信的服务器（也称为基站）。可靠服务器与每个节点共享长期密钥，并根据请求将会话密钥传输到传感器节点，例如使用Kerberos。此方法可能导致消息中继从而产生昂贵的成本，可能对于维护安全的服务器不适用。
第三种方法也是最常用于DSN的方法，我们在本文中采用的方法是密钥预分配方案（KPS），即部署传感器节点之前在每个节点中安装密钥。
这里可以参考KPS的例子。如果每个节点都被赋予相同的密钥即“主密钥”，这样内存成本会很低。但是，这种情况是不合适的，因为单个节点加密会使网络不完全。另一方面，对于每一对节点Ui和Uj，可能只有一个密钥Kij给这两个节点。这种方案对于节点有出色加密能力，但是对于大型网络而言，因为每个节点都必须存储n-1个密钥，其中n是DSN中的节点数量，内存成本将非常昂贵。
实际的解决方案必须在存储要求和弹性（即安全性）之间合理的折中（还有其他一些必须考虑的要求，比如网络连接，我们稍后会讨论）。一个常用的方法（以及我们在本文中研究的方法）是为每个节点提供一个特定的密钥空间。（但是，其他方法也是可能的，请见第1.1.6节和1.1.7节） 在Eschenauer和Gligor 的开创性论文中，提出了一种传感器网络密钥预测的方法，即：每个节点分配一个密钥子集（称为密钥环），其中密钥环是在给定密钥池中随机选择的子集。
在Eschenauer-Gligor方案和我们考虑的所有其他方案中，都有三个基本操作需要实施：密钥预分配，共享密钥确定和路径密钥建立。共享密钥确定是指确定两个附近节点是否共享同一种公共共享密钥（或者从它们的共享信息来构造共享配对密钥）的算法。当两个节点，比如x和y不共享配对密钥时，可以在它们中间试图找到一个或多个“中间”节点的序列，比如z1，z2，... ，zt，使得路径x，z1，z2，...zt，y中的每一对相邻节点共享一个共同的成对密钥。这就是路径密钥建立阶段。
一般来说，我们会使用各种标准来评估DSN的性能，这将在2.2节中详细描述。这里我们主要说的是网络的全局和本地连接，存储要求，网络规模和防御节点破解的安全性以及上述三种操作的效率。当我们分析网络操作的效率时，说的是通信复杂度（即网络中节点之间传输的信息量）以及计算复杂度（即计算量必须是由网络节点执行）。
1.1相关的准备工作
在本节中，我们简要总结一下Eschenauer-Gligor方案和其他以前文章中研究过的和/或从它衍生出来的方案。
1.1.1 Eschenauer和Gligor的方案。 Eschenauer和Gligor的密钥预分配方案在后续文章中被称为基本方案。该方案由三个参数定义：DSN中的节点数目，记为n;每个密钥环的大小，记为k;和密钥池P的大小，记为v。
网络中的每个节点从P接收不同的随机k子集的密钥。两个节点之间的安全直接通信要求它们共享至少一个公用密钥。如果两个节点共享多个公用密钥，则他们可以选择任意公用密钥用作它们的成对密钥。
请注意，关于三个参数n，k和v的唯一条件是nle;v。在实际应用中，对于k和v的“合理”值是n ，DSN中的节点数量可能非常大。
1.1.2 q综合方案。基本程序由Chan等人提出。 其中规定两个节点只在共享至少q个公钥时才能计算配对密钥。整数q是预先指定的交点阈值。整数q是预先指定的交点阈值。 鉴于两个节点至少有q个公共密钥，他们通过使用适当的密钥导出函数，以及所有的公共密钥来计算它们的成对密钥（参见例如第2.1.2节）。
当q = 1时与上述的基本方案非常相似。唯一的区别是两个节点共享多个公钥。在复合场景中，所有公钥都用于派生成对密钥，而在基本场景中，任何公钥都可以用作成对密钥。
1.1.3 Camtemp和Yener的方案。一开始，是由Camtepe和Yener 使用组合设计（也称为集合系统）来研究传感器网络的密钥预分布的。他们考虑了两种类型的组合设计：对称平衡不完全块设计（特别是有限投影平面）和广义四边形设计。采集系统中的点和块分别与不同的密钥标识符和传感器节点相关联（关于设置系统的正式定义，请参见第2节）。因此，与该块相关联的传感器节点（例如，B）接收由包含在B中的点索引到的所有密钥。通过使用这类收集系统，可以实现良好的连接性和安全性。这种方法的局限性在于，网络的大小受到设置系统中的块数限制。出于这个原因，他们还提出了一种混合方法来提高对于较大网络规模的适用性，就是当系统中的所有模块都用尽时，就会选择一个随机密钥环。
1.1.4 Lee和Stinson的方案。 Lee和Stinson 也研究了传感器网络密钥预分配的组合设计。他们介绍了一种着重于有限域上的线性多项式定义的水平设计，称为通用交叉口设计。在本文中，我们将详细分析线性和二次两种场景。线性方案是Lee和Stinson 研究的线性方案，我们在这里第一次提出了一个二次方案。显而易见，二次方案是在有限域上定义的二次多项式。
1.1.5 Chakrabarti，Maitra和Roy的方案。 Chakrabarti，Maitra和Roy也使用组合设计来实现传感器网络的密钥预分布。他们的主要想法是从一个特定的系统开始（如Lee和Stinson 提出的transversal设计），然后通过合并系统中的块来形成密钥环。这会导致更大的密钥环（因此会增加存储需求），但是其他性能指标会得到改进
1.1.6多空间方案。有人提出将基本方案（或基于组合设计或图的方案）与其他密钥预分配方案（如Blom方案）或Blundo等人的归纳方法“结合起来”。这种KPS有时被称为“多空间”KPS。遵循这种方法的工作包括Du，Lee和Stinson ，Liu，魏和吴等人。在多空间方案中，底层“外部”方案中的每个密钥会被相应的“内部”方案的某些部分密钥信息替代。 如果内部方案是基本的Blom方案，则此过程将增强节点的安全性，但同时它会将内存要求增加一倍。。
显然有很多不同的设置和场景可能会考虑DSN。在某些应用中，安全性可能不是主要因素（取决于可能存在的安全威胁类型）。可以看出，更好的安全性必须与诸如连接性之类的其他属性相互抵消，因此寻找各种安全性水平的结构是有用的。看来，基本的Eschenauer-Gligor方案以及几乎所有的通用方案，在连接性比安全性更重要的时候是最合适的。我们将在第7节中展示一种有希望增加安全性的多个空间方案，但同时需要花费额外的计算开销。
1.1.7哈希链方案。另一个密钥分布技术的研究途径，涉及到Leighton-Micali密钥预分配方案，该方案可以适应当地网络的情况。 Leighton-Micali方案基于Lee和Stinson 以及Ramkumar和Memon 提出的散列链进行修改。这些方案的一个特点就是使用哈希链，这样做可以更好的适应节点复杂性而且顾及安全性。但是，计算散列链是一个额外的计算要求。
1.2我们的贡献
在本文中，作为随机密钥环的替代方案，我们将研究由组合设计构造的确定性密钥环。与使用随机方法相比，使用确定性密钥分配方法有几个潜在的优点，而且通过使用基于组合设计的确定性密钥分配方案可以很好地实现这些优点。
我们现在列举确定性方案的主要优点。
（1）产生好的伪随机数会花费很大开销。确定性方案潜在地允许通过使用简单，直接的公式来完成密钥分配，而不是产生随机密钥环。 这导致的其中一个结果是确定性方案需要更少的随机比特位来建立（参见6.4节的例子）。
当系统初始化时，即使密钥分配只进行一次，使用简单的方法执行此操作仍然很有用。我们构造的特定方案（线性方案和二次方案）是非常简单的可用于密钥分配的公式。这些公式基于小素数整数p为模来分别评估线性和二次函数。
（2）我们确定了块图的理想组合属性（块图在2.2.3节中定义）。这些属性在研究DSN的本地连接时很有用。我们构建使用的配置和公共交叉设计的组合方案是保证了相关性能水平的最佳方案（这在第3节中得到了解决）。例如，我们的方案在块图中拥有最大可能的边数。
另一方面，当使用随机密钥分配方案时，不能保证所得方案的块图具有原本期望的属性。因此，在构建随机化方案之后，可能有必要构建和分析块图，以确定它是否具有足够的连接性。
（3）通过使用适当的确定性方案，共享密钥发现以及路径密钥建立可以大大简化。我们构造的线性和二次方案，可以使得计算复杂度和通信复杂度都是O（1）（即，复杂度不取决于存储在节点中的密钥数量）。然而，对于随机方案，由于关键任务缺乏结构，所以这些操作本身就很复杂。这点将在第2.2.6节中进一步讨论。
1.3文章摘要
我们提出了一种通用框架来构建2.1节中集合系统的密钥预分配方案。然后我们介绍各种指标来评估第2.2节中DSN的性能。在第3节中，我们讨论某些称为配置的集合系统，它们生成具有最佳本地连接的DSN。在这类配置中，称为通用交叉口设计的集合系统的子类特别有用。在第4节和第5节中，我们给出了性能非常好的两个特定类别的集合系统（具体来说，两种类型的横向设计：即线性和二次方案）。第6节给出了几种方案的仿真结果和比较。在第7节中，我们比较了线性方案和多空间方案。最后，我们对我们的结果进行简要总结。
2.密钥环空间
2.1组合框架
在本节中，我们正式定义了我们在本文中使用的组合框架。简而言之，我们使用组合集合系统作为密钥环空间来扩展Eschenauer和Gligor方案的框架。这个框架在上述几篇文章中很常见。
我们从一套系统的定义开始。
定义2.1：一个集合系统是一个对（X，A），其中A是一组有限的X个子集，称为块。点x的度是指包含x的块的数量。如果所有点具有相同的度数r，则称（X，A）是有规律的（r度）。 （X，A）的等级是最大块的大小。如果所有的块都具有相同的大小，比如说k，那么（X，A）被认为是一致的（秩k）。
例2.1. 不妨设
- = {1, 2, 3, 4, 5, 6, 7, 8, 9}, 且 A = {123, 456, 789, 147, 258, 369, 159, 267, 348, 168, 249, 357}.
那么（X，A）是一个由9个点和12个块的设定系统。这套系统是4度，等级都为3级。
在本文中，我们只会使用既规律又统一的集合系统。
2.1.1密钥预分配阶段。 一旦确定了期望的网络大小（由n表示）和每个节点的期望数目的密钥（由k表示），则选择具有正好n个块且秩为k的规则的统一集合系统，例如（X，A）。 在这种情况下，我们称（X，A）为密钥环空间。 中心确定一个整数q，称为交点阈值。 然后，密钥环空间可以用作具有n个节点的传感器网络中的密钥预分配方案。
让传感器节点表示为U1，... ，Un。 让
- = {xi : 1 le; i le; v}
然后让
A = {Aj : 1 le; j le; n}.
全文共6169字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[10908]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
