juaninf - notas de psudoprogramador

Friday, March 07, 2014

Problema em Teoria dos Códigos

Neste post vou analisar o Problema MINIMUM DISTANCE (MD) (conjeturado NP-Completo em [1] e demostrado NP-Completo em [2])  para poder entender porque o problema computacional associado a este problema é NP-Hard

Problema de Decisão MINIMUM DISTANCE (MD)
Instancia : Uma matriz binária $H^{m\times n}$ e um $w > 0$.
Pregunta: Existe algum vector $x\in \mathbb{F}_2^n$ com peso de Hamming $\leq w$ tal que $Hx=0$?

Problema de Computación COMPUTATIONAL MINIMUM DISTANCE (MD)
Instancia : Uma matriz binária $H^{m\times n}$ e um $w>0$.
Pregunta: Computar o vector $x\in \mathbb{F}_2^n$, com peso minimo, do código $C$ associado a $H$.

Veja que este é um problema de decisão porque as resposta possíveis são SIM ou NÃO. Que é NP-Completo esta demostrado em [2]. Que MD seja NP-Completo implica em que COMPUTING MINIMUM DISTANCE (CMD) é NP-Hard. Para demonstrar isto vamos a usar a definição informal que nos da o wikipedia.
Um problema $H$ é NP-difícil se e somente se (sse) existe um problema NP-completo L que é Turing-redutível em tempo polinomial para $H$. Em outras palavras, $L pode ser resolvido em tempo polinomial por umaMáquina de Turing Não Determinística com um oráculo para H. Informalmente, podemos pensar em um algoritmo que pode chamar tal Máquina de Turing Não-Determinística como uma sub-rotina para resolver H, e resolver L em tempo polinomial, se a chamada da sub-rotina leva apenas um passo para computar.
Então podemos usar como oraculo um algoritmo que resolve CMD para resolver em tempo polinomial, numa máquina de Turing Não Determinista, o problema MD. Para isto basta só comparar se o $w$ do problema MD é maior ou menor que o resultado retornado pelo oráculo. Se o $w$ fosse maior que o valor retornado pelo oraculo então a resposta do problema MD é SIM. Isto porque se fosse possível calcular a distancia minima do código, digamos $d$, então para qualquer $w\leq d$ a resposta é SIM. Se o $w$ fosse menor que o valor retornado pelo oraculo então a resposta do problema MD é NÃO dado que não pode existir $x$ com peso menor que $d$.

Referências
[1] Berlekamp, Elwyn R. and McEliece, Robert J. and van Tilborg, Henk C. A. (1978) On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24 (3). pp. 384-386. ISSN 0018-9448.
[2] The intractability of computing the minimum distance of a code - Vardy - 1997


Tuesday, February 04, 2014

Transformação Afim na Criptografia

Uma transformação afim é uma transformação entre dois espaços afins $A$ e $B$. Essa transformação, ou mapeamento, consiste numa transformação lineal em $A$ somado de um vetor $b \in B$. Ou seja: $$S(x)=Tx + b.$$ No campo da criptografia post-quântica as transformações afins são usadas para ocultar a chave pública dos sistemas de cifração baseados em multivariados.

Para os envolvidos na área é de importância saber lidar com as diferentes representações de uma transformação afim. Neste post apresentarei essas representações e mostrarei como converter uma para a outra. Seja $\mathbb{F}$ um corpo finito com $q$ elementos e $\mathbb{E}$ uma extensão de grau $n$ do corpo $\mathbb{F}$. Seja $S:\mathbb{F}^n\rightarrow \mathbb{F}^n$ uma transformação afim.

Definição 1: Seja $0\leq i < n$ e $A,B_i \in \mathbb{E}$. Então nós chamamos o polinômio $S(X)=\sum_{i=0}^{n-1}B_i X^{{q}^i}+A$ a representação de uma só variável da transformação afim $S$.

Definição 2: Seja $M_S \in \mathbb{F}^{n\times n}$ uma matriz e $v_s \in \mathbb{F}^n$ um vetor. Então nos chamamos $S(x):=M_Sx+v_s$, a representação matricial da transformação afim $S$ .

Definição 3: Seja o espaço vetorial $\mathbb{F}^n$. Então nós chamamos $\phi:\mathbb{E}\rightarrow \mathbb{F}^n$ com $\phi(a):=b$ e $b_i=a_{i-1}$ de bijeção canônica.

Teorema: Uma transformação afim, com $v=0$ na representação de uma só variável pode ser transformada eficientemente na sua representação matricial.

Prova: Definamos $e_i \in \mathbb{F}^n$ com $1\leq i \leq n$, com um $1$ no seu i-th coeficiente e zero no restante. Vamos a mostrar que a coluna $k$ dessa matriz é dada pela seguinte fórmula: $M_k=\phi(S(\phi^{-1}(e_k))).$ Vamos a definir $P(X):=\sum_{i=0}^{n-1}B_i X^{{q}^i}$. Da álgebra conhecemos que o corpo $\mathbb{F}^n$ é também um espaço vetorial sobre o corpo $\mathbb{F}$. Esse espaço vetorial tem a base $V=\{t^0, t^1, t^2,\ldots,t^{{n-1}}\}.$ Vamos a representar os coeficiente de $P(X)$ como  $B_i =\sum_{j=0}^{n-1}b_{ij} t^j$ e a variável $X=\sum_{k=0}^{n-1}X_{k}t^k$. Substituindo esses valores em $P(X)$ temos $$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} t^j(\sum_{k=0}^{n-1}X_{k}t^k)^{{q}^i},$$
Usando o teorema binomial e reduzindo temos
$$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}t^{j+k{{q}^i}},$$

Escrevendo $t^{j+k{{q}^i}}$ usando a base $V$ temos $t^{j+k{{q}^i}} = \sum_{m=0}^{n-1}c_{ijkm}t^m$. Por tanto:

$$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k} \sum_{m=0}^{n-1}c_{ijkm}t^m$$
$$P(X) =  \sum_{m=0}^{n-1}\underline{\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}c_{ijkm}}_{E}t^m$$
Por outro lado, escrevendo  $\phi(S(\phi^{-1}(e_k)))$ usando a base $V$ temos que esta é igual a: $\phi(S(\phi^{-1}(e_k)))=(\sum_{i,j}^{n-1}b_{i,j}c_{ijk0}, \cdots, \sum_{i,j}^{n-1}b_{i,j}c_{ijk(n-1)})$. Por fim, veja que $E_m = (\phi(S(\phi^{-1}(e_1)))[m],\cdots,\phi(S(\phi^{-1}(e_{n-1})))[m])^{T}*(X_1,\cdots, X_{n-1}).$

No caso de transformação afim com $v \neq 0$ então se tem que v:=$M_k=\phi(S(\phi^{-1}(0)))$ e as colunas de $M$ são $M_k=\phi(S(\phi^{-1}(e_k)))-v.$

Tuesday, December 17, 2013

Friday, December 06, 2013

El Faq de las Máquinas de Turing

Este post es sólo un oráculo de algunas preguntas frecuentes para quién ya estudió teoria de la computación y con el tiempo ha ido olvidando algunos conceptos.

Que es una máquina de Turing?
Un Dispositivo
Que es un problema?
Un conjunto de frases de longitud finita que esta asociada a un conjuto de frases también de longitud finita.
Que es un problema decidible?
Un problema que su conjunto asociado solo tiene las frases si y no, es decir existe un método que ya consigue definir esos: si y no. Los problemas decidibles tienen un método definido que consigue decir si el problema(la sentencia) es cierto o falso.
Que es un algoritmo?
No existe un consenso, pero se puede decir que es una máquina de Turing.
Todo método que resuelve un problema decidible puede ser implementado en una máquina de Turing?
no sé. Creo que si.
Que es un problema indecidible?
Un problema para el cual no existe un método tal que sea capaz de resolverlo con una respuesta si o no.
Cuantas programas puedo escribir en una máquina de Turing?
Si es universal muchos, recuerde que una máquina de Turing Universal permite simular cualquier máquina de Turing para cualquier entrada.
Que es PP?
Es la clase de problemas de decisión para los cuáles existe un algoritmo de Montecarlo bilateral que responde si cuando la respuesta correcta es si con probabilidad > 1/2 (idem para no) y el tiempo de ese algoritmo es es un polinómio en el tamaño de la entrada. Otra definición equivalente, es la clase de problemas resolubles por una MT probabilística en tiempo polinomial con probabilidad > 1/2 para todas sus instancias.
NP \in PP?
Si. El problema de la factoración esta en NP, por tanto en PP, entonces existe un algoritmo de montecarlo que consigue factorar como descrito en la pregunta anterior, sólo que máquinas de Turing probabilisticas no existen (en general las no deterministas no existen) y las que se simulan estas no son eficientes, es decir no consiguen factorar en tiempo polinomico.

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

Friday, April 19, 2013

Ejemplo Criptosistema McEliece en SAGE

En el 1978 McEliece presentó un nuevo criptosistema de clave pública, basado en la Teoría de los Códigos. Dado que esta teoría es muy compleja, los expertos recomiendan una familiarización matemática preliminar con la Teoría de la Codificación, los Códigos de Goppa, y los Cuerpos de Galois.
 En el sistema de McEliece, cada usuario ha de elegir un polinomio irreducible de grado $delta$, y construir una matriz generadora del correspondiente código de Goppa, matriz G, de orden k x n. También ha de calcular la llave pública, que es una matriz generadora del código Goppa. Este código debe ser  tal que no exista un algoritmo computable que corrija los errores con éste código en un tiempo pequeño. La llave pública es obtenida a partir de la multiplicación de una matriz aleatoria no singular de orden 2^m-k*m, y una matriz de permutaciones de orden 2^m. Todos los usuarios del sistema mantienen sus respectivas llaves públicas, mientras que las matrices S,G e P serán secretas.
A continuación presentamos el algoritmo para generación de las llaves, cifrado de un texto plano y descifrado de un texto cifrado, según wikipedia, y su respectiva implementación mediante un ejemplo en SAGE. Es necesario "correr" primero la última de las celdas de este post, la cual contiene los algoritmos auxiliares como por ejemplo el algoritmo de Patterson.

Generación de Llaves
  1. Alicia selecciona un código de Goppa binario Gamma com parâmetros (n,k) y capacidad de correción de delta errores; 
  2. Alicia gera a matriz geradora $G$, de dimensiones n-m*k x n, del código \Gamma; Selecciona una matriz binaria no singular S, de dimensiones;n-m*k x n-m*k; 
  3.  Selecciona una matriz de permutación P, de dimensión n; 
  4.  Computa a matriz $G' = SGP; 
  5.  La llave pública de Alicia é (G',delta) y su llave privada es (S,G,P).
Related Posts Plugin for WordPress, Blogger...