active library

encrypted_search_thesis

Master's thesis on encrypted search: enabling standard IR on encrypted collections. Published via ProQuest (2014). Part of the oblivious-computing research series.

Started 2019 TeX

Resources & Distribution

Source Code

GitHub Repository

Package Registries

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)

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.
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:

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

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

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.