quarkslab/nfllib

NTT-based Fast Lattice library

NFLlib

An NTT-based Fast Lattice library

Goal

NFLlib is an efficient and open-source C++ library dedicated to ideal lattice cryptography. It is specialized in polynomial rings quotiented by a cyclotomic polynomial whose degree is a power of two. The library combines algorithmic optimizations (Chinese Remainder Theorem, optimized Number Theoretic Transform) together with programming optimization techniques (SSE and AVX2 specializations, C++ expression templates, etc.).

License

MIT

Install Steps

You need cmake, GMP and Mpfr, as well as a C++11 compiler to build NFLLib.

To build, test and install a production version of nfllib, run the following:

$> mkdir _build
$> cd _build
$> cmake .. -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=$HOME/nfllib
$> make
$> make test
$> make install

The following CMake options are relevant:

Option	Description
-DCMAKE_INSTALL_PREFIX=<value>	Where the library is installed
-DCMAKE_BUILD_TYPE=Release|Debug	The basic compiler configuration
-DNFL_OPTIMIZED=ON	Enable SSE/AVX-based optimization

SSE/AVX optimizations

To use SSE-based optimizations, compile the code with the flags -DNFL_OPTIMIZED=ON -DNTT_SSE.

To use AVX-based optimizations, compile the code with the flags -DNFL_OPTIMIZED=ON -DNTT_AVX2.

Getting started

In order to get the documentation you need Sphinx and the Alabaster theme. Installation procedures are described at (we recommend using pip for both installations) :

• http://www.sphinx-doc.org/en/stable/install.html
• https://anaconda.org/pypi/alabaster

After getting both Sphinx and the Alabaster theme build the documentation and show it with:

$> sphinx-build . build
$> your_favorite_browser build/nfl.html

If you have issues building the documentation please contact the developper team.

Contributors

This library is an extension/evolution of the NTTTools module from XPIR done by members of CryptoExperts, INP ENSEEIHT, Quarkslab (in alphabetical order).

nfllib's Issues

Errors in NFLlib Installation

I followed the steps to install NFLlib (in Ubuntu 18.04), but I'm running into some problems. Everything is fine until I run make test. Then, I get the following result:

95% tests passed, 6 tests failed out of 122

Total Test time (real) = 11.14 sec

The following tests FAILED:
98 - run_nfllib_demo1048576_124_uint64_t_op (Child aborted)
100 - run_nfllib_demo1048576_124_uint64_t_func (Child aborted)
108 - run_nfl_eq1048576_124_uint64_t (Child aborted)
110 - run_nfl_neq1048576_124_uint64_t (Child aborted)
114 - run_poly_p1048576_124_uint64_t (SEGFAULT)
118 - run_poly_mpz1048576_124_uint64_t (SEGFAULT)
Errors while running CTest
Makefile:97: recipe for target 'test' failed
make: *** [test] Error 8

Does anyone know why these tests are failing or what I can do about it?

I've also tried compiling the file nfllib_demo_main_func.cpp. But I get the following errors:

nfllib_demo_main_func.cpp: In function ‘int main()’:
nfllib_demo_main_func.cpp:122:14: error: ‘CONFIG’ was not declared in this scope
return run();
^
nfllib_demo_main_func.cpp:122:22: error: no matching function for call to ‘run()’
return run();
^
nfllib_demo_main_func.cpp:28:5: note: candidate: template<long unsigned int degree, long unsigned int modulus, class T> int run()
int run()
^
nfllib_demo_main_func.cpp:28:5: note: template argument deduction/substitution failed:
nfllib_demo_main_func.cpp:122:22: error: template argument 1 is invalid
return run();

If anyone could help with these issues, I would be very appreciative.

when using nfllib on mac, some errors occurred

previously, make test, everything is ok.
but when i run a program that use this nfllib, some error occurs:

In file included from /Users/xietiany/nfllib/include/nfl/poly.hpp:26:
/Users/xietiany/nfllib/include/nfl/ops.hpp:257:60: error: too many arguments
provided to function-like macro invocation
auto make_op(Args const&... args) -> decltype(_make_op<Op, Args...>{}(args...))
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__config:609:11: note:
macro 'decltype' defined here

define decltype(__x) __decltype(__x)

      ^

In file included from src/main.cpp:7:
In file included from src/ibe/user.hpp:7:
In file included from src/params.hpp:8:
In file included from /Users/xietiany/nfllib/include/nfl.hpp:17:
/Users/xietiany/nfllib/include/nfl/poly.hpp:346:1: error: too many arguments
provided to function-like macro invocation
DECLARE_BINARY_OPERATOR(operator-, submod)
^

ntt_perfs is faster than the ntt method in the library.

Hi,
I found that the 'ntt_new' method in 'tests/ntt_pefs.cpp' is 2x faster than the ntt_loop in the NFLib, even I used AVX and SSE opts.

Can any one tell me why this performance gap happen ?

Undefined reference to "nfl::params<unsigned int>::P"

I was able to successfully build the library, and all tests are successful during the build. However, I encountered the following error when compiling a simple test program:

/usr/bin/ld: /tmp/ccKiADHL.o: in function `nfl::poly<unsigned int, 512ul, 1ul>::get_modulus(unsigned long)':
main2.cpp:(.text._ZN3nfl4polyIjLm512ELm1EE11get_modulusEm[_ZN3nfl4polyIjLm512ELm1EE11get_modulusEm]+0x1b): undefined reference to `nfl::params<unsigned int>::P'
collect2: error: ld returned 1 exit status

I ran the following to compile the program:

g++ -I/root/nfllib/include -L/root/nfllib/lib -lnfllib -lnfllib_static main2.cpp

This is the source code for my program:

#include "nfl.hpp"

using poly_type = nfl::poly_from_modulus<uint32_t, 512, 30>;

int main(int argc, char *argv[])
{
    poly_type P;
}

Is there anything wrong with my source code above? I appreciate any help on how I can resolve this error. Thank you.

Please add a cmake variable for native optimizations (-march=native)

It's needed for packaging.

make error under macOS

after I enter the command make，the following prompts：

clang: error: unsupported argument '-q' to option 'Wa,'
make[2]: *** [CMakeFiles/nfllib_static.dir/lib/params/params.cpp.o] Error 1
make[1]: *** [CMakeFiles/nfllib_static.dir/all] Error 2
make: *** [all] Error 2

How can I fix it？

NTT/INTT operations seemingly giving wrong values

I am attempting to perform an NTT operation like so: output=INNT(NTT(input_1)*NTT(input_2)).

I have tried with the following code:

#include <memory>
#include <nfl/poly.hpp>

static constexpr size_t qNum = 1;
static constexpr size_t N = 32;

nfl::poly<uint64_t, N, qNum> nfl_1, nfl_2, nfl_3;

int main(int argc, char *argv[]) {

  uint64_t input_1[] = {0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0,
                        0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1};
  uint64_t input_2[] = {0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0,
                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

  memcpy(nfl_1.begin(), input_1, sizeof(uint64_t) * N);
  memcpy(nfl_2.begin(), input_2, sizeof(uint64_t) * N);

  nfl_1.ntt_pow_phi();
  nfl_2.ntt_pow_phi();
  nfl::mul(nfl_3, nfl_1, nfl_2);
  nfl_3.invntt_pow_invphi();

  return 0;
}

From other NTT implementations that I've used (e.g. sympy or rug-fft) I would expect the output to be

{2, 3, 1, 2, 2, 3, 3, 4, 2, 5, 3, 3, 3, 5, 2, 3, 3, 1, 3, 3, 1, 2, 2, 3, 3, 2, 3, 2, 3, 2, 2}

however instead I find the data in nfl_3 to be

{4611686018326724607, 4611686018326724606, 4611686018326724608, 0, 0, 4611686018326724608, 3, 2, 2, 3, 3, 3, 3, 5, 2, 3, 3, 3, 1, 3, 3, 1, 2, 2, 3, 3, 2, 3, 2, 3, 2, 2}

Am I do something wrong here? The data actually agrees in the second half but not the first. I find the big numbers particularly confusing. Why are they there?

Which discrete Gaussian sampling algorithm does NFLlib use?

Thanks.

make test in linux, some errors occurred

98% tests passed, 3 tests failed out of 122

Total Test time (real) = 39.94 sec

The following tests FAILED:
98 - run_nfllib_demo1048576_124_uint64_t_op (SEGFAULT)
114 - run_poly_p1048576_124_uint64_t (SEGFAULT)
118 - run_poly_mpz1048576_124_uint64_t (SEGFAULT)
Errors while running CTest
Makefile:127: recipe for target 'test' failed
make: *** [test] Error 8

when using nfllib on ubuntu18.04 some errors occurred

previously, make test, everything is ok! But I don't konw how to use nflib. there are no example .can U support some example,ths
There are my error:

knight@knight:~/nfllib/tests$ g++ -Ilib -lnfllib_static.a -std=c++11 Test_simple.cpp ../include/nfl.hpp
Test_simple.cpp:27:10: fatal error: nfl.hpp: 没有那个文件或目录
#include <nfl.hpp>
^~~~~~~~~
compilation terminated.
In file included from ../include/nfl.hpp:17:0:
../include/nfl/poly.hpp:23:10: fatal error: nfl/debug.hpp: 没有那个文件或目录
#include "nfl/debug.hpp"
^~~~~~~~~~~~~~~
compilation terminated.

I don't konw how to do!

install problem

Following the installation process, everything seems to be normal when it comes to cmake, but then there is a problem with make.


How can I solve this problem? Or is it something I haven’t configured properly?

Does not link (avx code) on OSX

GCC isn't able to link avx code on osx. It needs to use llvm for this purpose.
A PR follows (only adds a few lines to CMakeCompilers.txt)

Issue for uint16_t type and n=512

Hi,

I'm implementing a RLWE key exchange protocol. It seems there is a problem with uint16_t type and n=512 case. For key exchange, k1=(as_2+e_2)s_1+e_1', k2=(as_1+e_1)s_2+e_2'. Theoretically, k1 should approximately equals to k2. a is uniformly random, s_1, s_2, e_1, e_2, e_1', e_2' is sampled from discrete Gaussian distribution with standard deviation 3.2.

My implementation works for n=512 and uint32_t type case, but does not work for uint16_t case. I checked value of k1 and k2, they are not approximately equal in uint16_t case. When I implement with other library using same parameters defined in uint16_t case, it works. I didn't change parameters defined in params.hpp.

Do you have any suggestions where the problem is?

Thanks.

Any future plan to support divide-and-rounding operation for the RNS/CRT format ?

• Implementation and Performance Evaluation of
  RNS Variants of the BFV Homomorphic Encryption
  Scheme

Operations between two polynomials with different number of modules.

• It seems that NFlib does not support operations between polynomials with different modulus.
• Since, the all prime modulus are pre-defined, the following implementation should be well-defined as well. :) .

template <size_t N1, size_t N2>
struct  Max {
  enum { N = N1 > N2 ? N1 : N2 };
};

template <size_t N1, size_t N2>
struct  Min {
  enum { N = N1 < N2 ? N1 : N2 };
};

template <typename T, size_t D, size_t N0, size_t N1>
poly<T, D, Max<N0, N1>::N> operator+(
  poly<T, D, N0> const& op0,
  poly<T, D, N1> const& op1)
{
  size_t N = Min<N0, N1>::N;
  const T *op0_ = op0.begin();
  const T *op1_ = op1.begin();

  poly<T, D, Max<N0, N1>::N> rop;
  T *rop_ = rop.data();
  nfl::ops::addmod<T, nfl::simd::serial> adder;
  for (size_t cm = 0; cm < N; ++cm) {
    for (size_t i = 0; i < D; ++i)
      *rop_++ = adder(*op0_++, *op1_++, cm);
  }

  if (N0 > N)
    std::memcpy(rop_, op0_, sizeof(T) * D * (N0 - N));
  else
    std::memcpy(rop_, op1_, sizeof(T) * D * (N1 - N));

  return rop;
}

template <typename T, size_t D, size_t N0, size_t N1>
poly<T, D, Max<N0, N1>::N> operator*(
  poly<T, D, N0> const& op0,
  poly<T, D, N1> const& op1)
{
  size_t N = Min<N0, N1>::N;
  const T *op0_ = op0.begin();
  const T *op1_ = op1.begin();

  poly<T, D, Max<N0, N1>::N> rop;
  T *rop_ = rop.data();
  nfl::ops::mulmod<T, nfl::simd::serial> mul;
  for (size_t cm = 0; cm < N; ++cm) {
    for (size_t i = 0; i < D; ++i)
      *rop_++ = mul(*op0_++, *op1_++, cm);
  }
  return rop;
}

Compilation issue

Hi everyone,

I ran into some problems with the "make test" (I follow the build instructions on the github). Many tests (53 or 101 out of 122) fail to compile because of missing refs to chrono related functions. Adding a "#include " to tests/tools.h fix this.

Then I run inot other issues. Tests 98, 114 and 118 segfault.
Let me know what information you need to tackle that !

Guillaume

Why this Specified Format of Primes ?

NFL uses 2^62 - i * 2 * kMaxPolyDegree + 1 primes.
Does any reason for this specific form ? Could we use any other 62-bit long prime ?

Releases

Hi,

What do you think of doing releases of NFLlib (so that it could be handle by package managers)?

Linkage issue for multiple-source files

I created a project with several .cpp source files that #include <nfl.hpp>. When I link my code with the library I get the following linker error:

multiple definitions of « nfl::newton_raphson(double, double, int) »

Indeed, the function is implemented in the header file NFLlib/include/nfl/prng/FastGaussianNoise.hpp (line 136), so is defined in every of my .cpp files that includes it. A quick fix would be to mark it inline; alternatively to move its implementation to a .cpp file compiled in the library.

How is Gaussian sampling in NFLlib parameterized?

I'm looking into this library and would like to bound l2-norm of a vector sampled from discrete Gaussian distribution. A sampled vector example (n=1024, \sigma=3) is here. Is the distribution parameterized as e^(-x^2/(2\sigma^2)) or e^(-\pi*x^2/s^2)?

I'm trying to verify the bound of l2-norm of above vector using lemma 2.5 in this paper, where the norm of my example vector is 96.13, which is larger than r=1 case (sqrt(3^21024)) for lemma 2.5 in above paper. Since the probability of norm > sqrt(3^21024) should extremely small, I would like to know how the discrete Gaussian distribution in NFLlib is parameterized.

Thanks

"serialize_manually" functions should be marked "const"

`set(CMAKE_MODULE_PATH ${CMAKE_CURRENT_SOURCE_DIR}/cmake)`

https://github.com/quarkslab/NFLlib/blob/master/CMakeLists.txt#L33

should be

set(CMAKE_MODULE_PATH ${CMAKE_CURRENT_SOURCE_DIR}/cmake)

so NFLlib can be included from add_subdirectory

Don't compile tests with make

Is it possible to modify the cmake files to avoid the compilation of the tests when only "make" is used?

Am I doing something completely wrong ?

2 options : either I am completely wrong or there are enormous bugs (I tried a commit from last year but got the same behaviour) .... I'd prefer the first option.

x={1,2,3,4,5,6,7,8}; y={0};
(x==y) returns TRUE !

x={1,2,3,4,5,6,7,8}; y={1};
z=x*y;
// after that z={1} !

See the following commit for the full example :
Kirija@8b24259

Can you give some demo of using your polynomial operations?

Can you add some simple demo to show us like
how to generate a random polynomial?
how to do multiplication of two polynomials f,g in Z_q[x]/(x^n+1)?
As your library does not have detailed documentations as NTL, got loss of how to call this library.