Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation

Yoshiaki TAKATA  Hiroyuki SEKI  

IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.2   pp.200-210
Publication Date: 2009/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.200
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
trust management,  trust negotiation,  negotiation strategy,  computational complexity,  context-free grammar,  

Full Text: PDF(543.3KB)>>
Buy this Article

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.