
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation
Yoshiaki TAKATA Hiroyuki SEKI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E92D
No.2
pp.200210 Publication Date: 2009/02/01 Online ISSN: 17451361
DOI: 10.1587/transinf.E92.D.200 Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science) Category: Keyword: trust management, trust negotiation, negotiation strategy, computational complexity, contextfree grammar,
Full Text: PDF(543.3KB)>>
Summary:
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 lowerbound 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 contextfree 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 NPcomplete and NPhard, respectively, while both are solvable in polynomial time if we modify EVL not to require nonredundancy and MSET not to answer any subset useless for leading the negotiation to success.

