0
$\begingroup$

As we know in block ciphers, the distinguisher means that despite thousands ciphertexts (and plaintexts), allows an attacker to distinguish the encrypted data from random data. This attack is important because the secret key is ofen applied once related to many ciphertext.

My first question is what does it mean the distinguisher in LWE problem in which the secret key changes constantly for each ciphertext and plaintext pair?

The second question is how much does it(distinguishing) cost in LWE attack such as dual and primal attack?

Improve this question
$\endgroup$
2
  • $\begingroup$ The premise is not correct. One may not need thousands to distinguish! $\endgroup$
    – kelalaka
    Commented Feb 10 at 13:56
  • $\begingroup$ Yes, but i consider Known plaintext attack. $\endgroup$
    – R_Jalaei
    Commented Feb 12 at 7:07

1 Answer 1

Reset to default
1
$\begingroup$

what does it mean the distinguisher in LWE problem in which the secret key changes constantly for each ciphertext and plaintext pair?

this isn't true, so if you have a particular source that is claiming that and leading to your confusion you should probably link it. The correct definitions are below.

The LWE problem can be stated as follows.

LWE Distribution: For $\vec s\in\mathbb{Z}_q^n$, let $\mathsf{LWE}_{n,q,\chi}(\vec s)$ be the distribution that samples $\vec a\gets \mathbb{Z}_q^n$ and $e\gets \chi$, and then outputs $(\vec a, \langle \vec a,\vec s\rangle + e)$.

Here $\chi$ is a "concentrated" distribution on $\mathbb{Z}$. Typical examples are discrete Gaussians, or bounded uniform cdistributions $\{-B,-B+1,\dots, B-1,B\}$, though there are many choices possible.

LWE Problem: An adversary is given query access to an oracle $\mathcal{O}$ that is either

  1. Uniform: Uniform samples $(\vec a, u)\gets \mathbb{Z}_q\times \mathbb{Z}$, or
  2. LWE: For $\vec s\gets \mathbb{Z}_q^n$, the oracle $\mathsf{LWE}_{n,q,\chi}(\vec s)$,

And must determine which oracle they are given.

This is to say that the secret $\vec s$ is fixed. Note that sampling $\vec s\gets \mathbb{Z}_q^n$ is one choice, but one can also sample $\vec s\gets \chi^n$ without degrading the security of the problem (and in applications to homomorphic encryption this is preferrable).

The fact that $\vec s$ is fixed is vital to be able to prove security of cryptosystems. Without this assumption, you could prove security to encrypt a single integer, but I don't see how you could do much else, e.g. the cryptosystem would be "one-shot".

Improve this answer
$\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.