在信息安全领域，有关计算问题复杂度的研究是一个重点内容。本文深入研究了一种基于图论思想的，分析计算问题复杂度的新理论——分层数据处理理论，并应用该理论来分析和解决信息安全中的两类重要问题。 分层数据处理理论(HDPT,Hierarchical Data Processing Theory)是由美国布朗大学计算机系的两位学者：Roberto Tamassia 和Nikos Triandopoulos提出的基于图论思想的分析计算问题复杂度的新的理论。该理论首先定义了分层数据处理问题(HDP，HierarchicalData Processing Thaeory)，并结合图论的思想给出其代价分析标准，从而形成了一套完整的理论框架体系。目前，该理论已初步应用于两类信息安全问题之中，即基于密码学哈希的数据认证和基于密钥图的组播密钥管理。 本文将HDPT在上述两类信息安全问题中的研究与应用做了进一步的深入和扩展。在已有分析的基础上，完善了认证数据结构代价分析模型，并对一种新的认证跳表方案做了理论上的代价分析,并给出相应的数学证明；在对基于密钥图的组播密钥管理的问题研究中，本文应用HDPT，从理论上提出了基于逻辑密钥树的组播密钥管理方案的代价分析模型，并应用该模型对m叉逻辑密钥作以理论上的代价分析，并得出在所有逻辑密钥树当中，四叉逻辑密钥树具有最优的密钥更新和存储代价。结合HDPT的理论分析成果，本文构建了一种新的基于完全树的组播密钥管理方案，并应用HDPT对其代价进行分析，得出完全四叉树在密钥更新和存储代价方面具有最优性，从而证明了本文所提出的逻辑密钥树代价分析模型的通用性。