リング-LWE
リング-LWE（Learning With Errors over Rings）問題は、LWE（Learning With Errors）問題の一般化であり、多項式リング上で定義される。LWE問題が線形代数の概念に基づくのに対し、リング-LWEは代数的数論と多項式の概念を利用する。リング-LWE問題の定義には、多項式リング、誤差項、秘密の多項式などが関係する。
リング-LWE問題の主な概念は、ある固定された多項式リング $ \mathbb{Z}_q[x] / \langle f(x) \rangle において、ランダムな多項式 $ a(x) と秘密の多項式 $ s(x) 、そして小さな誤差多項式 $ e(x) を用いて、次のような形式の多項式 $ b(x) = a(x)s(x) + e(x) を考えることである。ここで、$ q は素数であり、$ f(x) はリングを定義する既約多項式である。
リング-LWEの問題は、与えられた多項式のペア $ (a(x), b(x)) から秘密の多項式 $ s(x) を推測することが非常に困難である、ということに基づいている。これは、小さな誤差 $ e(x) の存在が、秘密の多項式 $ s(x) を復元することを著しく難しくするためである。
リング-LWEの安全性は、数学的に困難な問題に基づいており、現代の量子コンピュータに対しても安全であると考えられている。この問題は準同型暗号スキームやその他の暗号プロトコルの構築において、重要な役割を果たす。
リング-LWE問題の具体的な応用例としては、キー交換、デジタル署名、秘密分散などがある。これらの暗号プロトコルは、リング-LWE問題の計算上の困難さを安全性の根拠として利用している。