Различение между двумя монетами

13

Хорошо известно, что сложность отличия монеты, смещенной на от монеты-монеты - это . Есть ли результаты для отличия монеты от монеты ? Я вижу, что для частного случая сложность будет . У меня есть догадка, что сложность будет зависеть от того, имеет ли порядок , но не может доказать это строго. Любые намеки / ссылки?θ ( ϵ - 2 ) p p + ϵ p = 0 ϵ - 1 p ϵϵθ(ϵ2)pp+ϵp=0ϵ1pϵ

elexhobby
источник

Ответы:

15

Я предлагаю вам использовать рамки, найденные в следующей статье:

Как далеко мы можем выйти за пределы линейного криптоанализа? , Томас Беньер, Паскаль Юно, Серж Водене, ASIACRYPT 2004.

Критический результат говорит о том, что вам нужно n1/D(D0||D1) , где - расстояние Кульбака-Лейблера между двумя распределениями D 0 и D 1 . Расширяя определение расстояния KL, мы видим, что в вашем случаеD(D0||D1)D0D1

D(D0||D1)=plogpp+ϵ+(1p)log1p1pϵ,

с условием, что .0log0p=0

Когда , мы находим D ( D 0pϵ . Таким образом, когда p ϵ , мы находим, что вам нужно n p ( 1 - p ) / ϵ 2 подбрасывания монет. Когда p = 0 , находим D ( D 0D(D0||D1)ϵ2/(p(1p))pϵnp(1p)/ϵ2p=0 , поэтому вам нужно n 1 / ϵ подбрасывание монет. Таким образом, эта формула согласуется с частными случаями, о которых вы уже знаете ... но она обобщает на все n , ϵ .D(D0||D1)=log(1ϵ)ϵn1/ϵn,ϵ

Обоснование см. В статье.


Когда , обоснование легко прорабатывается вручную. При n наблюдениях количество головок является либо биномиальным ( n , p ), либо биномиальным ( n , p + ϵ ) , поэтому вы хотите найти наименьшее n, такое, чтобы эти два распределения можно было различить.pϵnBinomial(n,p)Binomial(n,p+ϵ)n

Вы можете аппроксимировать оба из них гауссианом с правильным средним и дисперсией, а затем использовать стандартные результаты по сложности различения двух гауссиан, и ответ должен выпасть. Аппроксимация хороша, если или около того.p5/n

N(μ0,σ02)N(μ1,σ12)μ0=pnμ1=p+ϵ)nσ02=p(1p)nσ12=(p+ϵ)(1pϵ)nerfc(z)z=(μ1μ0)/(σ0+σ1)ϵn/2p(1p)z1n2p(1p)/ϵ2pϵ

Для общего случая ... см. Статью.

DW
источник