OpenFHE for pke schemes does not work correctly when NATIVE_SIZE=64 and 128-bit integers are disabled

[j2kun]

I have the following code pulled from the BGV tutorial:

CCParams<CryptoContextBGVRNS> parameters;
parameters.SetMultiplicativeDepth(2);
parameters.SetPlaintextModulus(65537);
CryptoContext<DCRTPoly> cryptoContext = GenCryptoContext(parameters);

This fails with the error

"external/openfhe/src/core/include/math/nbtheory-impl.h:332 
FirstPrime: Requested bit length 60 exceeds maximum allowed length 57"

My OpenFHE version is pinned to v1.1.2 (b2869ae) and I'm running with

MATHBACKEND=2

My config_core.h is

#define WITH_BE2
#define WITH_BE4
/* #undef WITH_NTL */
/* #undef WITH_TCM */

#define HAVE_INT64 TRUE
#define NATIVEINT 64
#define CKKS_M_FACTOR 1

[yspolyakov]

Hi @j2kun

Based on the error, it looks like you are using a configuration where INT128 is not available. The typical configuration for the 64-bit native backend is to use 128-bit words to store the result of multiplication. This maps to _unsigned __int128, which are available in g++ and clang++ compilers. Visual C++ does not support it. Is the environment you are running it on missing support of 128-bit integers, or you are simply not setting HAVE_INT128 to TRUE?

In the mode when INT128 is not available, the maximum modulus should be set to 57 bits (instead of default 60). I can give you more instructions if INT128 is not available in your configuration.

[j2kun]

I can enable INT128 but it seems I'm now running into this:

https://quuxplusone.github.io/blog/2019/02/28/is-int128-integral/#relationship-to-integer-types-and-intmax_t

external/openfhe/src/core/lib/math/hal/bigintfxd/ubintfxd.cpp:121:13: error: no matching function for call to 'GetMSB'
  121 |     m_MSB = lbcrypto::GetMSB(val);
      |             ^~~~~~~~~~~~~~~~
external/openfhe/src/core/include/math/nbtheory.h:167:24: note: candidate template ignored: requirement 'std::is_integral_v<unsigned __int128>' was not satisfied [with T = U128BITS]
  167 | inline constexpr usint GetMSB(T x) {

I'll try tinkering with my libc++/libstdc++

[pascoec]

The problem is in CryptoParametersBGVRNS::PrecomputeCRTTables(), which is passed an auxBits value of 60 from ParameterGenerationBGVRNS::ParamsGenBGVRNS() regardless of whether HAVE_INT128 is set or not. There needs to be an alternate default auxBits value used when HAVE_INT128 is false.

[yspolyakov]

I just looked through the code. It looks like BGV, BFV, and CKKS are hard-coding 60 bits, which is not supported when 128-bit are note available. Assigned this bug to Milestone 1.1.3.

[yspolyakov]

I suggest changing the implementation of modular multiplication so that we could support 60-bit moduli for the case when 128-bit integers are not available.

[yspolyakov]

@j2kun If possible, it is better to use the configuration when 128-bit integers are supported. This configuration is faster than the 64-bit only option (even after we fix the 57 vs 60-bit issue specific to the 64-bit only option)

[j2kun]

I can enable 128-bit ints, though I ran into #669 when trying to do that.

Is there a particular place in the documentation that is intended to explain how the compilation parameters connect to the functionality and/or compilability of the library?

[yspolyakov]

In CMakeLists.txt, the following code checks whether 128-bit and 64-bit integers are supported. This automatically sets HAVE_INT128 (to TRUE in g++ and clang++ environments).

# Size checks
include(CheckTypeSize)
check_type_size("__int128" INT128)
check_type_size("uint64_t" INT64)

You can also manually set it (overriding the automatically set value).

set( HAVE_INT128 TRUE)