kmp-mpc

Oblivious substring search using Obliv-C, sqrtOram and Knuth-Morris-Pratt.

NOTE: The sqrtOram dependency is not working. Anyone who is familiar with the sqrtOram library and can fix this is welcome to make a PR.

Introduction

One party wants to be able to determine whether its substring is in another party's text. However, both parties want to keep their input private. This multi-party computation (MPC) problem, known as oblivious substring search, can be found across several different fields. In bioinformatics, for example, people might want to allow a company to search their DNA for a particular proprietary pattern, while maintaining privacy.

kmp-mpc uses Obliv-C as a MPC framework. It creates a new variation of the substring search algorithm Knuth-Morris-Pratt to accomodate for Obliv-C's restrictions on oblivious conditional statements and indexing into arrays. To keep memory access patterns hidden, all oblivious indexing into arrays use ORAM. Rather than use the naive solution of reading at each index to hide memory access patterns, this implementation uses sqrtOram reducing the time complexity of oblivious lookups from linear to square-root order.

Test Results

Tests were conducted on two AWS c4.2xlarge nodes. The tests found a linear relationship between text size and run time and a square-root relationship between pattern size and run time.

Installation

• Clone and install Obliv-C
• Clone and install sqrOram

git clone https://github.com/jnayak1/kmp-mpc.git

export OBLIVC_PATH=/path/to/obliv-c

export SQR_ORAM_PATH=/path/to//sqrtOram

Docker

docker build . -t kmp-mpc:latest

docker run -it kmp-mpc

cd kmp-mpc

Running

MAX_PATTERN_LENGTH=4 MAX_TEXT_LENGTH=256 make

./a.out [port] -- text.txt & -- server

./a.out [port] [host] pattern.txt -- client