Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation
スポンサーリンク
概要
- 論文の詳細を見る
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.
- The Institute of Electronics, Information and Communication Engineersの論文
- 2009-02-01
著者
-
SEKI Hiroyuki
Nara Institute of Science and Technology
-
Seki Hiroyuki
Nara Inst. Sci. And Technol. Ikoma‐shi Jpn
-
Takata Yoshiaki
Kochi Univ. Technol. Kami‐shi Jpn
-
Takata Yoshiaki
Kochi University Of Technology
関連論文
- Layered Transducing Term Rewriting System and Its Recognizability Preserving Property (Special Issue on Selected Papers from LA Symposium)
- Termination Property of Inverse Finite Path Overlapping Term Rewriting System is Decidable
- Finite State Translation Systems and Parallel Multiple Context-Free Grammars
- New certificate chain discovery methods for trust establishment in ad hoc networks and their evaluation (特集:次世代社会基盤をもたらす高度交通システムとモバイル通信システム)
- Policy Controlled System and Its Model Checking
- Decidability of the Security Verification Problem for Programs with Stack Inspection
- Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation
- Comparison of the Expressive Power of Language-Based Access Control Models
- FOREWORD
- Error Control for High-density Monochrome Two-dimensional Barcodes
- A Weighted-Pushdown-System-Based Formal Model for Information-Based Access Control
- LTL Model Checking for Extended Pushdown Systems with Regular Tree Valuations