# LWE problem Let $n,q$ positive integers, $\chi$ probability distribution over $\mathbb{Z}$ and $s$ be a secret random vector in $\mathbb{Z}^m$ . choose $a$ uniformly from $\mathbb{Z}^m_q$ , $e$ sampled from $\chi$ and considered in $\mathbb{Z}_q$ and returning $(a,\langle a,s\rangle+e)\in\mathbb{Z}^n_q\times\mathbb{Z}_q$ ## Decision problem decide if pairs $(a,c)$ are LWE instance or sampled uniformly from $\mathbb{Z}^n_q\times\mathbb{Z}_q$ ## Search problem find $s$ when given pairs of $(a,c)$ from a LWE instance. ## Equivalence of the problems It is known that [[Decision-LWE is equivalent to Search-LWE]] Related: [[Public key encryption scheme based on LWE]] Reference: [[@On the concrete hardness of Learning with Errors]] ## Created 2023-06-22 13:15