We provide the experimental results, which display in form of figures or tables in the article "https://eprint.iacr.org/2024/067.pdf". The paper has been accepted in PKC2024, if you want to cite it, please add the following bibtex in your paper:
@inproceedings{pkc-2024-33721,
title={A Refined Hardness Estimation of LWE in Two-step Mode},
publisher={Springer-Verlag},
author={Wenwen Xia and Leizhang Wang and Geng Wang and Dawu Gu and Baocang Wang},
year=2024
}We implement the test to verify the predicted success probability of each $d_{\rm svp}$ in solving an LWE instance. The test implemented code could be reproduced by lwe_prob_test.py in https://github.com/Summwer/test-for-refined-lwe-estimator. One can also see the test result in the folder test_dsvps_prob.
Besides the simulated success probability was implemented in the file lwechal-two-step.sage in the folder sage/lwechal-est of https://github.com/Summwer/lwe-estimator-with-pnjbkz/tree/refined-lwe-estimator.
To take a comparison between two-step mode and BKZ-only, we give two comparison estimation experiments.
One compares it to the leaky-LWE-estimator. The data about two-step mode is generated by the Two-step LWE Estimator we mentioned in the following text, one should run the file NIST-two-step.sage in the folder sage/NIST-round3 of https://github.com/Summwer/lwe-estimator-with-pnjbkz/tree/refined-lwe-estimator.
The other estimation compares it to the LWE estimate method mentioned in [ADPS16] (corresponding to the Appendix A in our article). One can reproduce the experiment in TwoStep_Cost_Simple_Model.py in the main directory and draw the Figure4 shown in the article.
To obtain the result of column $S_{\rm op}$ in Table1, one should run
./implement_all_NIST_schemes.shin the folder cpp of https://github.com/Summwer/lwe-estimator-with-pnjbkz/tree/refined-lwe-estimator. We've uploaded the result both in the online folder nist-round3-est-result in https://github.com/Summwer/lwe-estimator-with-pnjbkz/tree/refined-lwe-estimator.
To obtain the result of column $S_0$, one should run the file NIST-two-step.sage in the folder sage/NIST-round3 of https://github.com/Summwer/lwe-estimator-with-pnjbkz/tree/refined-lwe-estimator.
To obtain the result of column "Previous", one should run the file NIST-pro-bkz.sage in the folder sage/NIST-round3 of https://github.com/Summwer/lwe-estimator-with-pnjbkz/tree/refined-lwe-estimator.
Figure3 gives a detailed probability change related to cost. The relation information about two-step with the trivial blocksize strategy for NIST-scheme is the same as the file in the folder Table2&Table3/nist-est-log. The other information has been provided in the folder Figure3/lwechal-est-log and Figure3&Table1/nist-est-log , including the two-step success probability with the trivial blocksize strategy on lwechal and the two-step success probability with the optimized blocksize strategy generated by EnumBS on lwechal and nist-scheme.
In https://github.com/Summwer/lwe-estimator-with-pnjbkz/tree/refined-lwe-estimator, for the detailed two-step success probability with the optimized blocksize strategy generated by EnumBS, one should first generate the blocksize strategy by EnumBS (run ./lwechal-prob-test.sh for lwechal, ./implement_all_NIST_schemes.sh for nist schemes). Then, input the strategy and the parameter about lwechal/nist scheme in the file strategy_simulation_for_cum_prob.cpp and run ./strategy_simulation_for_cum_prob.sh to generate the detailed success probability for each dimension of Pump. The result will store in cpp/lwechal-prob-test/EnumBS(cumprob+prob)-simulation.log.
To generate the data of Table 2, one can run the file Lower_Bound_Estimation.py in the folder sage/NIST-round3/.
The strategy in Figure 5 and Figure 7 is generated by the enumbs in cpp and the normal two-step estimator in sage, and the logs are new-lwechal-EnumBS-Strategy(cumprob+prob)+practical-cost-model.log and trivial-strategy-practical-cost.log.