  There has recently been an increased scientific interest in the
de-anonymization of users in anonymized databases containing user-level
microdata via multifarious matching strategies utilizing publicly available
correlated data. Existing literature has either emphasized practical aspects
where underlying data distribution is not required, with limited or no
theoretical guarantees, or theoretical aspects with the assumption of complete
availability of underlying distributions. In this work, we take a step towards
reconciling these two lines of work by providing theoretical guarantees for the
de-anonymization of random correlated databases without prior knowledge of data
distribution. Motivated by time-indexed microdata, we consider database
de-anonymization under both synchronization errors (column repetitions) and
obfuscation (noise). By modifying the previously used replica detection
algorithm to accommodate for the unknown underlying distribution, proposing a
new seeded deletion detection algorithm, and employing statistical and
information-theoretic tools, we derive sufficient conditions on the database
growth rate for successful matching. Our findings demonstrate that a
double-logarithmic seed size relative to row size ensures successful deletion
detection. More importantly, we show that the derived sufficient conditions are
the same as in the distribution-aware setting, negating any asymptotic loss of
performance due to unknown underlying distributions.
