0
$\begingroup$

This may be a naive question:

LWR assumption states that for ${A} \stackrel{$}{\leftarrow} \mathbb{Z}^{m \times n}_q, s \stackrel{$}{\leftarrow} \mathbb{Z}^n_q$, given $(A, \lfloor A\cdot s \rfloor_p$), it is indistinguishable from $(A, u)$ with $u \stackrel{$}{\leftarrow} \mathbb{Z}^m_p$. There seems to be no specific condition on $m$ and $n$ except $m,n \geq 1$.

My question is does this hold true for $m = n = 1$? It does not seem right to me, kindly explain.

$\endgroup$
2
$\begingroup$

There seems to be no specific condition on $m$ and $n$ except $m,n \geq 1$.

The LWR assumption isn't that the problem is hard for any arbitrary $m, n$, it's there it's true for the specific $m, n$ pairs we use in practice. Obviously, for $m=n=1$, it's an easy problem; that's not particularly relevant, as we don't use $m=n=1$.

This is similar to the RSA assumption; that assumption isn't that it's a hard problem for arbitrary sized keys (it's not for, say, 10 bit keys); it's that it's a hard problem for the key sizes we use in practice (for example, 3072 bit correctly generated keys).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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