Knoppia

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Cifrado Homomorfico ======
Cuando un tercero tiene que operar con nuestros datos y no queremos que los vea, se aplica cifrado homomorfico, que permite realizar operaciones sobre datos cifrados.

A la hora de operar con cifrado homomorfico se usan los siguientes componentes:
  * **n** -> Tamaño de los vectores
  * **q** -> Valor del módulo (módulo q)
    * Trabajamos con módulos en potencias de 2 ($2^x$)
  * **e** -> Error
    * Dsitribución normal N(0,γ*q) -> r = γ*q
      * Media 0
      * Valor relacionado con q
      * El valor debe estar redondeado
      * Valor entre 0 y q
  * **a** -> Vector de soporte
    * Vector de tamaño n con valores entre 0 y q-1
  * **S** -> Secreto o clave privada
    * Solo la conoce el dueño de los datos a operar
    * Valores aleatorios del conjunto {-1,0,1}

Sabiendo esto, sabemos que la clave pública (a,b) del cifrado homomorfico es: 
<WRAP box>
$(a,b = S^T*a+e $ $MOD q) ∈ Z^n_q * Z_q$ 
</WRAP>
Esta fórmula es solo la clave pública, si queremos proceder a realizar el cifrado utilizando esta, debemos introducir otros 2 elementos:
  * **m** -> Mensaje a Cifrar
  * **Δ** -> Constante (Normalmente su valor es una potencia de 2)

El cifrado homomórfico se vería de la siguiente forma:
<WRAP box>
$(a,b = S^T*a+e+Δ*m $ $MOD q)$ 
</WRAP>
  * Clave pública -> $S^T*a+e$
  * Texto Cifrado -> $b = S^T*a+e+Δ*m $ $MOD q$ 
  * **OJO**: a y b son necesarios para poder descrifrar el mensaje

Cuando se mandan datos a un tercero para operar con ellos, se madan a y b

<WRAP box>
$Δ*m+e = b+S^T*a$
</WRAP>
  * $m' = Δ*m+e$ -> Mensaje aproximado con error

<WRAP box>
$m+e = (b+S^T*a)/Δ$ $MOD q$
</WRAP>
  * $m' = m+e$

<WRAP box>
$m = ||(b+S^T*a)/Δ - e$ $MOD q||$
</WRAP>
  * Redondeamos el resultado para el descifrado
  * Si todo va bien, al realizar el redondeo desaparece el error aplicado y el valor final obtenido es el mensaje inicial.

{{drawio>pan:chomoej1.png}}

===== Sumas sobre cifrado Homomórfico =====

{{drawio>pan:chsuma.png}}

===== Multiplicación de cifrado homomórfico contra una pequeña constante =====

{{drawio>pan:chmultcons.png}}

**NOTA**: Si el valor de C es muy grande puede descuadrarse todo al multiplicarse el error.

===== Descomposición gadget =====

La descomposición gadget consiste en tomar un número grande y descomponerlo en bloques. Esto se usa en las multiplicaciones con cifrado homomórfico para evitar que se descuadren los valores.
{{drawio>pan:descgadget1.png}}

La descomposición gadget permite calcular varios factores de la constante C. Se tienen en cuenta los siguientes datos:
  * C: Constante a descomponer
  * B: En cuantos trozos se va a descomponer, normalmente equivale al número de restos que obtenemos.
  * P: Valor de la potencia de 2 que se va a utilizar para realizar las divisiones.
{{drawio>pan:descgadget2.png}}

==== Descomposición Gadget en el Cifrado Homomórfico ====

Gracias a la descomposición gadget podemos descomponer una multiplicación homomórfica por una constante muy grande de la siguiente forma para $(a*c, b*c)$:
  * $(a*c_0, b*c_0)$
  * $(a*c_1, b*c_1)$
  * $(a*c_2, b*c_2)$
Lo que reduce el error de forma considerable
<WRAP box>
$C = C_2*2^{P*2} + C_1*2^{P*1} + C_0*2^{P*0}$
</WRAP>
Para ello, se crean varios mensajes cifrados:
{{drawio>pan:descgadget3.png}}

{{drawio>pan:descgadgetejemplo.png}}
Knoppia

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
