Fundamentos de la Criptografía CC5301 (2011/01)
Profesor: Alejandro Hevia
Propósito: El propósito del curso es familiarizar al estudiante con los conceptos teóricos que fundamentan la criptografía moderna, así como dotar al estudiante de herramientas de análisis para diseñar y evaluar formalmente algoritmos y protocolos criptográficos.
Aspectos administrativos:
Cátedra: Martes, Jueves 2:30-4:00pm, Sala por anunciar
Auxiliar: No hay.
Sitio web oficial (especialmente el Foro de Discusión): ucursos
Carga académica: 10 UD,
Requisitos: ((MA34A/MA3403),(CC40A/CC4102))/AUTOR
Carácter del curso: electivo Cs. de la Computación
Novedades
- 24 de Marzo 2011: Está disponible el template y archivo de macros para las transcripciones.
Material de Lectura
En esta sección pondremos material de lectura recomendada para el curso.
Estas lecturas son altamente recomendadas para las clases de cátedra indicadas.
- Martes 15 y Jueves 17 de Marzo: Capitulo 1 de libro de Goldreich (Basic Tools).
- Jueves 17 de Marzo: "Tail Inequalities", Apunte de Mihir Bellare,
PDF.
Temario
- Introducción
- Motivación y aplicaciones
- Revision conceptos básicos necesarios: notación y modelos de computación,
probabilidades, complejidad básica
- Introducción a la Dificultad Computacional
- Funciones unidireccionales (one-way functions, OWFs): definiciones, variantes,
OWF que preservan el largo,
- OWFs débiles y fuertes, OWFs débiles implican OWFs fuertes
- Permutaciones unidireccionales con puertas secretas (trapdoor permutations, TDP): definiciones,
ejemplos.
- Pseudo-Aleatoriedad
- Generadores pseudo-aleatorios (PRGs): definiciones, no-ejemplos, implicancias
- PRGs a partir de OWFs
- Predicados de núcleo duro y el teorema de Goldreich-Levin
- Indistinguibilidad: muestreo simple implica muestreo múltiple.
- Funciones pseudo-Aleatorias (PRFs) y permutaciones pseudo-aleatorias (PFPs): Construcciones
genéricas a partir de PRG y basadas en teoría de números.
- Aplicaciones de Pseudo-Aleatoriedad: Encriptación y Firmas Seguras.
- Encriptación: definiciones, esquemas de clave privada, esquemas de clave pública
- Firmas: definiciones, esquemas probables a partir de OWF y permutaciones con puerta secreta.
- Introducción a Nula Divulgación (Zero knowledge)
- Demostraciones interactivas (IP), robustez computacional versus estadística/perfecta.
- Nula Divulgación (Zero Knowledge): motivación, conceptos,
dem. para Isomorfismo de Grafos, y residuosidad cuadrática.
- Esquemas de Vinculación (Commitments): definición y construcciones básicas
(genéricas y basadas en teoría de números).
- Nula divulgación para todo lenguaje NP: demostración para 3-Coloramiento.
- Demostraciones de Conocimiento (Proofs of knowledge)
- Aplicaciones: Identificación.
- Variantes y extensiones: witness indistinguishability, simulación black-box versus
non-black box, composición, nula divulgación concurrente y reseteable.
- Tópicos Avanzados:
- Introducción a la Computación Multipartita Segura
- Motivación, conceptos y definiciones.
- Oblivious Transfer.
- Evaluación segura de funciones: caso 2 participantes, caso multiparticipante.
- Generalizaciones: Computación Multipartita Segura, y Universal composability.
- Criptografía Post-cuántica.
- Introducción a computadores cuánticos.
- Algoritmos cuánticos: Algoritmo de Shor y algoritmo de Grove, y sus
efectos en la criptografía moderna.
- Esquemas y Protocolos post-cuánticos: ejemplos y problemas abiertos.
Nota:
Este es un curso avanzado. Por lo tanto, el temario del
curso es potencialmente variable dependiendo del interés de los estudiantes.
Evaluación:
La evaluación se basa en dos actividades:
- Lectura y presentación en clase de un artículo de investigación
por parte del estudiante,
- Resolución de 2 ó 3 tareas teóricas, y
- Transcripción de al menos 2 clases de cátedra. Debe realizarse en LaTeX
(si no sabe, se recomienda mirar este tutorial). He aquí el
template
y archivo de macros
para las transcripciones.
Alternativamente, el requisito de lectura y presentación de paper es reemplazable
por el desarrollo de una implementación en software de algún protocolo revisado en el curso,
siempre que tal cambio sea autorizado explícitamente por el profesor (hasta la 2da semana de clases).
El proyecto planteado por
el estudiante debe ser lo suficientemente interesante para hacer la
excepción.
Posibles Artículos para presentar:
Clásicos:
- "How to Construct Random Functions", Goldreich, Goldwasser, and Micali.
(PDF).
- "How to Construct Pseudorandom Permutations from Pseudorandom Functions",
Luby and Rackoff. SIAM Journal on Computing 1988.
(PDF).
Este paper introduce una manera estandar de construir de funciones pseudo-aleatorias.
- "Probabilistic Encryption and How to Play Mental Poker Hiding All Partial Information", Goldwasser, S. and
Micali, S. In STOC'82.
(PDF). Artículo fundacional sobre
encriptación moderna y su formalización.
- "Probabilistic Encryption", Goldwasser, S. and Micali, S., JCSS 1984,
(PDF). Version journal del paper anterior.
- "How to Generate Cryptographically Strong Sequences of Pseudo-random Bits",
Blum and Micali.
- "The Knowledge Complexity of Interactive Proof Systems", Goldwasser, Micali,
and Rackoff.
(PDF). Artículo que presentó la noción de ZKP y PoK.
(Versión de STOC'85: PDF).
- "Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems",
Goldreich, Micali, and Wigderson.
(FOCS'86: PDF,
JACM'91: PDF).
- "How to Prove Yourself: Practical Solutions to Identification and Signature
Problems", Fiat and Shamir. Crypto'86.
(PDF).
- "Witness indistinguishable and witness hiding protocols", Uriel Feige , Adi Shamir,
STOC'90.
(PDF). Introduce los conceptos de WI y WH.
- "Proofs of Partial Knowledge and Simplied Design of Witness Hiding Protocols", Ronald Cramer, Crypto'94
(PDF). Muestra cómo diseñar protocolos
donde es posible demostrar conocimiento parcial (de witnesses).
- "A digital signature scheme secure against adaptive chosen-message attacks", Shafi Goldwasser, Silvio Micali,
Ronald L. Rivest, SIAM Journal on Computing 1988.
(PS). Artículo fundacional en cómo diseñar firmas digitales a partir
de factorización. Formaliza la definición UF-CMA estándar de seguridad para firmas digitales.
- "Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme", O. Goldreich,
(PS). Simplifica y aclara la construcción
original en GMR ("A digital signature...").
- "On Defining Proofs of Knowledge", M. Bellare, O. Goldreich, Crypto'92.
(PS). Discusión de aspectos
delicados de la formalización de PoK.
Tareas
Las tareas consistirán en demostraciones y resolución de
problemas, principalmente teóricos.
Referencias Utiles: Otros cursos
- Curso de Yehuda Lindell: recomendado.
- Curso de Jon Katz: recomendado.
- Curso de Luca Trevisan: recomendado, cubre
mucho más de lo que cubriremos acá.
- Curso de Boaz Barak: recomendado, temas de pseudo-aleatoriedad.
- Curso de Mihir Bellare: algo
más focalizado en ZK y en secure multiparty computation.
- Curso de Rafail Ostrovsky.
recomendado, cubre mucho más de lo que cubriremos acá.
- Curso de Wikstrom. Más
parecido al CC5301 que al nuestro.
Bibliografía:
- Oded Goldreich, “Foundations of Cryptography, Basic Tools”, Cambridge University Press, 2001
- Oded Goldreich, “Foundations of Cryptography, Basic Applications”, Cambridge University Press, 2004
- Jonathan Katz, Yehuda Lindell, “Introduction to Modern Cryptography”, Editorial Chapman and Hall/CRC, 2008
- Mihir Bellare y Phil Rogaway, “Introduction to Cryptography, Lecture Notes”, University of California San Diego, 2006.
(Disponible en versiones del curso para
pregrado, y de
postgrado)
- Douglas Stinson, “Cryptography, Theory and Practice”, Third edition, Editorial Chapman and Hall/CRC, 2006
- Oded Goldreich, “Computational Complexity”, Editorial Cambridge, 2008
Última modificación: 7 Marzo 2011.
|