Complexidade do cálculo de bases de Gröbner para criptanálise

Abstract

A resolução de sistemas polinomiais multivariáveis pelo calculo de bases de Grobner tem aplicações a criptologia do projeto de sistemas criptográficos baseados em polinômios multivariáveis a criptanálise algébrica do problema do logaritmo discreto sobre curvas elípticas. Estimar a complexidade desses cálculos e, contudo, um problema difícil, e diversos estudos deram origem a definições divergentes do parâmetro de complexidade desses sistemas chamado grau de regularidade. Nesse trabalho, revisamos algumas dessas definições, estabelecendo relações teóricas entre algumas delas e estudamos seu comportamento em dois casos práticos relevantes a criptografia, o problema da mochila e o sistema de criptografia Hidden Field Equations (HFE). Nossos resultados sugerem que algumas noções de grau de regularidade são desnecessárias e que proposições previamente demonstradas em termos de uma noção podem ser escritas utilizando outras delas. Essa ideia, juntamente com dados experimentais salientando a relevância dessas noções no caso do HFE podem ser exploradas mais a fundo a fim de simplificar a apresentação de resultados futuros e simplificar a comparação entre eles.