This is the implementation of our FC 2018 paper: SWiM: Secure Wildcard Pattern Matching From OT Extension[ePrint].

Evaluating on a single Intel Xeon server (2 36-cores Intel Xeon CPU E5-2699 v3 @ 2.30GHz and 256GB of RAM), ours protocol requires only 60 seconds to securely compute the Secure Wildcard Pattern Matching for text size n = 2^22 and pattern size m = 2^14

C++ compiler with C++14 support. There are several library dependencies including Boost, Miracl, and libOTe. For libOTe, it requires CPU supporting PCLMUL, AES-NI, and SSE4.1. Optional: nasm for improved SHA1 performance. Our code has been tested on both Windows (Microsoft Visual Studio) and Linux. To install the required libraries:

• windows: open PowerShell, cd ./libOTe/cryptoTools/thirdparty/win, and getBoost.ps1; getMiracl.ps1
• linux: cd ./libOTe/cryptoTools/thirdparty/linux, and bash all.get.

NOTE: If you meet problem with getBoost.ps1; getMiracl.ps1 or all.get which builds boost, miracl and libOTe, please follow the more manual instructions at libOTe

After cloning project from git,

1. build cryptoTools,and libOTe projects in order.
2. add argument for frontend project (for example: -t)
3. run frontend project

1. make (requirements: CMake, Make, g++ or similar)
2. for test: ./bin/frontend.exe -t

The database is generated randomly. The outputs include the average online/offline/total runtime that displayed on the screen and output.txt.

-t		unit test which computes the Secure Wildcard Pattern Matching for text size 2^14 and pattern size 2^9
-r		role (`-r 0` as sender, `-r 1` as receiver)		
-nn		logarithm of text size. For example, `-nn 14` means that the text size is 2^14
-n		text size
-mm		logarithm of pattern size. For example, `-mm 9` means that the text size is 2^9
-m		pattern size		

./bin/frontend.exe -t

Compute Secure Wildcard Pattern Matching for text size 2^14 and pattern size 2^9 in semihonest setting

./bin/frontend.exe -r 0 -nn 14 -mm 9 
& ./bin/frontend.exe -r 1 -nn 14 -mm 9 

Compute Secure Wildcard Pattern Matching for text size 10000 and pattern size 256 in semihonest setting

./bin/frontend.exe -r 0 -n 10000 -m 256
& ./bin/frontend.exe -r 1 -n 10000 -m 256

For any questions on building or running the library, please contact Ni Trieu at trieun at oregonstate dot edu