How to authenticate graphs without leaking
How to authenticate graphs without leaking
复制标题
DOI：
10.1145/1739041.1739114
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
A. Kundu;E. Bertino
中科院分区：
文献类型：
--
作者：
A. Kundu;E. Bertino
多方环境中的安全数据共享要求确保数据的真实性和机密性。数字签名方案通常用于数据的认证。然而，即使有向图是最广泛使用的数据组织结构之一，也不存在这样的技术。现有的DAG方案具有保真性而不保密性，在认证过程中会导致敏感信息的泄漏。本文提出了两个无泄漏认证DAG和有向循环图的方案，这是文献中第一个这样的方案。它基于深度优先图遍历和聚集签名所定义的图的结构。图在结构上不同于树，因为在深度优先遍历中，图有四种类型的边：树、前向、交叉和后边。一条边是前边、十字边或后边这一事实传达了在几个环境中敏感的信息。此外，后边比前向边提出了更困难的问题，而交叉边主要是因为后边给图增加了双向性质。我们证明了所提出的技术既具有保真性，又不会泄漏。在提供如此强的安全性的同时，我们的方案也是有效的，性能结果支持这一点。
Secure data sharing in multi-party environments requires that both authenticity and confidentiality of the data be assured. Digital signature schemes are commonly employed for authentication of data. However, no such technique exists for directed graphs, even though such graphs are one of the most widely used data organization structures. Existing schemes for DAGs are authenticity-preserving but not confidentiality-preserving, and lead to leakage of sensitive information during authentication. In this paper, we propose two schemes on how to authenticate DAGs and directed cyclic graphs without leaking, which are the first such schemes in the literature. It is based on the structure of the graph as defined by depth-first graph traversals and aggregate signatures. Graphs are structurally different from trees in that they have four types of edges: tree, forward, cross, and back-edges in a depth-first traversal. The fact that an edge is a forward, cross or a back-edge conveys information that is sensitive in several contexts. Moreover, back-edges pose a more difficult problem than the one posed by forward, and cross-edges primarily because back-edges add bidirectional properties to graphs. We prove that the proposed technique is both authenticity-preserving and non-leaking. While providing such strong security properties, our scheme is also efficient, as supported by the performance results.