Matemática e engenharia informática

Fundamentos da Criptografia. Ferramentas B´ sicas a (Vers˜ o Parcial: 25 de abril de 2007) a Favor n˜ o distribuir a
Oded Goldreich Traduzido do original em inglˆ s e Foundations of Cryptography. Basic Tools (Cambridge University Press, c 2001) por Ruy J. Guerra B. de Queiroz

2

´ Indice
1 Introducao ¸˜ 1.1 Criptografia: T´ picos Principais . . . . . . . . . . . . . . . . . . . . o 1.1.1 Esquemas de Encriptacao . . . . . . . . . . . . . . . . . . . ¸˜ 1.1.2 Geradores Pseudoaleat´ rios . . . . . . . . . . . . . . . . . . o 1.1.3 Assinaturas Digitais . . . . . . . . . . . . . . . . . . . . . . 1.1.4 Protocolos Tolerantes-a-Falha e Provas de Conhecimento-Zero 1.2 Alguns Conhecimentos B´ sicos . . . . . . . . . . . . . . . . . . . . a 1.2.1 Convencoes de Notacao . . . . . . . . . . . . . . . . . . . . ¸˜ ¸˜ 1.2.2 Trˆ s Desigualdades . . . . . . . . . . . . . . . . . . . . . . . e 1.3 O Modelo Computacional . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 P, N P, e N P-Completude . . . . . . . . . . . . . . . . . . 1.3.2 Tempo Polinomial Probabil´stico . . . . . . . . . . . . . . . . ı 1.3.3 Tempo Polinomial N˜ o-Uniforme . . . . . . . . . . . . . . . a 1.3.4 Suposicoes de Intratabilidade . . . . . . . . . . . . . . . . . ¸˜ 1.3.5 M´ quinas-Or´ culo . . . . . . . . . . . . . . . . . . . . . . . a a 1.4 Motivacao para o Tratamento Rigoroso . . . . . . . . . . . . . . . . . ¸˜ 1.4.1 A Necessidade de um Tratamento Rigoroso . . . . . . . . . . 1.4.2 Conseq¨ encias Pr´ ticas do Tratamento Rigoroso . . . . . . . uˆ a 1.4.3 A Tendˆ ncia a Ser Conservador . . . . . . . . . . . . . . . . e 1.5 Miscelˆ nea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 1.5.1 Notas Hist´ ricas . . . . . . . . . . . . . . . . . . . . . . . . o 1.5.2 Sugest˜ es para Leitura Adicional . . . . . . . . . . . . . . . o 1.5.3 Problemas Em Aberto . . . . . . . . . . . . . . . . . . . . . 1.5.4 Exerc´cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . ı Dificuldade