I recently studied the LPN problem and BKW algorithm for solving LPN problem. Several papers deal with the concrete parameters of LPN to be secure against BKW algorithm, but I cannot measure the concrete complexity of BKW algorithm. The papers provided the concrete parameters when the memory space is bounded by $2^{60}$ or $2^{80}$ while I cannot understand how to set those parameters.

Is there a LPN estimator? or estimator of BKW algorithm? If not, how to measure the concrete parameters of BKW algorithm?

  • $\begingroup$ Which paper do you have in mind? As far as I know, some parameters are suggested in eprint.iacr.org/2017/078, and their security estimation algorithm can be found in github.com/Memphisd/LPN-decoded. $\endgroup$
    – Hhan
    Jan 25 '21 at 7:59
  • $\begingroup$ As I know, the code implemented the BKW attack, but what I want is just estimate the concrete security for simplicity. $\endgroup$ Jan 25 '21 at 8:05
  • $\begingroup$ No, the code is for estimating the security. See the bottom of page 23 in the paper. (In particular, the code does not take any concrete LPN instance as its input.) $\endgroup$
    – Hhan
    Jan 25 '21 at 8:14
  • $\begingroup$ @Hhan Thanks you! $\endgroup$ Jan 26 '21 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.