{"created":"2023-05-15T12:35:12.422648+00:00","id":127,"links":{},"metadata":{"_buckets":{"deposit":"a06bf1bd-ca1b-4853-a7a7-6877ed94772a"},"_deposit":{"created_by":2,"id":"127","owners":[2],"pid":{"revision_id":0,"type":"depid","value":"127"},"status":"published"},"_oai":{"id":"oai:kutarr.kochi-tech.ac.jp:00000127","sets":["5"]},"author_link":["456","457"],"item_2_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2009-02-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"2","bibliographicPageEnd":"210","bibliographicPageStart":"200","bibliographicVolumeNumber":"E92-D","bibliographic_titles":[{"bibliographic_title":"IEICE Transactions on Information and Systems"}]}]},"item_2_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Abstract"}]},"item_2_publisher_35":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"The Institute of Electronics, Information and Communication Engineers"}]},"item_2_relation_13":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"10.1587/transinf.E92.D.200","subitem_relation_type_select":"DOI"}}]},"item_2_relation_44":{"attribute_name":"関係URI","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"http://search.ieice.org/"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"http://search.ieice.org/","subitem_relation_type_select":"URI"}}]},"item_2_rights_14":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright © 2009 The Institute of Electronics, Information and Communication Engineers"}]},"item_2_source_id_11":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11510321@@@AA10826272","subitem_source_identifier_type":"NCID"}]},"item_2_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1745-1361@@@0916-8532","subitem_source_identifier_type":"ISSN"}]},"item_2_version_type_18":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"TAKATA, Yoshiaki"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"SEKI, Hiroyuki"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2019-02-13"}],"displaytype":"detail","filename":"IEICE_E92-D_2_200.pdf","filesize":[{"value":"554.7 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"IEICE_E92-D_2_200.pdf","url":"https://kutarr.kochi-tech.ac.jp/record/127/files/IEICE_E92-D_2_200.pdf"},"version_id":"91899205-fa1b-4609-b56a-27f11e5ed150"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"rust management","subitem_subject_scheme":"Other"},{"subitem_subject":"trust negotiation","subitem_subject_scheme":"Other"},{"subitem_subject":"negotiation strategy","subitem_subject_scheme":"Other"},{"subitem_subject":"computational complexity","subitem_subject_scheme":"Other"},{"subitem_subject":"context-free grammar","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation"}]},"item_type_id":"2","owner":"2","path":["5"],"pubdate":{"attribute_name":"公開日","attribute_value":"2011-06-23"},"publish_date":"2011-06-23","publish_status":"0","recid":"127","relation_version_is_last":true,"title":["Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation"],"weko_creator_id":"2","weko_shared_id":-1},"updated":"2023-05-15T13:44:00.915843+00:00"}