Aprimoramento de Protocolo de Identificação Baseado no Problema MQ - Monteiro, Fábio S.; Goya, Denise; Terada, Routo (Anais do Simpósio Brasileiro de Cibersegurança (SBSeg), 2012)
O problema MQ, que consiste em resolver um sistema de equações polinomiais multivariáveis quadráticas sobre um corpo finito, tem atraído a atenção de pesquisadores para o desenvolvimento de sistemas criptográficos de chave pública por ser (1) NP-completo, (2) não ter algoritmo conhecido de tempo polinomial para sua solução nem mesmo no modelo computacional quântico e (3) viabilizar primitivas criptográficas de interesse prático. Em 2011, Sakumoto, Shirai e Hiwatari apresentaram dois novos protocolos de identificação de conhecimento-zero baseados exclusivamente no problema MQ. O protocolo em 3 passos de Sakumoto et al. apresenta probabilidade de personificação de 2/3 em uma rodada. No presente artigo é proposto um protocolo aprimorado que reduz essa probabilidade para 1/2. O resultado é um protocolo que diminui a comunicação total necessária e requer um número menor de iterações para o mesmo nível de segurança.