Oblivious Computing Research

This research program develops mathematical foundations and practical implementations for privacy-preserving computation. The work spans three interconnected areas: algebraic cipher types for homomorphic computation on encrypted data, Bernoulli types for principled approximation in probabilistic data structures, and encrypted search systems that enable querying sensitive data without revealing query patterns or content.

Core Frameworks

Algebraic Cipher Types

Mathematical framework for type-safe encryption that preserves algebraic structure through homomorphic operations.

• Algebraic Cipher Types - Implements the cipher functor framework lifting monoids (S,*) to encrypted types c_A(S,*) with homomorphic properties. Provides type-safe encryption with zero-cost abstractions through C++20 templates. PDF | Code

Bernoulli Types

Unified framework distinguishing latent (true) values from their observed (approximate) representations, formalizing error propagation through probabilistic data structures.

• Bernoulli Types - Foundational theory making approximation a first-class concept at the type level. Enables formal reasoning about accuracy/resource tradeoffs in probabilistic algorithms. PDF | Code

• Bernoulli Data Types - Implementation framework with Bernoulli maps (universal function approximation), Bernoulli sets (including Bloom filters), and Bernoulli booleans. Demonstrates how traditional algorithms like Miller-Rabin fit the framework. Bernoulli Sets PDF | Higher-Order PDF | Code

• Cipher Trapdoor Sets - Privacy-preserving set operations using cryptographic one-way trapdoor functions. Enables secure computation on encrypted sets with explicit error rates. PDF | Code

Encrypted Search Systems

Practical systems enabling search over encrypted data while preserving query privacy and measuring information leakage.

Theory and Confidentiality

• Encrypted Search Thesis - Comprehensive treatment of encrypted search through Bernoulli types. Develops theoretical foundations for oblivious data structures and proves information leakage bounds. PDF

• Probabilistic Confidentiality Estimator - Measures confidentiality of encrypted search systems against adversaries observing query patterns. Bootstrap methods estimate sampling distributions to assess probability an adversary infers queries. Maps entropy to confidentiality lower bounds. PDF | Code

• Encrypted Search: Stream Entropy Maximization - Information-theoretic approach to maximizing entropy in query streams for stronger confidentiality guarantees. Analyzes entropy under different adversarial models.

Boolean Search Implementation

• Secure Index Boolean Search - Boolean encrypted search using approximate sets with information retrieval performance measures. Secure indexes support membership tests for trapdoors with measured false positive rates. Includes biword phrase search and k-graph extensions. PDF

• Encrypted Boolean Search (Code) - Implementation replacing Boolean index types with secure indexes based on random approximate sets. Code

Robust Approaches

• Encrypted Search: A Robust Approach - Query language design and robust encryption schemes for practical encrypted search deployment. Addresses real-world constraints and attack vectors.

Statistical Estimation

• Estimating Confidentiality in Search - Statistical methods for quantifying confidentiality in encrypted search systems through empirical measurement.

• Confidentiality Estimation: Moving Average Bootstrap - Bootstrap-based moving average techniques for estimating confidence intervals on query confidentiality over time. Code

Distributed Systems

• Hidden Information Retrieval on Blockchain - Decentralized encrypted search architecture using IPFS storage, P2P query processing, and blockchain consensus. Provides Byzantine fault tolerance and majority voting for Bernoulli result aggregation without central authority. PDF

Key Insights

This research program demonstrates:

1. Algebraic Structure Preservation: Cipher functors enable computing on encrypted data while maintaining mathematical properties
2. Principled Approximation: Bernoulli types formalize the latent/observed distinction, making error rates explicit at the type level
3. Measurable Privacy: Information-theoretic bounds and probabilistic estimators quantify confidentiality against adversaries
4. Practical Trade-offs: Explicit error rates enable reasoning about accuracy/performance/privacy trade-offs
5. Composability: Frameworks compose naturally - cipher types build on Bernoulli approximation for oblivious computation

Applications

• Privacy-preserving analytics on sensitive data
• Secure deduplication in encrypted storage
• Private set intersection without revealing sets
• Encrypted database queries
• Federated learning with confidential training data
• Oblivious data structures for secure computation

Implementations

All frameworks include modern C++ implementations with:

• Header-only libraries for easy integration
• Generic programming with concepts and templates
• Zero-cost abstractions through compile-time optimization
• Comprehensive test suites with property-based testing
• Clear documentation of mathematical foundations

This research develops both theoretical foundations and practical tools for computing on sensitive data while provably limiting information disclosure.