2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can $s$ be binary as well? If it is then this is the LPN problem (see crypto.stackexchange.com/questions/68164/…) $\endgroup$
    – lamba
    Commented Jul 11, 2022 at 8:30
  • $\begingroup$ 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. $\endgroup$
    – user102777
    Commented Jul 11, 2022 at 9:35

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.