Motivando a palestra sobre os fundamentos da criptografia

10

Esta questão segue o mesmo discurso inspirador dos alunos do último ano do ensino médio . Meu Ph.D. orientador me pediu para dar uma palestra inspiradora para o novo M.Sc. alunos. O assunto são fundamentos da criptografia , que é melhor ilustrada pelo livro de Goldreich . A conversa vai demorar cerca de uma hora, e eu quero familiarizar os alunos para as principais construções (como one-way funções / permutações, geradores pseudor-aleatório, provas de conhecimento zero, criptografia / esquemas de assinatura, etc.), e resolvido e problemas não resolvidos no campo.

Eu quero manter a conversa muito motivadora . O principal problema é duplo:

  1. Os fundamentos da criptografia precisam de um entendimento muito bom da teoria da complexidade computacional . Infelizmente, o M.Sc. os alunos não passaram por nenhum curso relacionado a essa teoria.
  2. Preciso apresentar alguns problemas como possíveis tópicos para um M.Sc. tese. Embora existam muitos problemas não resolvidos no campo, a maioria deles é muito difícil para um M.Sc. aluna.

Sugestões são bem-vindas. Além disso, estou muito interessado em sugestões para conversas semelhantes.


Edit: Eu achei a lista dos alunos de Goldreich extremamente inspiradora. Vou procurar outras listas desse tipo, mas você pode me ajudar se souber alguma lista semelhante. Veja também: Desmistificando a tese de mestrado e a pesquisa em geral: a história de algumas teses de mestrado .

MS Dousti
fonte

Respostas:

12

Como você não pode confiar em um conhecimento da teoria da complexidade, é necessário enfatizar a mudança de paradigma de segurança por obscuridade para segurança por intratabilidade, postulando a ideia de que alguns problemas são difíceis de resolver com eficiência. É claro que isso elimina os muitos problemas associados aos mundos da intratabilidade do Impagliazzo, mas fornece uma amostra da maneira como as criptos modernas funcionam.

para o ZKP, que é realmente incrível, há muitas maneiras de transmitir as idéias básicas intuitivamente. Veja, por exemplo, minha resposta sobre MO , bem como a hilariante Ali Baba e a história dos 40 ladrões . Embora tenham sido projetados originalmente para uma multidão mais jovem, eles funcionam bem em todas as idades para transmitir a intuição certa.

Suresh Venkat
fonte
@ Suresh: Muito obrigado. Alguma idéia sobre a segunda questão (motivar problemas não resolvidos no nível de mestrado)?
MS Dousti
11
Os dois links são os mesmos.
Tsuyoshi Ito
isso é difícil. não há muitos problemas tratáveis ​​nesse nível sem conhecer a complexidade.
Suresh Venkat
@Suresh: Sim, esse tem sido o meu problema desde que comecei a dar palestras sobre o assunto. Enfim, tenho que fazer compromissos; então você pode assumir com segurança que as pessoas de alguma forma entendem bem a complexidade! Então, como posso dar-lhes problemas motivadores para o M.Sc. tese?
MS Dousti
Eu sei muito pouco sobre criptografia, então :(. Em geometria, há uma boa lista de problemas em aberto. Talvez você deva vasculhar a lista de perguntas em aberto que foi postada aqui há algum tempo.
Suresh Venkat
4

Honestamente, parece-me que uma palestra sobre o nível (e com o foco) do livro de Goldreich estará além de um estudante de mestrado. (Chamar o conhecimento zero de "construção principal" da criptografia, deixando de fora a criptografia de chave privada, é certamente um ponto de vista não-padrão.)

Eu sugeriria um foco (ligeiramente) mais aplicado, nas linhas do livro de Katz-Lindell.

user686
fonte