Dissertação

On trapdoor Kolmogorov one-way functions and elliptic curves cryptography EVALUATED

O principal objectivo desta dissertação é estudar a segurança de sistemas criptográficos baseados em curvas elípticas usando complexidade de Kolmogorov e funções de sentido único como veículo de análise da segurança de cada sistema. A motivação por trás desta dissertação é análisar funções de sentido único usando complexidade de Kolmogorov. Compreender criptografia baseado em curvas elípticas e sabendo que funções de sentido único são suficientes para a construção de sistemas criptográficos de chave púbica foi outra grande motivação para a análise de esquemas criptográficos definidos por uma função Kolmogorov de sentido único com alçapão e construída sobre curvas elípticas. Ao longo desta tese, iremos definir uma nova família de funções, que denotaremos por funções Kolmogorov de sentido único com alçapão. Iremos também provar que para cada função, o número de alçapões é sempre menor, (por uma fracção polinomial) do que o número de possíveis alçapões. Apresentamos um sistema criptográfico de chave publica baseado em curvas elípticas e denotaremos por f a função que emula este sistema. Serão obtidas conclusões sobre a segurança do sistema criptográfico, baseadas em observações feitas sobre o tamanho de cada chave privada visto que obteremos um resultado assimptótico que expressa um limite inferior para o tamanho de cada chave privada. Assumindo que ECDLP não está em P, iremos provar que f é uma função Kolmogorov de sentido único e que pode ser vista, com recurso a uma função auxiliar, como uma função de uma família de funções Kolmogorov de sentido único com alçapão.
Complexidade de Kolmogorov, Kolmogorov de sentido único com  alçapão, Criptografia baseada em curvas elípticas, Segurança criptográfica

Junho 20, 2014, 10:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

CO-ORIENTADOR

André Nuno Carvalho Souto

Instituto Superior Técnico

Especialista

ORIENTADOR

Paulo Alexandre Carreira Mateus

Departamento de Matemática (DM)

Professor Associado