# LWE with a binary matrix A

In LWE, we know that given reasonable public parameter $$A\in \mathbb{Z}_q^{n\times \lambda}$$, secret $$s\in \mathbb{Z}_q^{\lambda}$$ and noise $$e\in \mathcal{X}^{n}$$, random $$r\in \mathbb{Z}_q^{n}$$, $$(A, b = A\cdot s + e)$$ and $$(A, r)$$ are computationally indistinguishable.

Then, consider another scenario that $$A$$ is sampled from a sub-filed of q. For example, set $$A\in \mathbb{Z}_2^{n\times \lambda}$$, and others are the same as above. At this time, are $$(A, b = A\cdot s + e)$$ and $$(A, r)$$ still computationally indistinguishable.

Similar to question LWE problem with a sparse matrix, but $$A$$ is formed by binary random linear codes.

• Can $s$ be binary as well? If it is then this is the LPN problem (see crypto.stackexchange.com/questions/68164/…) Commented Jul 11, 2022 at 8:30
• Thanks for your reply @lamba. LPN seems not what I'm concerned. In fact, I'm wondering if $A\cdot s + e$ is computationally indistinguishable from a list of real random numbers, is it possible to use it as random masks for additive secret sharing? For LPN, only binary masks with noises are provided, which cannot be used as masks as I think. Commented Jul 11, 2022 at 9:35

The LWE problem is only believed to be hard when A is uniformly random, and, in fact, can easily be broken in special cases such as when A is binary or have some kind of very special structure.

Note that there exists extended LWE version over polynomial rings where (essentially) all columns in the matrix A is just rotation of the first column (this can also be extended to modules, where A is a block matrix where each block has a new, random first column, see survey on Ring-LWE and Module-LWE schemes by Vadim Lyubashevsky). I acknowledge that this is somewhat different than what you asked about initially.

My understanding is that when $$A$$ is binary, the problem is completely broken by this paper:

LP Solutions of Vectorial Integer Subset Sums - Cryptanalysis of Galbraith's Binary Matrix LWE Alexander May and Gottfried Herold https://eprint.iacr.org/2018/741

This variant of LWE is secure provided that the security parameter is increase by a factor of $$O(\log q)$$ (even the paper linked by @LeoDucas mentions this at the end of Section 2).

The variant of LWE with a binary matrix is known as the Non-uniform LWE (NLWE) problem [1] because in the general case, $$A$$ can be chosen from any (reasonable) non-uniform distribution in the field.

[1] D. Boneh, K. Lewi, H. W. Montgomery, and A. Raghunathan. Key homomor- phic PRFs and their applications. https://eprint.iacr.org/2015/220.pdf