LWE Problem

お気持ち

LWE(Learning With Errors)問題とは秘密ベクトル $s\in {\mathbb{F}}_q^n$ に小さい誤差 $e$ を与えた近似合同線形方程式 $sA+e\equiv b(\mathrm{mod}q)$ が与えられた時, $s$
を復元する問題のことをいう. 適切なパラメータのLWE問題を解くことは非常に困難なことが知られており, 様々な暗号の困難性の根拠となっている.

ring-LWE Problem

LWE問題 を多項式環に拡張したもの.
$n$
2べき,
$q\equiv 1(\mathrm{mod}2n)$

困難性

SVP, LLLとかの話

• Lattice Estimator — Lattice Estimator 0.1 documentation
  • 実際の $\lambda$ を計算できる

modulus LWE

• malb.io/discrete-subgroup/slides/2018-01-15-deo.pdf watchlater

参考文献

• 2022-12-09 https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220801_03hiromasa.pdf