LUNA+: More Succinct Post-Quantum ZK-SNARKs from Computational Privacy

LUNA+ is the successor to LUNA, providing a more efficient and succinct post-quantum ZK-SNARG construction based on computational privacy. This repository contains the C++ implementation of the Half-GSW vector encryption scheme used in the paper LUNA+: More Succinct Post-Quantum ZK-SNARGs from Computational Privacy, together with the SageMath scripts used to derive the parameter sets. The implementation is built with the C++17 standard using gcc/g++ 11.4.0 or later. It runs for ($N_g = 2^{10}, 2^{12}, 2^{14}$), in this order, and reports the runtimes of the main components: Setup, Encrypt, Add, and Decrypt. By default, the build uses the accepted-paper LUNA+ parameter set, while a faster parameter set is also included. Quick Start Everything is driven from the Makefile in the repository root. make help lists all targets. Command What it does make all Install dependencies, build and install PALISADE v1.11.9, build and run the benchmark make docker Do the same inside a pinned container, leaving the host untouched make lima Do the same inside a pinned x86-64 Ubuntu 22.04 VM make sage Run the SageMath parameter search make docker-sage Run the SageMath parameter search in the upstream sagemath/sagemath image make sage-verify Check the parameter search against the paper's table make doctor Report toolchain, CPU feature, and PALISADE status The three paths are alternatives, pick one. 1. Host build Requires a Debian/Ubuntu host and sudo:make all This runs, in order: make deps (apt packages), make palisade (clone the pinned PALISADE tag into third_party/, build it, make install it), make build, and make test. PALISADE may take 10 to 30 minutes to compile. On a non-apt distribution, install git build-essential cmake autoconf libomp-dev (or their equivalents) yourself, then run make palisade test. 2. Docker make docker Builds luna-plus:v1.11.9 from the Dockerfile (Ubuntu 22.04, gcc 11.4, PALISADE v1.11.9) and runs the benchmark in it. The HGSW binary is compiled at run time rather than baked into the image, because it is built with -march=native and must match the CPU that executes it.make docker-shell # interactive shell, host repo mounted at /mnt/hostmake docker-sage # run the Sage scripts in the sagemath/sagemath image (no PALISADE) 3. Lima make lima # create the VM and run the benchmarkmake lima-shell # shell into itmake lima-delete # destroy itlima/luna-plus.yaml pins an x86-64 Ubuntu 22.04 cloud image by SHA-256. Your home directory is mounted writable at the same path inside the VM, so the build lands in your working tree. Prerequisites A Linux-based OS An x86-64 CPU with AES-NI/AVX support. The pseudorandom generator (hgsw/rng/aes256ctr.h) uses SSE and AES-NI intrinsics, so this artifact does not build on ARM. make doctor checks for this. On an Apple Silicon host, you may use make lima, which provisions an emulated x86-64 VM. Emulated timings are not comparable to the numbers in the paper. CMake (minimum version 3.5.1) gcc/g++ (minimum version 11.4.0; a lower version supporting the _uint128_t intrinsic will probably work, this is a recommendation) PALISADE Homomorphic Encryption Software Library, v1.11.9, installed for you by make palisade. For a manual install, see PALISADE_installation.md. SageMath, only for make sage; if absent, make sage falls back to the sagemath/sagemath Docker image automatically Selecting a Parameter Set PARAMS=1 (the default) is the accepted-paper LUNA+ parameter set ($n = 61, log_q = 47$); PARAMS=2 is the faster set ($n = 53, log_q ≈ 40.92, β = 12784$), which is the last row of the paper's parameter table. params_v2.hpp is a generated file: make sage re-derives it as sage/params_impl_p19_d32.hpp, which is gitignored rather than tracked, so run make sage and diff the two if you want to check that the committed header matches the search. Edit the search, not the header. make test PARAMS=2 # or the equivalent shorthand: make params-v2make docker PARAMS=2This is passed through to CMake as -DHGSW_PARAMS_VERSION. Editing HGSW/hgsw/params_selector.hpp directly still works and is used whenever PARAMS is not given on the command line. Parameter Search make sage runs sage/params_search.sage. For each plaintext modulus $p \in {19, 37, 277}$ it searches the $(m_q, \nu)$ grid and prints the parameter set that minimises the proof size, the compressed CRS size and the full CRS size. It writes them as C++ headers (params*.hpp) plus params_candidates.csv / params_best.csv into sage/. make sage-verify runs sage/verify_table.sage, which re-derives every LUNA+ row of that table, compares each entry with the value printed in the paper and exits non-zero on any mismatch.cd sage && sage params_search.sagecd sage && sage verify_table.sagemake sage, make sage-verify and make docker-sage do this for you. Manual Build If you prefer not to use the Makefile, and PALISADE v1.11.9 is already installed: cmake -S HGSW -B HGSW/build && cmake --build HGSW/build -jcd HGSW/build/hgsw/bin && ./HGSW_test Housekeeping make clean # remove HGSW build artifactsmake distclean # also remove the vendored PALISADE checkout