Cryptographic security of individual instances
Luís Antunes
Departamento de Ciência de Computadores
Universidade do Porto

Resumo

For symmetric cipher systems one can prove unconditional security against an opponent with unlimited computational power. The proof is based on the notion of entropy. However, this measure does not provide a satisfactory framework to the analysis of public key cryptosystems, always based on cryptographic assumptions. The problem is that Shannon´s definition of information is a purely statistical notion, which ignores the computational difficulty of extracting the information. The public key and the cipher text together contain all the Shannon information concerning the plaintext, but the information is computationally inaccessible. So, we face this intriguing question: what is accessible information? In this talk we present a first attempt to answer this question based on algorithmic entropy also known as Kolmogorov complexity.

Encontro Matemático SPM/CIM em Teoria da Codificação, Informação e Criptografia