Movatterモバイル変換

IEICE Transactions on Information and Systems

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 subproblemsEVL andMSET of DTS areNP-complete andNP-hard, respectively, while both are solvable in polynomial time if we modifyEVLnot to require non-redundancy andMSET not to answer any subset useless for leading the negotiation to success.

References (15)

Related articles (0)

Figures (0)

Supplementary material (0)

Result List ()

Cited by (0)

© 2009 The Institute of Electronics, Information and Communication Engineers

Favorites & Alerts