Relinearization Attack On LPN Over Large Fields
Abstract
We investigate algebraic attacks on the Learning Parity with Noise ($\mathsf{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\big(2^{d \log m}\big)$, 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 $\mathsf{LPN}$ polynomial system requires an $O(\sqrt{m})$ 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(\sqrt{m})$-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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 14, 2023
- Source ID
- 10.1093/comjnl/bxad070
Entities
People
- Amit Sahai
- Paul Lou
- Varun Sivashankar
Organizations
- Brain Sciences Foundation
- Defense Advanced Research Projects Agency
- University of California, Los Angeles