Encrypted Search with Oblivious Bernoulli Types: Information-Theoretic Privacy through Controlled Approximation

Problem: Traditional encrypted search systems face a fundamental tension: deterministic schemes leak access patterns enabling inference attacks, while probabilistic structures like Bloom filters provide space efficiency but fail to hide what is being queried.