Modern research and strategic decision-making across industry, government, and academia often rely on extensive datasets containing personal information. There is a fundamental assumption that only aggregate statistics and patterns, and not individual records, will be accessible to users.

There are two primary strategies to safeguard individual privacy: adding noise to data and restricting permissible queries.  However, even with these safeguards, sophisticated attackers may still “compromise” the database by inferring individual values through carefully crafted combinations of aggregate queries.

This talk explores the critical trade-off between database utility and individual privacy protection, examining the mathematical and algorithmic foundations underlying database security. For example, we reveal unexpected connections between secure database design and graph theory, demonstrating how compromise-free query collections correspond to graphs with the least eigenvalue -2, and we establish the relationship between maximal compromise-free query collections and maximum antichains in finite sets, revealing how abstract mathematical structures inform practical privacy protection mechanisms.