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

  1. Introducción
    1. Motivación y aplicaciones
    2. Revision conceptos básicos necesarios: notación y modelos de computación, probabilidades, complejidad básica
  2. Introducción a la Dificultad Computacional
    1. Funciones unidireccionales (one-way functions, OWFs): definiciones, variantes, OWF que preservan el largo,
    2. OWFs débiles y fuertes, OWFs débiles implican OWFs fuertes
    3. Permutaciones unidireccionales con puertas secretas (trapdoor permutations, TDP): definiciones, ejemplos.
  3. Pseudo-Aleatoriedad
    1. Generadores pseudo-aleatorios (PRGs): definiciones, no-ejemplos, implicancias
    2. PRGs a partir de OWFs
    3. Predicados de núcleo duro y el teorema de Goldreich-Levin
    4. Indistinguibilidad: muestreo simple implica muestreo múltiple.
    5. Funciones pseudo-Aleatorias (PRFs) y permutaciones pseudo-aleatorias (PFPs): Construcciones genéricas a partir de PRG y basadas en teoría de números.
  4. Aplicaciones de Pseudo-Aleatoriedad: Encriptación y Firmas Seguras.
    1. Encriptación: definiciones, esquemas de clave privada, esquemas de clave pública
    2. Firmas: definiciones, esquemas probables a partir de OWF y permutaciones con puerta secreta.
  5. Introducción a Nula Divulgación (Zero knowledge)
    1. Demostraciones interactivas (IP), robustez computacional versus estadística/perfecta.
    2. Nula Divulgación (Zero Knowledge): motivación, conceptos, dem. para Isomorfismo de Grafos, y residuosidad cuadrática.
    3. Esquemas de Vinculación (Commitments): definición y construcciones básicas (genéricas y basadas en teoría de números).
    4. Nula divulgación para todo lenguaje NP: demostración para 3-Coloramiento.
    5. Demostraciones de Conocimiento (Proofs of knowledge)
    6. Aplicaciones: Identificación.
    7. Variantes y extensiones: witness indistinguishability, simulación black-box versus non-black box, composición, nula divulgación concurrente y reseteable.
  6. Tópicos Avanzados:
    1. Introducción a la Computación Multipartita Segura
      1. Motivación, conceptos y definiciones.
      2. Oblivious Transfer.
      3. Evaluación segura de funciones: caso 2 participantes, caso multiparticipante.
      4. Generalizaciones: Computación Multipartita Segura, y Universal composability.
    2. Criptografía Post-cuántica.
      1. Introducción a computadores cuánticos.
      2. Algoritmos cuánticos: Algoritmo de Shor y algoritmo de Grove, y sus efectos en la criptografía moderna.
      3. 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:

  1. Lectura y presentación en clase de un artículo de investigación por parte del estudiante,
  2. Resolución de 2 ó 3 tareas teóricas, y
  3. 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:
  1. "How to Construct Random Functions", Goldreich, Goldwasser, and Micali. (PDF).
  2. "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.
  3. "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.
  4. "Probabilistic Encryption", Goldwasser, S. and Micali, S., JCSS 1984, (PDF). Version journal del paper anterior.
  5. "How to Generate Cryptographically Strong Sequences of Pseudo-random Bits", Blum and Micali.
  6. "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).
  7. "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).
  8. "How to Prove Yourself: Practical Solutions to Identification and Signature Problems", Fiat and Shamir. Crypto'86. (PDF).
  9. "Witness indistinguishable and witness hiding protocols", Uriel Feige , Adi Shamir, STOC'90. (PDF). Introduce los conceptos de WI y WH.
  10. "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).
  11. "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.
  12. "Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme", O. Goldreich, (PS). Simplifica y aclara la construcción original en GMR ("A digital signature...").
  13. "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

  1. Curso de Yehuda Lindell: recomendado.
  2. Curso de Jon Katz: recomendado.
  3. Curso de Luca Trevisan: recomendado, cubre mucho más de lo que cubriremos acá.
  4. Curso de Boaz Barak: recomendado, temas de pseudo-aleatoriedad.
  5. Curso de Mihir Bellare: algo más focalizado en ZK y en secure multiparty computation.
  6. Curso de Rafail Ostrovsky. recomendado, cubre mucho más de lo que cubriremos acá.
  7. Curso de Wikstrom. Más parecido al CC5301 que al nuestro.

Bibliografía:

  1. Oded Goldreich, “Foundations of Cryptography, Basic Tools”, Cambridge University Press, 2001
  2. Oded Goldreich, “Foundations of Cryptography, Basic Applications”, Cambridge University Press, 2004
  3. Jonathan Katz, Yehuda Lindell, “Introduction to Modern Cryptography”, Editorial Chapman and Hall/CRC, 2008
  4. 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)
  5. Douglas Stinson, “Cryptography, Theory and Practice”, Third edition, Editorial Chapman and Hall/CRC, 2006
  6. Oded Goldreich, “Computational Complexity”, Editorial Cambridge, 2008

Última modificación: 7 Marzo 2011.