| CHITTAPHONE PHONHARATH | 1261020: D, 中間発表 | 関 浩之, 伊藤 実, 楫 勇一, 橋本 健二 |
|
title: Deciding Schema k-Secrecy for XML Databases
abstract: We study a static analysis problem on k-secrecy, which is a metric for the security against inference attacks on XML databases. Intuitively, k-secrecy means that the number of candidates of sensitive data of a given database instance or the result of unauthorized query cannot be narrowed down to k-1 by using available information such as authorized queries and their results. This talk consists of two parts. In the first part, I will talk about the formal definition of k-secrecy, and the decidability (and undecidability) results. We showed that the schema k-secrecy problem is undecidable for any finite k >1 even when queries are represented by a simple subclass of linear deterministic top-down tree transducers (LDTT). We also showed that the schema ∞-secrecy problem is decidable for queries represented by LDTT. Time complexity will also be given in the talk. In the second part, I will talk about an ongoing work which extends and/or refines the first part. For a negative result, even if erasing or subtree-deleting rules are not allowed in a tree transducer, k-secrecy is still undecidable for LDTT. For a positive result, restricting unauthorized query to identity map makes 2-secrecy decidable. I conjecture that using delimiter in authorized query makes k-secrecy decidable. Conservative approximation for k-secrecy by using delimiter is a future study. language of the presentation: English | ||
| 中島 悟 | 1251077: M, 2回目発表 | 井上 美智子, 伊藤 実, 米田 友和, 大和 勇太 |
| 矢野 正人 | 1251110: M, 2回目発表 | 関 浩之, 金谷 重彦, 楫 勇一, 加藤 有己 |