juaninf - notas de psudoprogramador

Thursday, July 18, 2013

Compuscientia 2013

CompuScientia es una revista que busca difundir los diferentes caminos que ofrece el inmenso mundo de la Computación: aplicaciones tecnológicas, áreas de investigación, recomendaciones legales, fuentes de financiamiento de proyectos, oportunidades laborales, entre otros. Siendo así, la revista está dirigida a jóvenes estudiantes de pre y posgrado, profesionales y entusiastas de diferentes carreras de Computación y afines.
La Computación y la Tecnología van de la mano, y hoy son dos de los pilares del desarrollo mundial. En consecuencia, CompuScientia tiene el objetivo de presentarlos como agentes importantes para el desarrollo sostenido del país.
CompuScientia es una revista para todos los interesados en conocer más acerca del mundo de la Computación y Tecnología. En CompuScientia les hacemos partícipes de las diversas oportunidades académicas, profesionales y laborales que les pueden interesar.

Para mas información ingresar a la web aquí


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
Related Posts Plugin for WordPress, Blogger...