DSpace Kochi University of Technology

Kochi University of Technology Academic Resource Repository >
A.学術情報資料別 >
学術雑誌論文 >

Files in This Item:

File Description SizeFormat
IEICE_E92-D_2_200.pdf541.71 kBAdobe PDFView/Open
Title: Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation
Authors: TAKATA, Yoshiaki
SEKI, Hiroyuki
Issue Date: 1-Feb-2009
Publisher: The Institute of Electronics, Information and Communication Engineers
Journal Title: IEICE Transactions on Information and Systems
Volume: E92-D
Issue: 2
Start Page: 200
End Page: 210
Abstract: Trust negotiation is an authorizing technique based on digital credentials, in which both a user and a server gradually establish trust in each other by repeatedly exchanging their credentials. A trust negotiation strategy is a function that answers a set of credentials to disclose to the other party, depending on policies and the set of already disclosed credentials. The disclosure tree strategy (DTS), proposed by Yu et al., is one of the strategies that satisfies preferable properties. DTS in a simple implementation requires exponential time and space; however, neither an efficient algorithm nor the lower-bound of its complexity was known. In this paper, we investigate the computational complexity of DTS. We formulate subproblems of DTS as problems on derivation trees of a context-free grammar (CFG), and analyze the computational complexity of the subproblems using the concepts of CFGs. As a result, we show that two subproblems EVL and MSET of DTS are NP-complete and NP-hard, respectively, while both are solvable in polynomial time if we modify EVL not to require non-redundancy and MSET not to answer any subset useless for leading the negotiation to success.
Rights: Copyright © 2009 The Institute of Electronics, Information and Communication Engineers
DOI: http://dx.doi.org/10.1587/transinf.E92.D.200
Type: Journal Article
URI: http://hdl.handle.net/10173/675
Appears in Collections:学術雑誌論文
高田, 喜朗 (TAKATA, Yoshiaki)

Please use this identifier to cite or link to this item: http://hdl.handle.net/10173/675

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Kochi University of Technology Library - Feedback