Encrypted Search: Enabling Standard Information Retrieval on an Encrypted Collection

This repository contains my Master's thesis (published via ProQuest Dissertations & Theses Global) and related research papers on encrypted search systems, which enable untrusted cloud servers to search encrypted documents on behalf of authorized users without revealing document contents or query terms.

📄 Thesis PDF: Available in papers/alex_towell_cs_thesis_proquest.pdf or online at metafunctor.com | GitHub

Overview

The research explores how to enable powerful search capabilities over encrypted data while maintaining privacy guarantees through:

• Secure indexes based on approximate set data structures (Bloom filters, Perfect Hash Filters)
• Information leakage analysis and mitigation strategies
• IR scoring techniques (BM25, proximity scoring) adapted for encrypted search
• Plausible deniability through controlled false positives and uniform encoding

Repository Structure

encrypted_search_thesis/
├── papers/                          # Master's thesis materials
│   ├── alex_towell_cs_thesis_proquest.pdf  # Official ProQuest thesis (106 pages)
│   ├── encrypted-search.pdf         # Compiled thesis
│   ├── encrypted-search.docx        # Source document
│   ├── encrypted-search.pptx        # Defense presentation
│   ├── cs_thesis.bib                # Complete bibliography (440 entries)
│   └── references.bib               # Bibliography
│
├── followup/                        # Unpublished follow-up papers
│   ├── alex-journal/                # FSSA architecture paper
│   │   ├── Alex_Journal.docx        # Original manuscript
│   │   └── paper/
│   │       └── document.tex         # LaTeX version
│   │
│   └── perfect-hash/                # PSI taxonomy paper
│       ├── Perfect_hash_02.docx     # Original manuscript
│       └── paper/
│           └── document.tex         # LaTeX version
│
├── data/                            # Experimental data
├── CITATION.cff                     # Citation metadata
├── LICENSE                          # MIT License
└── README.md                        # This file

Key Contributions

Master's Thesis (2014)

The thesis introduces secure index types for encrypted search:

Index Type	Description
BSI	Bloom filter Secure Index - Boolean queries
PSI	Perfect hash filter Secure Index - Boolean queries with O(1) hash
PSIB	PSI-Block - Boolean + location + frequency via block segmentation
PSIP	PSI-Post - Approximate postings lists
PSIF	PSI-Frequency - Boolean + frequency queries
PSIM	PSI-Minimum distance - Pairwise proximity queries

Follow-up Papers (Unpublished)

1. Fail-Safe Security Architecture (FSSA): A security design ensuring no single party has access to complete customer information, protecting privacy even if servers are compromised.

2. Perfect Filter Secure Indexes Taxonomy: Comprehensive analysis of PSI variants with space complexity, false positive characteristics, and privacy properties.

Building the Papers

The follow-up papers are available in LaTeX:

# Build FSSA paper
cd followup/alex-journal/paper && pdflatex document.tex

# Build PSI taxonomy paper
cd followup/perfect-hash/paper && pdflatex document.tex

Pre-compiled PDFs are included in the repository.

Citation

If you use this research in your work, please cite:

@mastersthesis{towell2014encrypted,
  author       = {Towell, Alexander R.},
  title        = {Encrypted Search: Enabling Standard Information Retrieval on an Encrypted Collection},
  school       = {Southern Illinois University Edwardsville},
  year         = {2014},
  address      = {Edwardsville, Illinois, USA},
  type         = {Master's Thesis},
  note         = {Available via ProQuest Dissertations \& Theses Global},
  url          = {https://metafunctor.com/latex/2015-cs-thesis/alex_towell_cs_thesis_proquest.pdf}
}

For the follow-up papers:

@unpublished{towell2015fssa,
  author = {Towell, Alexander R. and Fujinoki, Hiroshi},
  title  = {Fail-Safe Security Architecture for Encrypted Search Using Perfect Filters},
  year   = {2015},
  note   = {Unpublished manuscript}
}

@unpublished{towell2015psi,
  author = {Towell, Alexander R. and Fujinoki, Hiroshi},
  title  = {Perfect Filter Secure Indexes: A Taxonomy of Privacy-Preserving Data Structures for Encrypted Search},
  year   = {2015},
  note   = {Unpublished manuscript}
}

Core Insight

The fundamental insight across this research is that approximation + uniform encoding = privacy:

1. Accept imperfection: Use approximate data structures (Bloom/Perfect filters) with controlled false positive rates
2. Encode uniformly: "Poison" indexes so true matches and false matches are computationally indistinguishable
3. Achieve deniability: Adversaries cannot determine which query responses are true positives vs. false positives

Related Work

This repository is part of the oblivious-computing research series. Central hub: metafunctor.com/series/oblivious-computing

Related Repositories

Repository	Description
bernoulli-types	Theoretical foundation for approximate set membership
bernoulli_data_type	C++ implementation of Bernoulli types
cipher_trapdoor_sets	Privacy-preserving set operations
encrypted-search-confidentiality	Bootstrap methods for confidentiality analysis
entropy-maximization-encrypted-search	Entropy optimization framework
maph	Space-efficient approximate mappings via PHF
crypto-perf-hash	Cryptographic perfect hash functions

Author

Alexander R. Towell lex@metafunctor.com

License

This project is licensed under the MIT License - see the LICENSE file for details.