Я предлагаю вам использовать рамки, найденные в следующей статье:
Как далеко мы можем выйти за пределы линейного криптоанализа? , Томас Беньер, Паскаль Юно, Серж Водене, ASIACRYPT 2004.
Критический результат говорит о том, что вам нужно n∼1/D(D0||D1) , где - расстояние Кульбака-Лейблера между двумя распределениями D 0 и D 1 . Расширяя определение расстояния KL, мы видим, что в вашем случаеD(D0||D1)D0D1
D(D0||D1)=plogpp+ϵ+(1−p)log1−p1−p−ϵ,
с условием, что .0log0p=0
Когда , мы находим D ( D 0p≫ϵ . Таким образом, когда p ≫ ϵ , мы находим, что вам нужно n ∼ p ( 1 - p ) / ϵ 2 подбрасывания монет. Когда p = 0 , находим D ( D 0D(D0||D1)≈ϵ2/(p(1−p))p≫ϵn∼p(1−p)/ϵ2p=0 , поэтому вам нужно n ∼ 1 / ϵ подбрасывание монет. Таким образом, эта формула согласуется с частными случаями, о которых вы уже знаете ... но она обобщает на все n , ϵ .D(D0||D1)=−log(1−ϵ)≈ϵn∼1/ϵn,ϵ
Обоснование см. В статье.
Когда , обоснование легко прорабатывается вручную. При n наблюдениях количество головок является либо биномиальным ( n , p ), либо биномиальным ( n , p + ϵ ) , поэтому вы хотите найти наименьшее n, такое, чтобы эти два распределения можно было различить.p≫ϵnBinomial(n,p)Binomial(n,p+ϵ)n
Вы можете аппроксимировать оба из них гауссианом с правильным средним и дисперсией, а затем использовать стандартные результаты по сложности различения двух гауссиан, и ответ должен выпасть. Аппроксимация хороша, если или около того.p≥5/n
N(μ0,σ20)N(μ1,σ21)μ0=pnμ1=p+ϵ)nσ20=p(1−p)nσ21=(p+ϵ)(1−p−ϵ)nerfc(z)z=(μ1−μ0)/(σ0+σ1)≈ϵn/2p(1−p)−−−−−−−−−−√z∼1n∼2p(1−p)/ϵ2p≫ϵ
Для общего случая ... см. Статью.