Exemplos de algoritmos de troca de chaves NP Complete

7

Há várias perguntas na internet (este site e outros; por exemplo, por que não existe um algoritmo de criptografia baseado nos problemas conhecidos do NP-Hard? ) Discutindo a dureza do NP de diferentes sistemas criptográficos assimétricos. Quão bem estabelecidos são os sistemas de compartilhamento de chaves virtuais NP? Ou seja, sistemas para estabelecer uma chave compartilhada (que pode ser usada na criptografia simétrica) com base em problemas que são conhecidos por serem NP rígidos.

Fui solicitado a esta pergunta ao ler sobre https://en.wikipedia.org/wiki/Anshel-Anshel-Goldfeld_key_exchange e me perguntei se poderia ser mostrado NP completo quando implementado em ou , pois eles parecem muito difíceis de satisfazer restrições ou problemas de otimização quadrática à primeira vista. O problema correspondente em que se baseia é o problema de conjugação simultânea.GLn(F2)GLn(R)

Estou ciente de que existe uma distinção importante entre problemas que são meramente NP difíceis no pior caso - mas fáceis na maioria das instâncias aleatórias, em oposição a problemas que são "NP de caso médio" - dado um conjunto de instâncias aleatórias , resolver metade deles ainda é difícil. Eu estaria interessado em ouvir sobre sistemas de compartilhamento de chaves que dependem de qualquer noção de dureza.

complexity-theory np-complete cryptography Alex Meiburg
fonte
11
Algoritmos não podem ser NP-hard; é uma propriedade de problemas .
Raphael
11
Certo, quero dizer a dureza NP de quebrar os protocolos correspondentes. No caso de AAG em seguida, o que corresponde ao simultânea de conjugação Problema (que é conhecido fácil em alguns grupos, tais como o grupo simétrico, e acredita duro com os outros, tais como grupos trança)
Alex Meiburg
Por favor, defina o que você quer dizer com "sistema de compartilhamento de chaves". Você está falando sobre troca de chave pública , por exemplo, Diffie-Hellman e similares?
DW
11
Sim, um protocolo (não necessariamente autenticação) que permite às partes chegar a chave conhecida (idealmente) apenas para o par deles, que pode ser usado em mais comunicações criptografadas por exemplo AES
Alex Meiburg

Respostas:

5

Não há algoritmos criptográficos de chave pública conhecidos que tenham sido comprovadamente difíceis de quebrar. Nenhum. Portanto, não podemos fornecer exemplos, porque nenhum é conhecido.

Responda à sua pergunta original:

A análise em Por que não houve um algoritmo de criptografia baseado nos problemas conhecidos do NP-Hard? também se aplica à troca de chave pública.

A criptografia requer dureza de caso médio. A dureza NP refere-se à dureza do pior caso; não tem noção de distribuição de insumos, probabilidade ou qualquer tipo de "média". A dureza do pior caso não parece implicar dureza do caso médio: há muitos problemas que se acredita serem difíceis no pior caso, mas fáceis no caso médio. Status dos mundos de Impagliazzo? tem algumas dicas sobre esse tópico.

DW
fonte