CODIGO Y SISTEMAS DE CODIFICACION

Autor: Fariña Martínez Antonio.
Año: 2004.
Universidad: A CORUÑA [www.udc.es].
Centro de lectura: Facultad de Informática.
Centro de realización: Facultad de Informática.

Resumen: Las bases de datos textuales están creciendo en los últimos años debido a la proliferación de las biliotecas digitales, bases de datos documentales, y sobre todo por el gran crecimiento continuado que la Web está manteniendo. La comresión surge como una solución ideal que permite reducir espacio de almacenamiento y las operaciones de E/S, con el consiguiente beneficio para la transmisión de información a través de una red. Si bien la compresión nace en la primera parte del siglo XX, en la pasada décda aparecen nuevas técnicas de compresión basadas en Huffman, que usan las palabrad con los símbolos a comprimir. Estas nuevas técnicas no sólo mejoran la capacidad de compresión de otros métodos muy conocidos (p.ej: Ziv-Lempel), sino que además permiten realizar búsquedas dentro del texto comprimido, sin necesidad de descomprimirlo, de forma mucho más rápida que cuando dichas búsquedas se realizan sobre el texto plano. Siguiendo con la idea de la compresión basada en palabras, en esta tesis se desarrollan cuatro nuevas técnicas de compresión que dan comienzo a una nueva familia de compresores basados en la utilización de códigos densos. De estas cuatro técnicas, dos son semiestáticas y dos son dinámicas. Sus nombres son: End-Tagged Dense Code, (s,c)-Dense Code, Dynamic End-Tagged Dense Code y Dynamic (s,c)-Dense Code. Además también se ha desarrollado, por primera vez, un compresor dinámico orientado a bytes y basado en palabras, que usa Huffman como esquema de codificación. Los resultados experimentales obtenidos al comparar nuestros compresores contra corpus reales han demostrado que estos suponen una aportación relevante en el campo de la compresión, tanto para los sistemas orientados a Text Retrieval, como en sistemas orientados a la transmisión de datos, ya que nuestros compresores comprimen más y más eficientemente que muchos de los compresores actualmente en uso (gzip, compress, etc).

Autor: FERRÁNDEZ AGULLÓ FRANCISCO.
Año: 2004.
Universidad: ALICANTE [www.ua.es].
Centro de lectura: UNIVERSIDAD DE ALICANTE.
Centro de realización: ESCUELA POLITÉCNICA SUPERIOR.

Resumen: El incremento de la velocidad de los ordenadores y los nuevos algoritmos de ataque que surgen continuamente hacen preciso el aumento constante de la seguridad de los sistemas criptográficos. Lo que hoy en día es seguro puede que no fo sea al cabo de pocos años. Esta necesidad en el aumento de la seguridad no está exenta de inconvenientes. La complejidad alcanzada actualmente (de orden exponencial) con los sistemas de curva eliptica no parece mejorable ya que existen determinados ataques que siempre son aplicables sobre grupos (los de raíz cuadrada, como el Pollard-r). Otra opción para incrementar la seguridad consiste en aumentar el tamaño de los sistemas con claves más grandes. Pero esto requiere la utilización de claves de gran tamaño si utilizamos el DLP (Discrete Logarithm Problem) en el que se basa el DSA (Digital Signature Algorithm) o ellFP (Integer Factorization Problem) en el que se basa el RSA. El ECDLP (Elliptic Curve DLP) utiliza claves mucho más cortas pero requiere de grandes recursos computacionales ya que es necesario calcular el orden del grupo de puntos racionales de la curva eliptica. Con el objetivo de diseñar sistemas más seguros sin las dificultades comentadas, se proponen tres funciones unidireccionales que aumentan el tamaño del problema con claves cortas y sin apenas requerimientos de recursos. Los tres sistemas se han diseñado como problemas matemáticos complejos capaces de definir funciones unidireccionales con trampa, necesarias para el diseño de sistemas criptográficos de clave pública. La primera propuesta es un sistema criptográfico lineal de curva elíptica basado en matrices que consiste en una aplicación entre matrices construidas de forma polin6mica y n-tuplas de puntos en n-tuplas de puntos. Esta función consigue aumentar la seguridad de los esquemas criptográficos mediante el aumento de las instancias necesarias para resolverlo. Además, se muestra adaptable a los protocolos más importantes basados en el ECDLP. La segunda propuesta reside en un sistema criptográfico no lineal de curva elíptica y matrices formales que consiste en la exponenciación de elementos construidos con dos escalares y un punto de una curva eliptica. Este sistema se muestra equivalente al ECDLP aunque, en todo caso, requiere mayor esfuerzo de computación por iteración mientras que, mediante algoritmos de exponenciación rápida, la aplicación de la función resulta eficiente. La tercera propuesta consiste en un sistema criptográfico no lineal de curva elíptica y matrices formales triangulares por bloques que se fundamenta en la exponenciación de matrices formales construidas con bloques de escalares y un bloque de puntos de una curva elíptica. Este sistema permite aumentar la seguridad tanto como se precise sin apenas recursos. Además, se muestra la aplicabilidad a los protocolos criptográficos mediante el intercambio de claves y el cifrado. Además de la descripción y análisis de los tres sistemas propuestos, se realiza una implementación práctica de los mismos y de los protocolos criptográficos adaptados, junto con una serie de consideraciones de implementación.

Autor: ÁLVAREZ SÁNCHEZ RAFAEL IGNACIO.
Año: 2005.
Universidad: ALICANTE [www.ua.es].
Centro de lectura: ESCUELA POLITÉCNICA SUPERIOR.
Centro de realización: ESCUELA POLITÉCNICA SUPERIOR.

Resumen: Este trabajo está motivado fundamentalmente por las excelentes propiedades criptográficas y de aleatoriedad observadas en ciertas construcciones de matrices triangulares superiores por bloques con elementos en Zp, siendo p primo. Esta técnica matricial resulta interesante, no sólo por sus posibilidades criptográficas, sino también por su elevada flexibilidad ya que permite que el algoritmo resultante sea adaptable a diversos tipos de plataformas (hardware, software, dispositivos de bajo coste, etc.)y a diversas necesidades operacionales (alto rendimiento , alta seguridad, baja utilización de memoria ,etc). Además, no sólo ofrece la posibilidad de crear generadores pseudoaleatorios o cifradores en flujo, existen mecanismos para crear otro tipo de primitivas a partir de la misma técnica base. Esto ofrece grandes ventajas a la hora de integrar diferentes servicios criptográficos en un mismo componente. Se ha propuesto un generador pseudoaleatroria con las características deseables para ser empleado como el generador de secuencia cifrante en un criptosistema de cifrado en flujo binario aditivo. Está basado en las potencias de las matrices triangulares superiores por bloques defindas en Zp. Según se van tomando estas potencias, se obtiene una secuencia de matrices de gran período y muy buenas propiedades en términos de aleatroriedad. Para lograr rendimientos comparables al criptosistema de cifrado en flujo RC4, se ha diseñado una implementación optimizada en Z2 basada en el concepto de matrices empaquetadas y operaciones binarias entre palabras de bits que permite, además el aprovechamiento directo de los registros de gran tamaño presentes en las arquitecturas recientes. También se ha realizado una implementación harware de la optimización en Z2 , explotando las posibilidades de paralelismo presentes en dicha plataforma. Los resultados obtenidos han sido muy buenos: las características estadísticas superan en la mayoría de los casos a los criptosistemas de referencia, mientras que el rendimiento es perfectamente comparable a criptosistemas tan eficientes como RC4.

Autor: OLIVER GIL JOSE SALVADOR.
Año: 2005.
Universidad: POLITÉCNICA DE VALENCIA [www.upv.es].
Centro de lectura: UNIVERSIDAD POLITÉCNICA DE VALENCIA.
Centro de realización: UNIVERSIDAD POLITÉCNICA DE VALENCIA.

Autor: FERNÁNDEZ CÓRDOBA CRISTINA.
Año: 2005.
Universidad: AUTÓNOMA DE BARCELONA [www.uab.es].
Centro de lectura: ETSE.
Centro de realización: ESCUELA DE POSTGRADO.

Resumen: El año 1972, la nave espacial Mariner 9 transmitió imágenes de Marte utilizando el código Reed-Muller de orden 1 RM(1,5). Estos códigos son de especial interés por la facilidad del proceso de construcción, codificación y decodificación. A partir del año 1994, se abrió una nueva puerta al a investigaicón de la teoría de códigos. Se demostró que algunos códigos no lineales muy importantes (Preaparta, Kerdock, etc) tenían estructura de códigos Z-4-lineales. A partir de ese momento, también se empezó a estudiar la relación de los códigos Reed-Muller con los códigos cuaternarios. A parecieron un par de familias de códigos cuaternarios relacionados con los Reed-Muller, los códigos (QRM(r,m) y los códigos ZRM(r,m). En esta Tesis estudiamos con profundidad estas dos familias. Respecto a los códigos QRM(r,m), describiremos una generalización, construiremos una clase donde, para cada valor r y m, todo código C que pertenezca ala clase cumpla que C módulo 2 es, exactamente, el código RM(R,m). Generalizaremos las propiedades básicas de los códigos QRM(r,m) a los códigos de la clase. Se demuestra que todos los códigos Preparata-like i Kerdock-like son la imagen vía la aplicación de Gray de códigos en la clase. También se calcula el rango i la dimensión del núcleo de los códigos de esta clase. Finalmente, podemos encontrar diferentes construcciones de estos códigos y la creación de cadenas anidadas y propiedades de estas cadenas relacionadas con la dualidad y la distancia mínima de los códigos que la forman. En la literatura, hay dos definiciones diferentes de códigos ZRM(r,m). Haremos servir esta notación ZRM(r,m), para los códigos definidos por Hammons, Kumar, Caldermakr, Sloane y Sole el año 1994 i ZRM*(r,m) para los códigos definidos posteriormente por Zhe-Xian Wan el año 1997. Hemos demostrado que estos códigos coinciden si y sólo si r=0,1,2,m,m+1 que son, exactamente, los valores para los cuales la imagen de estos códigos vía la aplicación de Gray es un código Reed-Muller. Estudiamos propiedades de estas dos familias. Las imágenes de la aplicación de Gray de los códigos ZRM(r,m) con códigos lineales y damos su dimensión y calculamos el rango y la dimensión del núcleo de las imágenes de los códigos ZRM* (r,m).

Autor: QUEIRUGA DIOS M. ARACELI.
Año: 2005.
Universidad: SALAMANCA [www.usal.es].
Centro de lectura: FACULTAD DE CIENCIAS.
Centro de realización: FACULTAD DE CIENCIAS.

Resumen: En el presente trabajo se estudian los criptosistemas de clave pública denominados 'de mochila' de alta densidad. En particular, se lleva a cabo un análisis pormenorizado del criptosistema de Chor-Rivest. Estos tipos de criptosistemas se denominan de mochila por estar basados en el problema computacional del mismo nombre. El primero de ellos fue propuesto por Merkle y Hellman y roto posteriormente por Shamir y Brickell. Más tarde, en 1985, Chor y Rivest propusieron otros criptosistema que ha permanecido invulnerable hasta que Vaudenay, en 2001, propuso un criptoanálisis para algunos de los parámetros originales. De forma más precisa, Chor y Rivest propusieron un criptosistema de tipo mochila, basado en la aritmética de cuerpos finitos, F_{q^h}, siendo q un primo, o la potencia de un primo, cercano a 200 y h menor = q un entero cercano a 25. Este criptosistema se caracteriza porque para la generación de las claves se requiere del cómputo de logaritmos en el cuerpo finito. Problema que, como es sabido, es considerado muy difícil desde el punto de vista computacional. Sin embargo, la seguridad de este criptosistema no se basa en el problema del cómputo de logaritmos discretos, sino en la dificultad de resolver un problema de mochila de alta densidad. El ataque propuesto por Vaudenay determina una clave privada equivalente a la empleada por el destinatario. Para ello, se busca la norma de generador del grupo multiplicativo F_{q^s}*, siendo s un divisor de h verificando s menor = sqrt{h+1/4}+1/2. Una vez calculada dicha norma, se determina la permutación empleada en la fase de generación de las claves. Conociendo ambos parámetros, Vaudenay demuestra cómo es posible determinar una clave equivalente a la clave privada original. Posteriormente se analiza el ca so en el que los parámetros q y h del cuerpo finito sobre el que se lleva a cabo la aritmética del criptosistema de Chor-Rivest sean tales que no permitan llevar a cabo, de forma efectiva, el ataque de Vaudenay y que siga siendo eficiente para los procesos de cifrado y descifrado de mensajes. Tales parámetros son q = 409 y h = 17. La memoria se acompaña de los procedimientos que permiten llevar a cabo una implementación práctica en Maplae de los diferentes aspectos estudiados.

Autor: RUIZ HIDALGO JAVIER.
Año: 2006.
Universidad: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Centro de lectura: Aula de Teleen.-·Edif. B-3-Campus Nord.
Centro de realización: D5 108 Nord.

Resumen: Este trabajo estudia la utilidad de explotar la sinergia entre las representaciones de compresión e indexación de secuencias de vídeo. El estudio se ha separado en dos tareas principales. En la primera tarea, las representaciones de compresión se han analizado para producir representaciones de indexación más optimizadas. En la segunda tarea, las representaciones de indexación se han explotado para generar representaciones de compresión más eficientes. En esta tesis, la expresión ârepresentación de compresión❠se refiere a todos aquellos datos, llamados normalmente bitstream, que describen el contenido digital de una manera compacta, usando el menor número de bits posible y permitiendo a su vez la funcionalidad de visualización del contenido. Por otro lado, el término ârepresentación de indexación❠se refiere a todas aquellas estructuras de datos, descriptores o información extra que ha sido extraída del contenido digital para proporcionar funcionalidades de indexación, resumen, búsqueda o adquisición. Durante los últimos años, ambas representaciones has sido estudiadas independientemente y, por ello, las representaciones de compresión e indexación se han obtenido o generado usando diferentes esquemas y algoritmos. Sin embargo, ambas representaciones describen el mismo contenido digital y, por lo tanto, es normal pensar que cada una de ellas se puede beneficiar de la otra. En la primera tarea de la tesis, las representaciones de compresión son analizadas para crear representaciones de planos de vídeo más robustas y optimizadas. En particular, ambas representaciones investigan los mosaicos para crear representaciones más eficientes. El esquema de codificación por mosaicos del estándar MPEG-4 se amplía para poder usar el mosaico, no sólo en codificación, sino para resumir y describir planos de vídeo. La representación de indexación que se propone en este trabajo se basa en el contenido de la escena ya que ésta es analizada para separar los objetos de primer y segundo plano. El mosaico se utiliza para representar los objetos del segundo plano mientras que otras representaciones, llamadas regiones clave, son creadas para representar los objetos del primer plano. Además, en este trabajo los mosaicos se mejoran mediante operadores conexos para que puedan representar mejor el segundo plano de la escena sin que ello suponga ninguna pérdida en su eficiencia de codificación. Los mosaicos también se utilizan en el algoritmo de extracción de regiones clave, permitiendo la segmentación y descripción de objetos de primer plano. La representación de indexación que propone en esta tesis supone un resumen compacto del plano de vídeo analizado. Además, la representación de indexación puede enriquecerse añadiendo información de movimiento con lo que se puede tener una primera idea de cómo los objetos del primer plano se mueven en la escena del plano de vídeo. En la segunda tarea, se estudia la mejora de la eficiencia de las representaciones de compresión, en particular del estándar H.264, mediante el uso de representaciones de indexación. Se investigan cuatro técnicas distintas para probar que las representaciones de indexación, incluso si son extraídas para cubrir otras funcionalidades, pueden ser aprovechadas para incrementar la eficiencia de los codificadores de vídeo actuales. En la primera técnica propuesta, las distintas transiciones de vídeo se codifican empleando la información extra de un descriptor de transiciones. La segunda técnica reformula parte de la estimación de movimiento de un codificador híbrido como un clásico problema de búsqueda y adquisición. Esta segunda técnica mejora la selección de tramas de referencia a largo plazo mediante representaciones de indexación de bajo nivel como por ejemplo descriptores de color. .