juaninf - notas de psudoprogramador

Monday, July 01, 2013

Esquema de Firma Digital Pos Cuántico Lamport-Diffie

Este esquema de firma digital fue propuesto en el año de 1979. Es uno de los primeros en ser estudiados dentro de los esquemas de firma digital que se consideran resistentes ataques cuánticos dada su simplicidad para entender. A continuación describiré los algoritmos usados tanto para la generación de llaves como para el proceso de firma y verificación.

Generación de Llaves:
Escoger dos funciones
  1. Una función de Mano Única: $$f:\{0,1\}^n \rightarrow \{0,1\}^n$$
  2. Una función Hash $$g:\{0,1\}^{*}\rightarrow \{0,1\}^n$$
La llave  de firma, X, consiste de $2n$ cadenas de bits de tamaño $n$ elegidas de forma aleatoria uniformemente.
$$X=(x_{n-1}[0], x_{n-1}[1],\cdots,x_0[0],x_0[1])\in \{0,1\}^{n,2n}$$
La llave de verificación, Y, es:
$$Y=(y_{n-1}[0], y_{n-1}[1],\cdots,y_0[0],y_0[1])\in \{0,1\}^{n,2n},$$
donde $$y_i[j] = f(x_i[j]).$$

Firma:
Un documento $$M\in \{0,1\}^{*}$$ es firmado usando la llave X, usando $$d=g(M)=(d_{n-1},\cdots,d_0)$$ como $$\sigma = (x_{n-1}[d_{n-1}],\cdots,x_{0}[d_0])\in \{0,1\}^{n,n}$$
Verificación:
Para verificar $\sigma$ el verificador calcula g(M) y verifica si
$$(f(\sigma_{n-1}),\cdots,f(\sigma_0))=(y_{n-1}[d_{n-1}],\cdots,y_0[d_0]).$$

La seguridad de este esquema esta basada en dos nociones de seguridad: resistencia a pre-Imagen que presentan las funciones de mano única y la resistencia a colisiones que presenta una función hash criptográfica. Como ya vimos justamente el esquema Diffie-Lamport usa una función de mano única y una función hash. Funciones hash y funciones de mano única solo admiten ataques genéricos contra las dos nociones de seguridad mencionada. Para ataques contra la noción de resistencia a colisiones, usando un computador clásico, se usa Ataque de Cumpleaños el cual tiene complejidad O(2^{n/2}) de encontrar colisiones con probabilidad 1/2. Para ataques contra la noción de resistencia a pre-imagen, usando un computador clásico, se usa fuerza bruta, la cual en este caso, tiene complejidad de O(2^{n/2})  de encontrar pre-imagen con probabilidad 1/{2^{n/2}}. En el caso de uso de computadores cuánticos para crear ataques contra estas nociones de seguridad lo mejor que se pueda usar es el algoritmo de Groover. Este algoritmo, adaptado para estos ataques, tiene complejidad de O(2^{n/3}) con probabilidad 1/2 de encontrar colisiones y complejidad O(2^{n/3}) de encontrar pre-imágenes con probabilidad  1/{2^{n/3}}, [1,pag 90]. Es por eso que se dice que este esquema de firma digital, con sus limitaciones, es una alternativa para esquemas basados en problemas de la teoría de números como factorización de números grandes y el problema de logaritmo discreto.

[1] Johannes; Dahmen, Erik, eds. (2009). Post-quantum cryptographySpringer
Post a Comment
Related Posts Plugin for WordPress, Blogger...