Articles in Press

We propose in this work a logical framework to formally model how a given piece of private information P (specified as a set of tuples) on a given database D, can get captured by an adversary A with a sequence of queries on the database; at every stage of the querying process, the knowledge acquired on D with the answers to his/her current and earlier queries, is 'saturated' using relational deductions; for this saturation, external public data given in advance can also be used. We assume that the database D can be protected with generalization mechanisms. The logical framework will be built on concepts from Probabilistic Automata, Probabilistic Concurrent Systems, and Probabilistic labeled transition systems, and will be named Distributed Labeled Tagged Transition System (DLTTS). A couple of concrete examples will show how the DLTTS can be used in practice. A second important point addressed in this work is in the realm of what is known as 'differential privacy'; its object is to study the situations where the query-answering mechanism (of D's DBMS) may or may not distinguish 'sufficiently/properly' the answers to two different instances of queries (by adversary A). A classical result in this direction says the following: If D, D′ are two databases (with all data of the same type and of the same length for both) adjacent for the Hamming metric (they differ at most on a single entry), then the answers to certain queries on D, D' are not properly distinguishable. In our current work, we shall show that on a larger and more general class of databases - where the data could be of mixed types, and not necessarily of the same length - (partial) metrics can be defined 'value-wise', i.e., in a constructive approach, and more general notions of adjacency between data bases can be defined, using these metrics; we will show them to be finer for differential privacy analysis.

^* Corresponding author.