Por que não houve um algoritmo de criptografia baseado nos problemas conhecidos do NP-Hard?

A maior parte da criptografia de hoje, como o RSA, depende da fatoração de número inteiro, que não se acredita ser um problema difícil de NP, mas pertence ao BQP, que o torna vulnerável a computadores quânticos. Eu me pergunto, por que não houve um algoritmo de criptografia baseado em um problema NP-hard conhecido. Parece (pelo menos em teoria) que criaria um algoritmo de criptografia melhor do que um que não está provado ser NP-hard.

Na pior das hipóteses, a dureza dos problemas de NP completo não é suficiente para criptografia. Mesmo que os problemas de NP completos sejam difíceis no pior dos casos ( ), eles ainda podem ser eficientemente solucionáveis ​​no caso médio. A criptografia assume a existência de problemas intratáveis ​​de caso médio no NP. Além disso, provar a existência de problemas graves na NP usando a suposição é um grande problema em aberto.P ≠ N $P \ne NP$$P \ne NP$

Uma excelente leitura é o clássico de Russell Impagliazzo, Uma visão pessoal da complexidade dos casos médios , 1995.

Uma excelente pesquisa é a Complexidade de casos médios de Bogdanov e Trevisan, Fundamentos e Tendências em Teoria da Computação, vol. 2, n. ° 1 (2006) 1–106

Houve.

Um exemplo é o sistema de criptografia McEliece, que se baseia na dureza de decodificar um código linear.

Um segundo exemplo é o NTRUEncrypt, que se baseia no menor problema de vetor que acredito ser conhecido como NP-Hard.

Outro é o sistema de criptografia da mochila Merkle-Hellman, que foi quebrado.

Nota: Não faço idéia se os dois primeiros estão quebrados / quão bons são. Tudo o que sei é que eles existem e consegui que eles fizessem uma pesquisa na web.

Posso pensar em quatro grandes obstáculos que não são totalmente independentes:

• A dureza NP fornece apenas informações sobre a complexidade no limite . Para muitos problemas completos de NP, existem algoritmos que resolvem todas as instâncias de interesse (em um determinado cenário) razoavelmente rápido. Em outras palavras, para qualquer tamanho de problema fixo (por exemplo, uma determinada "chave"), o problema não é necessariamente difícil apenas porque é difícil para o NP.
• A dureza NP considera apenas o pior caso. Muitas, mesmo a maioria de todas as instâncias, podem ser fáceis de resolver com algoritmos existentes. Mesmo se soubéssemos caracterizar as instâncias difíceis (afaik, não sabemos), ainda precisaríamos encontrá-las.
• $2^{n(n-1)}$$n$$n$
• Você precisa de algum tipo de reversibilidade. Por exemplo, qualquer número inteiro é descrito exclusivamente por sua fatoração primária. Imagem que gostaríamos de usar o TSP como método de criptografia; considerando todos os passeios mais curtos, você pode (re) construir o gráfico de onde vieram exclusivamente?

Observe que não tenho experiência em criptografia; estes são meramente resp. algorítmicos. objeções teóricas da complexidade.

A criptografia de chave pública como a conhecemos hoje é construída sobre permutações de alçapão unidirecional , e o alçapão é essencial.

Para que um protocolo seja publicamente seguro, você precisa de uma chave disponível para qualquer pessoa e uma maneira de criptografar uma mensagem usando essa chave. Obviamente, uma vez criptografada, deve ser difícil recuperar a mensagem original sabendo apenas sua cifra e a chave pública: a cifra só deve ser decifrável com algumas informações extras, como sua chave privada.

Com isso em mente, é fácil criar um sistema de criptografia primitivo com base em qualquer permutação unidirecional de alçapão.

1. Alice dá a permutação unidirecional ao público e mantém o alçapão para si mesma.
2. Bob colocou sua entrada na permutação e transmitiu a saída para Alice.
3. Alice usa o alçapão para inverter a permutação com a saída de Bob.

$\mathsf{P} \ne \mathsf{NP}$

$\mathsf{P} \ne \mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NPI}$$\mathsf{NP}$

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}$

Apenas para dar um argumento heurístico, com base na experiência prática.

Quase todas as instâncias, de quase todos os problemas completos de NP, são fáceis de resolver. Existem problemas em que isso não é verdade, mas eles são difíceis de encontrar e é difícil ter certeza de que você tem uma classe dessas.

Isso surgiu na prática várias vezes quando as pessoas tentam escrever geradores aleatórios de problemas para algumas classes famosas de NP-completas, como Programação de Restrições, SAT ou Traveller Salesman. Em algum momento posterior, alguém encontra um método para resolver quase todas as instâncias que o gerador aleatório produz trivialmente. Obviamente, se esse fosse o caso de um sistema de criptografia, estaríamos com sérios problemas!

Os sistemas de criptografia Merkle-Hellman são baseados em problemas de mochila binária (soma do subconjunto).