International Association for Cryptologic Research

International Association
for Cryptologic Research

EUROCRYPT 2024

The Hardness of LPN over Any Integer Ring and Field for PCG Applications:


README

      You can run our tool on Windows using the command line interface. Our script runs with Python 3 and the numpy library. The input format for our tool comprises 12 types, with 6 types tailored for exact LPN and the remaining 6 types for regular LPN. Assuming ``script.py'' (our tool) is in the "C:" directory.

==================Parameters==========
The order of command line parameters (n, N, k, t, lambda, q, exact/regular) is fixed, and we will explain their meanings. n: output length of dual LPN
N: number of samples 
k: dimension of LPN
t: Hamming weight of a noise vector
lambda: bit-length of ring Z_{2^lambda}
q: the size of finite field F, i.e., |F|=q
exact: for exact LPN
regular: for regular LPN

======================================================================================================================== There are three input formats for the primal LPN problem under an exact noise distribution:

The input format for estimating the bit security of exact LPN over binary field is ``C:\script.py N=1024 k=652 t=57 exact''

The input format for estimating the bit security of exact LPN over an integer ring of size 2^lambda is ``C:\script.py N=1024 k=652 t=57 lambda=13 exact''

The input format for estimating the bit security of exact LPN over a finite field of size |F|=q is ``C:\script.py N=1024 k=652 t=57 q=13 exact'' .
======================================================================================================================== There are three input formats for the dual LPN problem under an exact noise distribution:

The input format for estimating the bit security of exact dual LPN over binary field is ``C:\script.py n=1024 N=4096 t=88 exact''

The input format for estimating the bit security of exact dual LPN over an integer ring of size 2^lambda is ``C:\script.py n=1024 N=4096 t=88 lambda=13 exact''

The input format for estimating the bit security of exact dual LPN over a finite field of size |F|=q is ``C:\script.py n=1024 N=4096 t=88 q=13 exact''

======================================================================================================================== There are three input formats for the primal LPN problem under a regular noise distribution:

The input format for estimating the bit security of regular LPN over binary field is ``C:\script.py N=1024 k=652 t=57 regular''

The input format for estimating the bit security of regular LPN over an integer ring of size 2^lambda is ``C:\script.py N=1024 k=652 t=57 lambda=12 regular''

The input format for estimating the bit security of regular LPN over a finite field of size |F|=q is ``C:\script.py N=1024 k=652 t=57 q=13 regular''

======================================================================================================================== There are three input formats for the dual LPN problem under a regular noise distribution:

The input format for estimating the bit security of regular dual LPN over binary field is ``C:\script.py n=1024 N=4096 t=88 regular''

The input format for estimating the bit security of regular dual LPN over an integer ring of size 2^lambda is ``C:\script.py n=1024 N=4096 t=88 lambda=12 regular''

The input format for estimating the bit security of regular dual LPN over a finite field of size q is ``C:\script.py n=1024 N=4096 t=88 q=12 regular''