Predicting the Concrete Security of LWE Against the Dual Attack Using Binary Search.

The dual attack is widely used in the concrete security estimation of the learning with errors (LWE) problem. Predicting the concrete security of LWE against the dual attack, i.e., the minimal cost of the dual attack, is a constrained optimization problem. However, there is no complete theoretical analysis. We fill in this gap by proving that, for almost all LWE instances used in the design of public-key cryptographic schemes, the cost of the dual attack can be considered as a U-shape function. Therefore, we can predict the minimal cost with binary search. We use the binary search to predict the concrete security of all LWE-based algorithms in NIST-PQC and the experimental results demonstrate the accuracy of the binary search.