Diferencias

Muestra las diferencias entre dos versiones de la página.

--- pan:ataques_recontruccion_v2 [2026/01/04 14:54] – thejuanvisu
+++ pan:ataques_recontruccion_v2 [2026/01/04 15:56] (actual) – thejuanvisu
@@ Línea 19: / Línea 19: @@
 ===== Ataque de reconstrucción lineal =====
+**__Teorema:__** Si el analista puede realizar $2^n$ peticiones y el curador añade ruido $E$, entonces el adversario puede reconstruir la base de datos entera salvo por $4E$ posiciones.
+==== Fase 1 ====
+  * El analista envía todas las peticiones posibles a la base de datos y almacena las respuestas.
+{{drawio>pan:lienaletapa1.png}}
+<code>
+for i = 1:2^n
+    Analista envía s(i)
+    Curador responde con r(s(i)) ) s(i)^T * d + e(i)
+</code>
+==== Fase 2 ====
+  * El analista busca candidatos válidos
+<WRAP column 100%>
+<WRAP column half>
+{{drawio>pan:lienaletapa2.png}}
+</WRAP>
+<WRAP column half>
+<code>
+for k = 1:2^n
+  candidate = 'valid'
+  for i = 1:2^n
+    if |r(s(i)) - (s(i))^T * c(k)| > E:
+      canditate = 'not valid'
+      break
+  if candidate = 'valid' : store c(k) in lista de candidatos válidos
+</code>
+</WRAP>
+</WRAP>
+==== Resumen de ataque de reconstrucción lineal ====
+A menos que haya un límite de peticiones a la base de datos, es posible crear una reconstrucción casi perfecta de 4E entradas de la base de datos. Por ejemplo, si E = n/401, la base de datos puede ser reconstruida para al menos el 99% de las entradas (E es el error máximo que se introduce en las respuestas, por lo que no debe ser demasiado grande.). Sacrificando algo de la precisión, es posible reconsutrir estadísticamente el vector secreto con muchas menos peticiones.
+==== Ataque de Reconstrucción Lineal Probabilístico ====
+Dinur y Nissim propuisieron un ataque que funciona en $O(n)$ peticiones cuando el curador añade un ruido de $E=O(∝√n)$, permitiendo reconstruir toda la base salvo $O(∝^2)$ posiciones usando programación lineal. Para evaluar la magnitud del sonido, se toma una muestra de una poblaciñin que satisfaga una propiedad con probabilidad p y tome n muestras, la media es $np$ y la desviación típìca es $\sqrt{p(1-p)} \sqrt{n}$, por lo que R es requerido para evitar que este tipo de ataque sea mayor que el error de las muestras.
+===== Desafío Aircloack's Diffix =====
+La compañía Aircloack, que vendía el producto Diffix, prometía privacidad en base a curar las respuestas de las bases de datos. Esta compañía lanzó un concurso con un premio de 5000$ para ver si su producto respondía a los ataques de reconstrucción como se esperaba. La cantidad de ruido que se añadía en cada respuesta era la raiz cuadrada del número de condiciones. Estaban prohibidas las operaciones de tipo OR en la base de datos y, en caso de que la salida tuviera pocas entradas, la base de datos no respondería. Se planteó una forma de interrogar la base de datos de forma que las peticiones cubrieran muchos elementos de la base de datos de una forma más o menos aleatoria y que tuvieran un número de condiciones muy pequeño. Como resultado se obtuvo la siguiente consulta SQL:
+<code sql>
+SELECT COUNT(clientId)
+FROM loans
+WHERE FLOOR(100*((clientId*2)^0,7)+0.5) = FLOOR(100*(clientId*2)^0.7)
+AND clientID BETWEEN 2000 AND 3000
+AND loanStatus = 'C'
+</code>
+Con esta consulta se pudo reconstruir la abse de datos a pesar de las medidas tomadas.

Knoppia

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página