Charla motivadora sobre los fundamentos de la criptografía

10

Esta pregunta está en la misma línea que la charla inspiradora para los alumnos de último año de secundaria . Mi doctorado El asesor me pidió que diera una charla inspiradora para el nuevo M.Sc. estudiantes El tema es la base de la criptografía , que se ilustra mejor con el libro de Goldreich . La charla durará aproximadamente una hora, y quiero familiarizar a los estudiantes con las construcciones principales (como funciones / permutaciones unidireccionales, generadores aleatorios de pseudor, pruebas de conocimiento cero, esquemas de cifrado / firma, etc.), y resuelto y problemas no resueltos en el campo.

Quiero mantener la charla muy motivadora . El principal problema es doble:

  1. Los fundamentos de la criptografía necesitan una muy buena comprensión de la teoría de la complejidad computacional . Por desgracia, el M.Sc. Los estudiantes no han aprobado ningún curso relacionado con esta teoría.
  2. Necesito presentar algunos problemas como posibles temas para un M.Sc. tesis. Si bien hay muchos problemas sin resolver en el campo, la mayoría de ellos son demasiado difíciles para un M.Sc. estudiante.

Las sugerencias son bienvenidas. Además, estoy muy interesado en los consejos para conversaciones similares.


Editar: la lista de estudiantes de Goldreich me pareció extremadamente inspiradora. Buscaré otras listas similares, pero puedes ayudarme si conoces listas similares. Ver también: Desmitificar la tesis de maestría y la investigación en general: la historia de algunas tesis de maestría .

MS Dousti
fuente

Respuestas:

12

Como no puede confiar en un conocimiento de la teoría de la complejidad, debe enfatizar el cambio de paradigma de seguridad por oscuridad a seguridad por intratabilidad, al plantear la idea de que algunos problemas son difíciles de resolver de manera eficiente. Esto, por supuesto, evita los muchos problemas asociados con los mundos de intractabilidad de Impagliazzo, pero da una idea de cómo funciona la criptografía moderna.

Para ZKP, que son realmente impresionantes, hay muchas maneras de transmitir las ideas básicas de forma intuitiva. Vea, por ejemplo, mi respuesta sobre MO , así como la divertida historia de Ali Baba y los 40 ladrones . Si bien estos fueron diseñados originalmente para una multitud más joven, funcionan bien en todas las edades para transmitir la intuición correcta.

Suresh Venkat
fuente
@Suresh: Muchas gracias. ¿Alguna idea sobre el segundo problema (motivar problemas no resueltos en el nivel de maestría)?
MS Dousti
1
Los dos enlaces son iguales.
Tsuyoshi Ito
Esa es una pregunta difícil. No hay muchos problemas que sean manejables a ese nivel sin conocer la complejidad.
Suresh Venkat
@Suresh: Sí, ese ha sido mi problema desde que comencé a dar charlas sobre el tema. De todos modos, tengo que hacer compromisos; ¡así que puede asumir con seguridad que las personas de alguna manera entienden bien la complejidad! Entonces, ¿cómo puedo darles problemas motivadores para M.Sc. ¿tesis?
MS Dousti
Sé muy poco acerca de la criptografía, así que :(. En geometría, hay una buena lista de problemas abiertos. Tal vez deberías revisar la lista de preguntas abiertas que se publicó aquí hace algún tiempo.
Suresh Venkat
4

Honestamente, me parece que una conferencia sobre el nivel (y con el enfoque) del libro de Goldreich estará más allá de un estudiante de maestría entrante. (Llamar al conocimiento cero una "construcción principal" de la criptografía, mientras se omite el cifrado de clave privada, es ciertamente un punto de vista no estándar).

Sugeriría un enfoque (ligeramente) más aplicado, en las líneas del libro de Katz-Lindell.

usuario686
fuente