最近、lattice based cryptographyなるものをpythonで実装した。ある程度の確率で適切にデータが復号できないが、量子コンピュータに対する耐性がある、みたいなやつだった。（多分）自分の実装ではなんとエラー確率が体感で40%くらいあった。つまり、40%の確率で本人でない人の接続を許してしまったり、あるいは本人が接続しようとしているのに弾かれてしまったりするという事だ。もちろん認証回数を増やせば指数関数的に(？)エラー確率が減少するはずだ。そこで考えてみる。
「1」が出てくるのが正常な動作だとして、0.6の確率で1、0.4の確率で0が出てくる試行を(2n+1)回やる。
このときに0が多数になる確率は、0がn+1, n+2, n+3, …, 2n+1回出てくる確率の総和だから、
"sigma from k = 1 to k = n+1, ((2n+1) choose (n+k))*((4/10)^(n+k))*((6/10)^(2n+1-(n+k)))" = "2^(1 + n) 3^n 5^(-1 - 2 n) binomial(1 + 2 n, 1 + n) 2F1(1, -n, 2 + n, -2/3)" by Wolfram Alpha 大先生
つまり、エラー確率(間違った答えを出す、ここでは1と出力するのが正しいのに0を出力してしまう確率)が2の256乗分の1以下になるのは、以下の条件による。
"2^(1 + n) 3^n 5^(-1 - 2 n) binomial(1 + 2 n, 1 + n) 2F1(1, -n, 2 + n, -2/3)" < (1/2)^256
pythonのmpmathライブラリでこれを計算すると、
from mpmath import *
mp.dps = 100; mp.pretty = True
f = lambda n: (mpf(2) ** (1 + n)) * (mpf(3) ** n) * (5 ** (-1 - 2 * n)) * binomial(1 + 2 * n, 1 + n) * hyp2f1(1, -n, 2 + n, -2/3)
i = 0
while True:
if f(i) < mpf(1/2)**256:
print(i)
break
i += 1
# => 231
つまり、成功確率60%の認証は231 * 2 + 1 = 463回やると、2の256乗分の1くらいのエラー確率になるぞ！大変だ…