solution

Trong mã hoá đối xứng kiểu Regev, một bit $\mu \in \{0,1\}$ được đóng gói thành $c = \langle a, s\rangle + e + \mu\lfloor q/2\rfloor \pmod q$ với $e$ nhỏ. Người biết $s$ giải mã bằng cách tính

$v = (c - \langle a, s\rangle) \bmod q,$

đưa về dạng cân trong $(-q/2, q/2]$, rồi kết luận $\mu = 1$ nếu $v$ gần $q/2$ (điều kiện $4|v| > q$), ngược lại $\mu = 0$.

Ví dụ: $q=8$, $a=(1,1)$, $s=(1,1)$, $c=7$: $v=(7-2)\bmod 8=5\to-3$, $4\cdot 3=12>8 \Rightarrow \mu=1$.