SSE Implementations

Implementations of the following searchable symmetric encryption (SSE) schemes:

• PiBas (Cash et al., NDSS'14) (but specifically the result-hiding variant used in Demertzis et al., NDSS'20 (in figure 12), similar to PiBasRo)
• NLogN (Asharov et al., STOC'16, approach #3 "Improving the Cash–Tessaro Scheme")
• Logarithmic-SRC (Demertzis et al., SIGMOD'16)
• Logarithmic-SRC-i (Demertzis et al., SIGMOD'16)
• Logarithmic-SRC-i* (Demertzis et al., TODS'18)
• SDa (Demertzis et al., NDSS'20)

Since many of these can be instantiated with various underlying schemes, the following instantiations are possible:

• PiBas
• NLogN
• Logarithmic-SRC[PiBas]
• Logarithmic-SRC[NLogN]
• Logarithmic-SRC-i[PiBas]
• Logarithmic-SRC-i[NLogN]
• Logarithmic-SRC-i*
• SDa[PiBas]
• SDa[NLogN]
• SDa[Logarithmic-SRC[PiBas]]
• SDa[Logarithmic-SRC[NLogN]]
• SDa[Logarithmic-SRC-i[PiBas]]
• SDa[Logarithmic-SRC-i[NLogN]]
• SDa[Logarithmic-SRC-i*]

See src/main.cpp for usage examples.

Requirements

• CMake
• Conan 2
• A C++ compiler that supports C++20 (ideally g++ version 10 or above; e.g. for apt, install with apt install g++-10)

Only tested on Linux (NixOS, Ubuntu). To run on Windows, don't. (ok, fine, WSL works :p)

Running

1. Generate two Conan profiles for debug and release respectively (names must match those in the Makefile!):

   conan profile detect --name=sse_implementations_debug
   conan profile detect --name=sse_implementations_release
   

2. Edit both Conan profiles (by default at ~/.conan2/profiles/; the .conanrc should set it to ./conan2/profiles however):

   • Set build_type=Debug for the debugging profile and build_type=Release for the release profile.

   • Make sure compiler.cppstd=20 is set (gnu20 is fine too if using compiler=gcc).

   • If your "default" compiler (usually /usr/bin/c++, which is usually symlinked to /usr/bin/g++) is not the correct version and something like g++-10 was separately installed (e.g. to /usr/bin/g++-10), add the following to the bottom of both profiles to specify the compiler executable:

     [conf]
     tools.build:compiler_executables={"cpp": "<path to compiler executable>"}
     

     Make sure to use the C++, not C compiler! (E.g. g++ instead of gcc or clang++ instead of clang.)

3. Verify that the compiler executable set for CMAKE_CXX_COMPILER in CMakeLists.txt matches the one set in the Conan profiles. If using default, you can comment this line out in CMakeLists.txt (in which case CMake will use the default /usr/bin/c++).
4. In the base directory of this project/repo, run

   make
   

   and then run either the debug (non-compiler-optimized) version with

   ./build-debug/main
   

   or the release (compiler-optimized) version with

   ./build-release/main
   

NixOS

If you're using NixOS, there is a flake.nix provided that installs the packages listed in the "Requirements" section above. Run nix develop in this project's base directory to install them and then proceed with the steps above (I have chosen to not make the flake replace conan as dependency management).

Notes

• This is NOT intended for actual, real-world use! It's more as a proof of concept or a simulation for running experimental evaluation.
• The client-server distinction is very minimal and is only meant for benchmarking the network communication size. It does not actually run on two separate machines or have a well-defined client/server program. (At the moment, only the "most underlying" schemes like static point SSEs—PiBas and NLogN—have a server class; other schemes just keep many instances of these underlying schemes, client and server together.)
• Ids and keywords must be nonnegative integral values. Otherwise, Bad Things may happen.
• While each database tuple possess a range of keywords instead of just one for sake of generality (for range scheme underlying indexes), they must still only have a singular keyword in the input database, meaning the start and end of each keyword range must be the same.
• Keyword search is supported (i.e. one document can have multiple keywords), but only for non-range schemes (as range queries for documents with multiple "keywords" or attribute values are not well-defined). To insert such documents into the dataset, put in one document per keyword all with the same id. Attempting to do this for the range schemes may result in undefined behavior; only insert one document per id for those.
• Currently, src/main.cpp implements four experiments:
  • A debugging experiment that prints out the results for each scheme and acts as a basic test case/sanity check.
  • Experiment 1, which times range queries of varying sizes on a fixed-size db.
  • Experiment 2, which times a fixed range query on dbs of varying sizes.
  • Experiment 3, which demonstrates the advantage of Logarithmic-SRC-i over Logarithmic-SRC when a lot of false positives are generated.
• i have pain

Todo

• faster way to do setup() for dynamic schemes instead of calling update() (for ease of experimental evaluation)

• minor: investigate if srcidb1doc can be moved out of utils