A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A New Analysis of the Kipnis-Shamir Method Solving the MinRank Problem Uma nova análise do método Kipnis-Shamir resolvendo o problema MinRank

Shuhei NAKAMURA, Yacheng WANG, Yasuhiko IKEMATSU

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

O problema MinRank é investigado como um problema relacionado a ataques de classificação em criptografia multivariada e à decodificação de códigos de classificação na teoria da codificação. O método Kipnis-Shamir é um dos métodos para resolver o problema e, recentemente, progressos significativos foram feitos na sua estimativa de complexidade por Verbel et al. Como este método reduz o problema a um problema MQ, que pede uma solução para um sistema de equações quadráticas, a sua complexidade depende do grau de resolução de um sistema quadrático deduzido do método. Um valor teórico introduzido por Verbel et al. aproxima o grau mínimo de resolução dos sistemas quadráticos no método embora seu valor seja definido sob um certo limite para o sistema considerado. Um sistema quadrático fora de suas limitações geralmente possui um grau de resolução maior, mas a complexidade de resolução nem sempre é maior porque possui um número menor de variáveis ​​​​e equações. Assim, para discutir a melhor complexidade do método Kipnis-Shamir, é necessário um valor teórico para aproximar o grau de resolução de cada sistema quadrático deduzido do método. Um sistema quadrático deduzido do método Kipnis-Shamir sempre possui multigraus, e a complexidade da resolução é influenciada por esta propriedade. Neste estudo, introduzimos um valor teórico definido por tal multigrau e mostramos que ele se aproxima do grau de resolução de cada sistema quadrático. Assim, os sistemas deduzidos do método são comparados e a melhor complexidade é discutida. Como aplicação, para o ataque MinRank utilizando o método Kipnis-Shamir contra o esquema de assinatura multivariada Rainbow, mostramos um caso em que um sistema quadrático deduzido fora da limitação de Verbel et al. Em particular, a estimativa da complexidade do ataque MinRank usando o método KS contra os conjuntos de parâmetros Rainbow I, III e V é reduzida em cerca de 172, 140 e 212 bits, respectivamente, da estimativa de Verbel et al.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.3 pp.203-211
Data de publicação
2023/03/01
Publicitada
2022/09/29
ISSN online
1745-1337
DOI
10.1587/transfun.2022CIP0014
Tipo de Manuscrito
Special Section PAPER (Special Section on Cryptography and Information Security)
Categoria

autores

Shuhei NAKAMURA
  Nihon University
Yacheng WANG
  Corporate Research & Development Center Toshiba
Yasuhiko IKEMATSU
  Kyushu University

Palavra-chave