Distinguir entre dos monedas.

13

Es bien sabido que la complejidad de distinguir un moneda sesgada de una feria es θ ( ε - 2 ) . ¿Hay resultados para distinguir una moneda p de una moneda p + ϵ ? Puedo ver que para el caso especial de p = 0 , la complejidad será ϵ - 1 . Tengo el presentimiento de que la complejidad dependerá de si p es del orden de ϵ , pero no puede probarse tan rigurosamente. ¿Alguna pista / referencia?ϵθ(ϵ2)pagp+ϵp=0 0ϵ-1pagϵ

elexhobby
fuente

Respuestas:

15

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 0n1/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+ϵ+(1p)log1p1pϵ,

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(1p))pϵnp(1p)/ϵ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ϵ)ϵn1/ϵ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.p5/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,σ02)N(μ1,σ12)μ0=pnμ1=p+ϵ)nσ02=p(1p)n . Encontrará que la probabilidad de error en el distintivo óptimo es erfc ( z ) donde z = ( μ 1 - μ 0 ) / ( σ 0 + σ 1 ) ϵ σ12=(p+ϵ)(1pϵ)nerfc(z) . Por lo tanto, necesitamosz1para distinguir con probabilidad de éxito constante. Esto equivale a la condición de quen2p(1-p)/ϵ2(hasta un factor constante) ... cuandopϵ.z=(μ1μ0)/(σ0+σ1)ϵn/2p(1p)z1n2p(1p)/ϵ2pϵ

Para el caso general ... ver el documento.

DW
fuente