gvilitechltd / libswifft Goto Github PK

This makes it easy to navigate.

Describe the bug
When I use the arithmetic function SWIFFT_Add, the result has no additive homomorphism.
How do I make the input operation to obtain additive homomorphism.
I tried addition of elements-wise and addition of the whole input, but I was unable to verify the additive homomorphism.

My code:

#include <iostream>
#include "libswifft/swifft.h"

using namespace std;

int main ()
{
    SWIFFT_ALIGN BitSequence input0[SWIFFT_INPUT_BLOCK_SIZE];
    for (int i = 0; i < SWIFFT_INPUT_BLOCK_SIZE; i++)
    {
        input0[i]= rand()%2;
        printf("%d", input0[i]);
    }
    SWIFFT_ALIGN BitSequence output0[SWIFFT_OUTPUT_BLOCK_SIZE];
    SWIFFT_Compute(input0, output0);
        cout << "index 0" << endl;
    for (int j = 0; j < SWIFFT_OUTPUT_BLOCK_SIZE; j += 2)
    {
        printf("%d\n", output0[j]);
    }

cout << "\n";
        SWIFFT_ALIGN BitSequence input1[SWIFFT_INPUT_BLOCK_SIZE];
    for (int i = 0; i < SWIFFT_INPUT_BLOCK_SIZE; i++)
    {
        input1[i]= rand()%2;
        printf("%d", input1[i]);
    }
    SWIFFT_ALIGN BitSequence output1[SWIFFT_OUTPUT_BLOCK_SIZE];
    SWIFFT_Compute(input1, output1);
        cout << "index 0" << endl;
    for (int j = 0; j < SWIFFT_OUTPUT_BLOCK_SIZE; j += 2)
    {
        printf("%d\n", output1[j]);
    }

    cout << "\n";
        cout << "SWIFFT_Add" << endl;
    SWIFFT_Add(output0, output1);
    for (int l = 0; l < SWIFFT_OUTPUT_BLOCK_SIZE; l+=2)
    {
        printf("%d\n", output0[l]);
    }
    cout << "\n";

    
    SWIFFT_ALIGN BitSequence inputxor[SWIFFT_INPUT_BLOCK_SIZE];
for (int i = 0; i < SWIFFT_INPUT_BLOCK_SIZE; i++)
    {
        
       printf("%d", inputxor[i]);
    }

    SWIFFT_ALIGN BitSequence outputxor[SWIFFT_OUTPUT_BLOCK_SIZE];
    SWIFFT_Compute(inputxor, outputxor);
    cout << "xor" << endl;
    for (int j = 0; j < SWIFFT_OUTPUT_BLOCK_SIZE; j+=2)
    {
        printf("%d\n", outputxor[j]);
    }
}

Results:

Environment (please complete the following information):

• Platform: [desktop ]
• OS and version: [e.g. Ubuntu 20.04 LTS]
• Tool-chain and version [e.g. GCC 10.3.0]
• LibSWIFFT version [e.g. v1.2.0]

The cycle limits of SWIFFT_fft and SWIFFT_fftsum should sum to that of SWIFFT_Compute, which invokes them.

This is not really important but it would be nice if there are instructions to setup a test virtual environments like Docker and Singularity.

In this case a developer can clone the repo, and with in a few seconds, they just run a Docker command or Singularity command and the software is installed and tests are running.

Please close the issue if this is not a feature necessary at this moment.

Is your feature request related to a problem? Please describe.
There are currently multiple sets of similarly-named functions in LibSWIFFT, in particular for AVX, AVX2, and AVX512. In the future, there may be more. As currently organized, it is not easy for calling-code to easily switch between such sets.

Describe the solution you'd like
The SWIFFT object APIs are interfaces of function pointers to existing functions in LibSWIFFT. They will be divided into these topics:

• FFT: the SWIFFT_fft and SWIFFT_fftsum functions.
• Arithmetic: the functions providing SWIFFT arithmetic operations.
• Hash: the functions providing SWIFFT hash operations.

Describe alternatives you've considered
An alternative is providing interfaces as C++ classes. The disadvantage is that such code would not be available to C callers.

See openjournals/joss-reviews#3040 (comment)

See discussion.

To migrate:

• Remove old markdown files (contributing, release-checklist, roadmap) at the root directory
• Change the readme file to include a brief and a pointer to https://libswifft.readthedocs.io/

Is your feature request related to a problem? Please describe.
It is currently not convenient to obtain performance measurements comparing LibSWIFFT and K2SN-MSS binary 16-bit SWIFFT functions. Such a comparison would allow one to conveniently evaluate claims about LibSWIFFT's high-performance. See discussion.

Describe the solution you'd like
An automated performance comparison procedure that would pull K2SN-MSS code, build an executable that links with both LibSWIFFT code and the pulled K2SN-MSS code, and run the executable to obtain the performance measurements.

Describe alternatives you've considered
An alternative is to point the user to K2SN-MSS code along with build and performance testing instructions, and how to compare the performance measurements obtained to those of LibSWIFFT. This is not as convenient an alternative as the proposed one.

Additional context
N/A.

Add documentation pages for new users, like on GitHub pages or read-the-docs.

The installation instruction fail because a C++ compiler is not installed automatically. The line:

sudo apt-get install g++

should be added after sudo apt-get install gcc in the "Building LibSWIFFT" section.

Some available services to use
GitHub Actions
Appveyor
travis
Cicle CI

Update the doxygen instructions in the release-checklist with these instructions:

• Create a virtualenv with pip3 install -r docs/requirements.txt and activate it.
• Run make html from the docs directory.

Move the release-checklist to be part of the docs.

See openjournals/joss-reviews#3040 (comment)

Edit docs/index.rst to include the LibSWIFFT logo assets/LibSWIFFT-logo.png at the top of the page.

See discussion.

Add performance testing code to fork of K2SN-MSS. Compare cycles-per-byte of the 16-bit SWIFFT function to that of LibSWIFFT.

See discussion.

Is your feature request related to a problem? Please describe.
Some lattice-based constructions, such as streaming verifiable computation, use a sum of hash values and require a modulus larger than 257 currently supported by LibSWIFFT.

Describe the solution you'd like
Add support for certain larger moduli such that many more short vectors can be aggregated while maintaining high performance. The suggested moduli are the Fermat prime q=2^{16}+1 and the Mersenne prime q=2^{31}-1. The modular arithmetic operations for these moduli likely fit within 32-bit and 64-bit respectively. These moduli should also allow for high performance because they are one-off from a power of 2.

Describe alternatives you've considered
Other moduli besides the suggested ones were considered. For performance reasons, Fermat and Mersenne primes, being one-off from a power-of-2, are good candidates. There is only one known Fermat prime 2^{16}+1 that is larger than 257. It should be a good fit for a 32-bit register the same way 257 is a good fit for a 16-bit register. There is no Mersenne prime that is a better fit for a 32-bit register. For a 64-bit register, the best fitting Mersenne prime is 2^{31}-1.

Additional context
N/A.

The caching of Catch2 caused a build failure:

Run if [[ "$CACHE_HIT" == 'true' ]]; then
Install the project...
-- Install configuration: ""
CMake Error at cmake_install.cmake:58 (file):
  file cannot create directory: /usr/local/lib/cmake/Catch2.  Maybe need
  administrative privileges.

The fix is to add "sudo" to the Catch2 install command.

Is your feature request related to a problem? Please describe.
SWIFFT APIs are currently performance-optimized only for single-threaded execution. This risks leading to many multi-threaded applications developing different implementations of parallel SWIFFT API execution and to inconsistent SWIFFT performance in multi-threaded applications.

Describe the solution you'd like
Add multiple-block versions of SWIFFT APIs with OpenMP implementation. OpenMP is suitable for block-parallelization of SWIFFT API execution, since each block computation is constant-time and memory-localized while cache lines are not shared across blocks (i.e., false sharing is avoided). OpenMP is standard and relatively straightforward to use for this task.

Describe alternatives you've considered
A well-known alternative is Intel Threading Building Blocks, which is not as straightforward to use as OpenMP and does not seem to offer a way to obtain better performance than using OpenMP for this task. Kokkos is a promising alternative focused on performance portability and can be considered in the future.

Additional context
N/A.