Relinearization Attack On LPN Over Large Fields

We investigate algebraic attacks on the Learning Parity with Noise (LPN) problem over large fields in parameter settings relevant to building indistinguishability obfuscation in which the proportion of corrupted equations is inverse-polynomially sparse. Our aim was to obtain a subexponential algorithm using the Macaulay expansion and relinearization. Alas, we did not. Nevertheless, our findings suggest an interesting relation between runtime and the rank of the Macaulay expansion. The runtime of this attack is O(2(d log m)), where m is the number of initial equations and d is the degree of the Macaulay expansion. If the resulting system of equations has sufficiently large rank, we show that solving the LPN polynomial system requires an O(vm) degree expansion, which would imply a subexponential attack. Under the (more widely believed) assumption that the expanded system is semi-regular, however, we show that an O(m) degree expansion is required to recover the secret vector. Since O(vm)-degree expansions may not have sufficient rank, we propose a randomized algorithm which introduces carefully chosen equations that hold with high probability to increase the rank and improve the likelihood of a successful attack. We highlight the empirical and theoretical challenges in analyzing this approach. Our code is available at www.tinyurl.com/attacklpn.