与える誤差の度合いによってLWE問題の難易度が決まります。LWE暗号というと、このLWE問題の計算量困難性に依存した暗号技術のことを指します。以下の3つの理由からLWE問題は解くことが難しいと信じられています。その3つ目の一番重要な理由が格子問題を使っているので、LWEは格子暗号に分類されます。知られている中でもっとも良いLWE問題を解くアルゴリズムの実行時間が指数時間である(量子コンピュータでさえも計算速度を速くできない)LWE問題はLPN問題の一般化であり、LPN問題は解くのが困難な問題と予想されている。LPN問題はランダム線型バイナリ符号から復号する問題であり、もしLPN問題が簡単に解けるならば、符号理論において画期的で重大な発見になる。あり、そこでは1ビットの「暗号化」について書かれています。一方でこの記事では1ビットの「鍵共有」について説明したあとに、複数ビットへの拡張について説明していきます。AliceとBobの2人が鍵共有をします。