Information-Theoretic Advances in Privacy and Similarity Search

The field is witnessing a significant shift towards information-theoretic approaches to privacy and similarity search. Recent research has established a mathematical equivalence between witness-based similarity systems and Shannon's information theory, revealing that semantic similarity has physical units and search is communication over a noisy channel. Meanwhile, private information retrieval protocols are being developed to enable secure and efficient retrieval of information from databases. Noteworthy papers in this area include:

  • The Information Theory of Similarity, which establishes a precise mathematical equivalence between witness-based similarity systems and Shannon's information theory.
  • A Unified Framework for Constructing Information-Theoretic Private Information Retrieval, which proposes a new discrete structure for constructing IT-PIR protocols.
  • IVE: An Accelerator for Single-Server Private Information Retrieval Using Versatile Processing Elements, which achieves up to 1,275x higher throughput compared to prior PIR hardware solutions.

Sources

The Information Theory of Similarity

A Unified Framework for Constructing Information-Theoretic Private Information Retrieval

Non-Asymptotic Convergence of Discrete Diffusion Models: Masked and Random Walk dynamics

IVE: An Accelerator for Single-Server Private Information Retrieval Using Versatile Processing Elements

On the Context-Hiding Property of Shamir-Based Homomorphic Secret Sharing

A Privacy-Preserving Information-Sharing Protocol for Federated Authentication

A Dual Approach for Hierarchical Information-Theoretic Tree Abstractions

Towards Privacy-Preserving Range Queries with Secure Learned Spatial Index over Encrypted Data

Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics

An Information Theory of Finite Abstractions and their Fundamental Scalability Limits

Built with on top of