LWE problemの定義は以下の通りです https://www.latticechallenge.org/lwe_challenge/challenge.php [latticechallenge.org] > The LWE problem is to recover s, given an instance (A, b), where A is an m×n matrix over ℤq and b = As + e is a vector of length m over ℤq. Both the matrix A and the target vector s are sampled uniformly random, while the error vector e is sampled from the Gaussian distribution with parameter σ.
x=0, e=b ではダメなの？ (スコア:0)
タレコミの説明だけだと、
x=0, e=b っていう解でも条件満たしてしまう。
e についての追加の制約がいろいろあるんでしょうね。
eの分散を最小にするのなら、最小二乗法と一緒で、線形時間で解けるし、なんかもっと複雑なんだろうね。
Re:x=0, e=b ではダメなの？ (スコア:2)
いえいえ、暗号ですから、bが暗文、xが平文、eが鍵です。
逆に言うと絶対に0を暗号化できない(してはいけない)？
なんか、結構弱鍵とか出てきそうで怖い。
Re:x=0, e=b ではダメなの？ (スコア:2, 参考になる)
> いえいえ、暗号ですから、bが暗文、xが平文、eが鍵です。
全然違います
https://en.wikipedia.org/wiki/Learning_with_errors [wikipedia.org]
https://en.wikipedia.org/wiki/Ring_learning_with_errors_key_exchange [wikipedia.org]
LWE problemの定義は以下の通りです
https://www.latticechallenge.org/lwe_challenge/challenge.php [latticechallenge.org]
> The LWE problem is to recover s, given an instance (A, b), where A is an m×n matrix over ℤq and b = As + e is a vector of length m over ℤq. Both the matrix A and the target vector s are sampled uniformly random, while the error vector e is sampled from the Gaussian distribution with parameter σ.
Re: (スコア:0)
自己訂正
線形時間で解けるは、嘘だ。
多項式時間で解ける、、だね。
Re: (スコア:0)
たとえば、大きな数Xを素因数a、bに分解する(X=ab)のに時間がかかるから安全な暗号だ、というときに、
「両辺に0をかければ0=0でもう計算する必要なくね?」
って言い出すくらい的外れ。