ANDOS (criptografía)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de julio de 2019; las comprobaciones requieren 2 ediciones .

ANDOS ( All or Nothing Disclosure Of Secrets ) es un protocolo criptográfico para la "venta secreta de secretos" . Que el vendedor de S secrets tenga una lista de preguntas y ponga a la venta las respuestas a cualquiera de ellas. Supongamos que el comprador B quiere comprar un secreto, pero no quiere revelar cuál. El protocolo garantiza que B obtendrá el secreto que necesita y nada más, mientras que S no sabrá exactamente qué secreto obtuvo B.

Algoritmo

Veamos los secretos que posee S , cada uno de ellos contiene un pedacito. Para cada S publica una descripción del secreto. Suponga que los compradores B y C quieren comprar secretos y , respectivamente. La idea es que los compradores tengan funciones unidireccionales individuales y cada uno opere sobre los números recibidos por el otro. ${\ Displaystyle s_ {1},..., s_ {k}}$ $norte$ $s_{j}$ $s_{j}$ ${\ Displaystyle s_ {j'))$

Paso 1. S da a B y C funciones unidireccionales individuales f y g , pero mantiene sus inversas para sí mismo. Paso 2. B le dice a C (respectivamente C - B ) números de bits aleatorios (respectivamente ).

k

norte

{\ estilo de visualización x_{1},...,x_{k))

x_{1'},...,x_{k'}

Para , que asigna números de bits a números de bits y número de bits , digamos que el índice es el índice de bits fijos (FBI) correspondiente al par si el bit -ésimo es igual al bit -ésimo en . Está claro que hay un IFB correspondiente al par si es un IFB correspondiente al par . Si se comporta bastante aleatoriamente cuando cambia bits (como buenas funciones criptográficas), entonces, para random , uno puede estimar aproximadamente que aproximadamente los índices son IFB correspondientes a $F$ $norte$ $norte$ $norte$ $X$ $i,1\leqslant i\leqslant n$ ${\ estilo de visualización (x, f)}$ $i$ $X$ $i$ $f(x)$ $i$ ${\ estilo de visualización (x, f)}$ ${\ estilo de visualización (f (x), f ^ {-1})}$ $F$ $X$ $X$ ${\frac{n}{2))$ ${\ estilo de visualización (x, f).}$

Paso 3. B le dice a C (respectivamente C - B ) el conjunto de índices IFB correspondientes respectivamente al conjunto de índices IFB correspondientes a

{\ estilo de visualización _ {B}}

{\ estilo de visualización (x'_ {j}, f) (}

{\ estilo de visualización _ {C}}

{\ estilo de visualización (x_ {j'}, g)).}

Paso 4. B (respectivamente C ) le dice a S números (respectivamente , donde es el resultado obtenido al reemplazar cada bit en , cuyo índice no es IFB , con su opuesto (respectivamente obtenido de de manera similar).

{\displaystyle y_{1},...,y_{k))

y_{k'},...,y_{k'}

y_{yo}

x_{yo}

{\ estilo de visualización _ {C}}

{\ Displaystyle y'_ {yo}}

x'_{i}

Paso 5. S le dice a B (respectivamente C ) números

s_{i}\oplus f^{-1}(y'_{i})(

respectivamente , .

s_{i}\oplus g^{-1}(y_{i}))

{\ estilo de visualización i = 1,..., k}

Paso 6. B (respectivamente C ) puede calcular (respectivamente ) ya que se conocen respectivamente

s_{j}

{\ Displaystyle s'_ {j}}

x'_{j}=f^{-1}(y'_{j})(

x_{j'}=g^{-1}(y_{j'})).

B y C aprendieron los secretos que necesitaban. S no aprendió nada sobre su elección. Además, ni B ni C aprendieron más que uno de los secretos o elecciones del otro. Una colusión entre B y C da como resultado que puedan aprender todos los secretos. La colusión entre S y uno de los compradores puede revelar qué secreto quiere el otro comprador.

Así que el principal problema es la colusión. Sin embargo, si hay al menos tres compradores, entonces un comprador honesto es suficiente para que sea imposible engañar al resto, gracias al uso de funciones criptográficas, ya que cada bit de la secuencia enviada a los compradores desde S depende en gran medida de los bits proporcionada por el comprador honesto.

En el caso de que haya varios compradores , el protocolo funciona exactamente de la misma manera, pero cada comprador recibe una función del vendedor junto con conjuntos de números de otros compradores. $t\geqslant 3$ $t-1$

Ejemplos

Tomemos RSA como la base de las funciones unidireccionales . $F$ $gramo$

Elijamos _ Considere que S tiene los siguientes 8 secretos de 12 bits para vender:

{\ estilo de visualización k = 8, n = 12}

{\ estilo de visualización s_ {1} = 1990,}

{\ estilo de visualización s_ {2} = 471,}

{\ estilo de visualización s_ {3} = 3860,}

{\ estilo de visualización s_ {4} = 1487,}

{\ estilo de visualización s_ {5} = 2235,}

{\ estilo de visualización s_ {6} = 3751,}

{\ estilo de visualización s_ {7} = 2546,}

{\ estilo de visualización s_ {8} = 4043.}

Paso 1. S le da a B y C funciones unidireccionales individuales f y g basadas en números primos (respectivamente ), módulo (respectivamente ). Los exponentes abierto y cerrado son iguales (respectivamente ).

p_{1}=83,q_{1}=89

p_{2}=67,q_{2}=41

{\ estilo de visualización n_ {1} = 7387}

{\ estilo de visualización n_ {2} = 2747}

{\ estilo de visualización e_ {1} = 5145, d_ {1} = 777}

{\ estilo de visualización e_ {2} = 1421, d_ {2} = 2261}

Paso 2 B le dice a C ocho números de 12 bits :

x_{i},1\leqslant i\leqslant 8

{\ estilo de visualización x_ {1} = 743,}

{\ estilo de visualización x_ {2} = 1988,}

{\ estilo de visualización x_ {3} = 4001,}

{\ estilo de visualización x_ {4} = 2942,}

{\ estilo de visualización x_ {5} = 3421,}

{\ estilo de visualización x_ {6} = 2210,}

{\ estilo de visualización x_ {7} = 2306,}

{\ estilo de visualización x_ {8} = 912.}

C le dice a B ocho números de 12 bits :

x'_{i},1\leqslant i\leqslant 8

{\ estilo de visualización x'_ {1} = 1708,}

{\ estilo de visualización x'_ {2} = 711,}

x'_{3}=1969,

{\ estilo de visualización x'_ {4} = 3112,}

{\ estilo de visualización x'_ {5} = 4014,}

{\ estilo de visualización x'_ {6} = 2308,}

{\ estilo de visualización x'_ {7} = 2212,}

{\ estilo de visualización x'_ {8} = 222.}

Paso 3 Que B quiera comprar el secreto . el calcula

{\ estilo de visualización s_ {7))

f(x'_{7})=(x'_{7})^{e_{1}}{\pmod {n_{1}}}=2212^{5145}{\pmod {7387} }=5928.

Comparando la representación binaria y

{\ Displaystyle x'_ {7}}

f(x'_{7}),

{\ estilo de visualización 2212 = 0100010100100}

{\ estilo de visualización 5928 = 1011100101000}

B le dice a C un conjunto de IFB de la correspondiente

{\ estilo de visualización _ {B} = \ {0,1,4,5,6\}}

{\ estilo de visualización (x'_ {7}, f).}

Que C quiera comprar un secreto . Después de los cálculos, C le dice a B un conjunto de IFB de la correspondiente

s_{2}

{\ estilo de visualización _ {C} = \ {0,1,2,6,9,10\))

{\ estilo de visualización (x_{2}, g).}

Paso 4 B le dice a S el número , donde es el resultado que se obtiene al reemplazar cada bit en , cuyo índice no pertenece a , con el contrario, por ejemplo:

y_{i},1\leqslant i\leqslant 8

y_{yo}

x_{yo}

{\ estilo de visualización \ {0,1,2,6,9,10\))

y_{2}=0110011111100=1660.

C le dice a S los números , donde es el resultado obtenido al reemplazar cada bit en , cuyo índice no pertenece a , con el contrario, por ejemplo:

y'_{i},1\leqslant i\leqslant 8

{\ Displaystyle y'_ {yo}}

x'_{i}

{\ estilo de visualización \ {0,1,4,5,6\))

y'_{7}=1011100101000=5928.

Paso 5 S le dice a B números la función inversa , por ejemplo:

s_{i}\oplus f^{-1}(y'_{i}),1\leqslant i\leqslant 8(

f^{-1}(y')=y'^{d_{1}}{\pmod {n_{1}}}=y'^{777}{\pmod {7387}})

s_{7}=2546=0100111110010

f^{-1}(y'_{7})=2212=0100010100100

s_{7}\oplus f^{-1}(y'_{7})=0000101010110={\boldsymbol {342))

S le dice a C números una función inversa , por ejemplo.

s_{i}\oplus g^{-1}(y_{i}),1\leqslant i\leqslant 8(

g^{-1}(y)=y^{d_{2}}{\pmod {n_{2}}}=y^{2261}{\pmod {2747}})

{\ estilo de visualización s_ {2} = 471 = 000111010111}

g^{-1}(y_{2})=1988=011111000100

s_{2}\oplus g^{-1}(y_{2})=011000010011={\boldsymbol {1555))

Paso 6 B aprende la suma bit a bit secreta del séptimo número recibido de S , a saber:

{\ estilo de visualización s_ {7))

{\ Displaystyle x'_ {7}}

{\ estilo de visualización x'_ {7} = 2212 = 100010100100}

{\ estilo de visualización 342 = 000101010110}

x'_{7}\oplus 342)=100111110010={\boldsymbol {2546))

Si C quiere comprar el secreto , calcula la suma bit a bit del segundo número recibido de S , a saber:

s_{2}

x_{2}

x_{2}=1988=11111000100

{\ estilo de visualización 1555 = 11000010011}

x_{2}\oplus 1555)=00111010111={\boldsymbol {471))

Literatura

G. Brassard, C. Crepeau y J.-M. Roberto. Revelación de secretos de todo o nada // Springer Lecture Notes in Computer Science 263 (1987). Archivado desde el original el 4 de marzo de 2016.
A. Salomaa y L. Santean. Venta secreta de secretos con muchos compradores // EATCS Bulletin 42(1990)) . Archivado desde el original el 4 de marzo de 2016.