Tópicos em Algoritmos - Fundamentos da Criptografia (CI1355 / INFO7056)

Professor: Nicollas Mocelin Sdroievski
Para entrar em contato comigo, envie um e-mail para nmsdroievski[arroba]ufpr.br
Horário das aulas:
- Terça-feira 17h30-19h30
- Quinta-feira 17h30-19h30
Horário de antendimento quintas-feiras 13:30 - 14:30 ou a combinar (com agendamento)
Local das aulas:
- PA-05

Datas importantes

4/8: Não haverá aula

6/8: Não haverá aula

11/8: Início das aulas

8/9: Não haverá aula (Padroeira de Curitiba)

15/9: Não haverá aula (semana acadêmica)

17/9: Não haverá aula (semana acadêmica)

22/9: Entrega da L1 / P1

22/10: Entrega da L2 / P2

26/11: Entrega da L3 / P3

Datas das apresentações de projeto a definir

Descrição da disciplina
Na disciplina, seguiremos principalmente o livro de Katz e Lindell. Sugiro conferir a introdução do livro (disponível aqui, em inglês) para ter uma ideia melhor do que será abordado. Também apresento uma breve descrição a seguir.

Como definir o que é um protocolo criptográfico seguro? Vamos focar no exemplo clássico em que Alice gostaria de enviar uma mensagem m para Bob, de forma que se um intermediário malicioso Malorie intercepta a comunicação, não deve ser possível recuperar a mensagem enviada. Para isso, Alice primeiro criptografa m, obtendo um texto cifrado c, que é enviado para Bob. Certamente queremos que Bob seja capaz de recuperar m a partir de c, e Malorie não. Porém, há mais perguntas a serem respondidas: Nesta disciplina, estudaremos a criptografia moderna, que se distingue da criptografia clássica pela sua ênfase em definições, suposições e provas rigorosas de segurança. Primeiro, define-se que tipo de segurança é esperada do protocolo criptográfico (respondendo, por exemplo, as perguntas acima). Depois, prova-se que é computacionalmente inviável quebrar a segurança do protocolo, a menos que a suposição definida seja falsa. Neste sentido, a Criptografia Moderna é inseparável da teoria de Complexidade Computacional. Especificamente, a segurança de um protocolo é estabelecida através de uma redução: se um adversário for capaz de quebrar a segurança do protocolo, então esse adversário também seria capaz de resolver de maneira eficiente um problema considerado intratável, como o problema da fatoração.

Por que estudar Criptografia com esse foco mais teórico? Em primeiro lugar, não é possível entender se um protocolo é seguro se nem de fato definimos o que é um protocolo seguro. Além disso, é comum que pequenas modificações, aparentemente inofensivas, em protocolos inicialmente seguros resultem em um protocolo inseguro (para exemplos, confira este ataque e este outro ataque). Dessa forma, é importante conhecer não apenas a estrutura dos algoritmos, mas as ferramentas formais para provar que eles são, de fato, seguros. Essas ferramentas ajudam a transformar a intuição de que um protocolo é seguro em uma prova matemática de segurança, nos permitindo projetar, analisar e modificar protocolos sem introduzir vulnerabilidades catastróficas.

Conteúdos cobertos na disciplina:
- Criptografia clássica versus moderna
- Segredo perfeito
- Primitivas criptográficas (funções unidirecionais, geradores pseudo-aleatórios, funções pseudo-aleatórias)
- Criptografia de chave privada
- MACs (códigos de autenticação de mensagens)
- Funções hash
- Criptografia de chave pública
- Tópicos adicionais: Criptografia pós-quântica, provas de conhecimento zero, construção de primitivas criptográficas

Sistema de Avaliação:
Listas de exercícios (L1 + L2 + L3) / 3 OU Projeto semestral (P1 + P2 + 3*P3) / 5
Primeira lista de exercícios (atualizada 27/08).
Descrição do projeto.

Slides da disciplina: (aqui)
Notas de aula complementares: (aqui)

Sugestões de projeto semestral (atualizadas durante o semestre)

Mais teóricas Relacionadas com Complexidade Computacional Mais práticas
Bibliografia principal Bibliografia complementar