Busca de permutações APN criptográficas

Abstract

O trabalho de pesquisa descrito neste relatório foi realizado em duas partes, no período entre jan/2016 e fev/2018, e trata de um estudo sobre permutações APN (importantes no projeto de cifradores simétricos) com o auxílio dos conceitos de ambiguidade e deficiência, desenvolvidos pelo Prof. Daniel Panario e seu grupo de pesquisa na Universidade de Carleton, em Ottawa, Canadá. A primeira parte deste estudo foi executada durante um pós-doutorado do autor no Canadá (entre jan/2016 e fev/2017) e consistiu em uma caracterização diferencial completa (incluindo espectro diferencial, ambiguidade e deficiência) de todos os polinômios de permutação sobre corpos finitos com baixo grau (grau até 6). Na segunda parte, executada de mar/2017 a fev/2018, no escopo de um projeto de pesquisa do departamento INE/UFSC, o objetivo foi realizar uma busca computacional por permutações APN definidas em anéis sobre inteiros. Esta parte envolveu implementações (em C/C++) de buscas exaustivas do tipo backtracking podadas com heurísticas específicas a fim de encontrar permutações APN (2-uniformes) sobre Z_2 x Z_16. Os melhores resultados obtidos nesta segunda parte consistiram em permutações 3-uniformes sobre Z_2 x Z_16. Note-se que isto corresponde a uma busca em um universo de busca de tamanho maior do que 2^{117}. Os melhores casos encontrados pelo backtracking (com a poda heurística) foram refinados com a aplicação de técnicas de busca do tipo Tabu search e Simulated Annealing. O melhor resultado obtido nesta segunda parte chegou muito perto de uma permutação APN (2-uniforme) e consistiu em uma permutação 3-uniforme sobre Z_2 x Z_16, mas com apenas 24 valores iguais a 3 no espectro diferencial (todos os outros 968 valores eram menores ou iguais a 2).