Supplementary files for "Sota Voce: Low-Noise Sampling of Sparse Fixed-Weight Vectors"

This repository contains the implementations accompanying the paper "Sota Voce: Low-Noise Sampling of Sparse
Fixed-Weight Vectors", published at IACR TCHES vol. 2026 no. 1.

Prerequisites

• A C compiler (tested with gcc and clang), with AVX2 support if building the x86-64 implementation.
• CMake version 3.21 or later.
• Linux with getentropy() or equivalent entropy source. It may also work under macOS, but it hasn't been thoroughly
  tested on this platform.
• GNU Make (or Ninja).

Building the project

A typical command line for configuring the project, from the root folder of the repository, is:

cmake -DCMAKE_BUILD_TYPE=Release -DBUILD_X86_64=ON -DVECT_IMPL=sendrier_mergenet -B build -G Ninja

If Ninja is not available, -G Ninja can be removed from the command line.

The project can then be built, again from
the root folder of the repository, by running cmake --build build -j, or by going to the build directory and running
ninja (or make -j if configured without Ninja).

Configuration options

There are two available configuration options: BUILD_X86_64 and VECT_IMPL.

BUILD_X86_64 is a boolean variable (either ON or OFF). If OFF, only the reference version is built, with a
restricted set of tests. If ON, an Intel x86-64 version with AVX2 optimizations is built, along with a more extensive
test suite.

VECT_IMPL selects the algorithms to be benchmarked for steps 2 and 3 as well as protocol-level (KEM operation)
benchmarks. If set to default, HQC's original implementations are used for both step 2 (a non-vectorized
implementation of Sendrier's shuffle) and step 3 (an AVX2 version of the naïve algorithm for writing the support to a
bit vector). Alternatively, it can have the format <step-2-algorithm>_<step-3-algorithm>, with the following available
choices of algorithms:

• <step-2-algorithm>: sendrier (our AVX2 implementation of Sendrier's shuffle), unrank (TLShuffle), djb
  (DJBSample) or sota
• <step-3-algorithm>: naive (the AVX2 implementation in the HQC submission) or mergenet (MWSupport).

Tests

Tests can be run using the ctest utility from CMake, by cding to the build folder and running ctest -j.
Alternatively, binaries are available to be run directly in the build/tests folder.

Benchmarks

Benchmarks are also available in the build/tests folder, and are not run by ctest.

System configurations to reduce benchmark noise and increase reproducibility

Prior to running the benchmarks, it is recommended to configure the system as discussed in Section 5.1 ("Benchmarking
methodology") of the paper. At a minimum, it is recommended to disable HyperThreading and TurboBoost and, if running
under Linux, select the performance CPU scaling governor.

We recommend disabling HyperThreading directly in the computer setup (BIOS/UEFI), as there may be small performance
differences compared to disabling it at the OS level. If the former option is not practical, the following command
can be used (requires root privileges), alhough we haven't tested it:

echo off | sudo tee /sys/devices/system/cpu/smt/control

TurboBoost can be disabled by issuing the following command (requires root privileges):

echo 1 | sudo tee /sys/devices/system/cpu/intel_pstate/no_turbo

The CPU scaling governor can be changed to performance, for all CPUs, through the following command (requires root
privileges):

echo performance | sudo tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor

Reproducing results from the paper

The build creates many benchmarking binaries. We now explain the mapping between these binaries and Tables 1, 4 and 5
of the paper, which display our results. All of these required the BUILD_X86_64 CMake configuration variable to be set
to ON.

Results in Table 1 were obtained by running bench_kem_x86_64_{1,3,5}. The column [HQC25] was obtained by configuring
the project with VECT_IMPL=default. The remaining columns, in the order found in the paper, were obtained by
configuring the project with VECT_IMPL set to sendrier_mergenet, unrank_mergenet, djb_mergenet and
sota_mergenet, respectively.

Results in Table 4 were obtained by running bench_step_2_sendrier_ref_x86_64_{1,3,5} for the column [HQC25]. For the
remaining columns, the project should be configured as described in the previous paragraph, and then running
bench_step_2_x86_64_{1,3,5}. Results should be identical if _mergenet is replaced by _naive for each choice of
VECT_IMPL.

Results in Table 5 were obtained by running bench_step_3_x86_64_{1,3,5}, again with different project configuration
options for each column. For [HQC25], VECT_IMPL should be set to *_naive, for any choice of step 2 algorithm. For
the "MWSupport" column, a step 2 algorithm which does not produce a sorted output should be selected (either Sendrier or
TLShuffle), by setting VECT_IMPL to either sendrier_mergenet or tlshuffle_mergenet. For the "MWSupport + sort"
column, a step 2 algorithm which produces a sorted output should be selected (either DJBSample or Sota), by setting
VECT_IMPL to either djb_mergenet or sota_mergenet.

License

Our work builds upon many other libraries and implementations, with different licenses for each. Any modifications that
we make to an existing work is released under the same original license as that work. As for our original code, we
release it under the Apache 2.0 license.