openfheorg / openfhe-development

This is the development repository for the OpenFHE library. The current (stable) version is v1.2.0 (released on June 25, 2024).
BSD 2-Clause "Simplified" License
663 stars 170 forks source link

Inaccurate log Q(P) used for the initial estimation when checking compliance with LWE security tables #774

Closed yspolyakov closed 1 month ago

yspolyakov commented 1 month ago

There are two related problems that affect specific use cases:

  1. HYBRID key switching only (BGV, BFV, and CKKS): In the initial estimation, we use $\lceil \log Q/(d_{num} \log p_i) \rceil * \log p_i$. But later we use the maximum discrete size of each (large) digit in $Q$. Sometimes this leads to an increased value of $P$ (by 1 extra RNS limb).
  2. For BGV and BFV noise flooding in threshold FHE, we do not consider the extra modulus size during the compliance check with LWE tables.

Since the estimation is used to determine the minimum ring dimension that achieves the desired security level, this may lead crypto parameters that require a smaller work factor than prescribed by the selected security level. For example, although the user specifies 128 bits of security, the resultant parameters may only achieve 110 bits of security or so.

We need to update the estimation logic to use accurate $\log Q$ and $\log P$ when finding the minimum ring dimension parameter that achieves the desired security level for a given application.