概要
LWE問題をベースにした格子暗号を利用する時に、
現在知られているいろいろな攻撃アルゴリズムに対して、
設定したパラメータを使ったLWE問題がどのくらいのセキュリティビットを備えているのか
を試すことができるのがLWE Estimorです。
github はこちらです。
試してみよう
サクッと試したい時は、彼らが用意しているbinder
https://mybinder.org/
常に構築された Jupyternotebook に遷移することによってすぐに使用することができます。
上記環境に飛ぶためには、github レポジトリ上の
Try it in your browser のところのリンク
をクリックすることでJupyternotebook環境を使用することができます。
テスト用のプログラム
Jupyternotebook 上で例えば、
# import
from estimator import schemes
from estimator import LWE
from estimator import lwe_parameters
from estimator import nd
my_param = schemes.NTRUHPS2048677Enc
LWE.estimate.rough(my_param)
を実行します。
この例では、標準化のために使用されている
NTRUHPS2048677Enc
のパラメータを利用しています。
結果は数十秒くらいで返ってきます。
Algorithm functools.partial(<function dual_hybrid at 0x7f9d75143100>, red_cost_model=<estimator.reduction.ADPS16 object at 0x7f9d751066d0>, mitm_optimization=True) on LWEParameters(n=676, q=2048, Xs=D(σ=0.61), Xe=D(σ=0.82), m=676, tag='NTRUHPS2048677Enc') failed with β = 79 > d = 61
usvp :: rop: ≈2^150.7, red: ≈2^150.7, δ: 1.003328, β: 516, d: 1186, tag: usvp
hybrid :: rop: ≈2^222.3, red: ≈2^221.3, svp: ≈2^221.3, β: 515, η: 2, ζ: 234, |S|: ≈2^260.7, d: 1012, prob: ≈2^-68.8, ↻: ≈2^71.0, tag: hybrid
これで2^x となっているところが、xビットのセキュリティビットという意味です。
設定するパラメータの説明へのリンク
lwe_parameters.LWEParameters に渡す引数はこちらで確認できます。
最後に
今回は簡単ではありますが、
LWE Estimator の使い方を備忘録としてまとめました。
今回はこの辺で。