Le sugiero que use el marco que se encuentra en el siguiente documento:
¿Hasta dónde podemos ir más allá del criptoanálisis lineal? , Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.
El resultado crucial dice que necesita , donde D ( D 0n∼1/D(D0||D1) es la distancia Kullback-Leibler entre las dos distribuciones D 0 y D 1 . Ampliando la definición de la distancia KL, vemos que en su casoD(D0||D1)D0D1
D(D0||D1)=plogpp+ϵ+(1−p)log1−p1−p−ϵ,
con la convención de que .0log0p=0
Cuando , encontramos D ( D 0p≫ϵ . Por lo tanto, cuando p ≫ ϵ , encontramos que necesita n ∼ p ( 1 - p ) / ϵ 2 lanzamientos de monedas. Cuando p = 0 , encontramos D ( D 0D(D0||D1)≈ϵ2/(p(1−p))p≫ϵn∼p(1−p)/ϵ2p=0 , por lo que necesita n ∼ 1 / ϵ lanzamientos de monedas. Por lo tanto, esta fórmula es consistente con los casos especiales que ya conoce ... pero se generaliza a todos n , ϵ .D(D0||D1)=−log(1−ϵ)≈ϵn∼1/ϵn,ϵ
Para justificación, vea el documento.
Cuando , la justificación es fácil de resolver a mano. Con n observaciones, el número de cabezas es Binomial ( n , p ) o Binomial ( n , p + ϵ ) , por lo que desea encontrar el n más pequeño de manera que se puedan distinguir estas dos distribuciones.p≫ϵnBinomial(n,p)Binomial(n,p+ϵ)n
Puede aproximar ambos con un gaussiano con la media y la varianza correctas, y luego usar resultados estándar sobre la dificultad de distinguir dos gaussianos, y la respuesta debería fallar. La aproximación está bien si o menos.p≥5/n
En particular, esto se reduce a distinguir de N ( μ 1 , σ 2 1 ) donde μ 0 = p n , μ 1 = p + ϵ ) n , σ 2 0 = p ( 1 - p ) n , σ 2 1 = ( p + ϵ )N(μ0,σ20)N(μ1,σ21)μ0=pnμ1=p+ϵ)nσ20=p(1−p)n . Encontrará que la probabilidad de error en el distintivo óptimo es erfc ( z ) donde z = ( μ 1 - μ 0 ) / ( σ 0 + σ 1 ) ≈ ϵ √σ21=(p+ϵ)(1−p−ϵ)nerfc(z) . Por lo tanto, necesitamosz∼1para distinguir con probabilidad de éxito constante. Esto equivale a la condición de quen∼2p(1-p)/ϵ2(hasta un factor constante) ... cuandop≫ϵ.z=(μ1−μ0)/(σ0+σ1)≈ϵn/2p(1−p)−−−−−−−−−−√z∼1n∼2p(1−p)/ϵ2p≫ϵ
Para el caso general ... ver el documento.