Existem algoritmos de criptografia de chaves públicas que são comprovadamente NP-difíceis de derrota? [fechadas]

Question

deve quântico prático de computação se tornar uma realidade, eu estou querendo saber se existem algoritmos criptográficos de chaves públicas que são baseados em problemas NP-completos, em vez de fatoração de inteiros ou logaritmos discretos.

Editar:

Por favor, consulte a "computação quântica na teoria da complexidade computacional" do o artigo wiki em computadores quânticos. Ele ressalta que a classe de computadores problemas quânticos pode responder (BQP ) é acreditado para ser estritamente mais fácil do que NP-completos.

Edit 2:

'Baseado em NP-completo' é uma maneira ruim de expressar o que eu estou interessado.

O que eu pretendia pedir é para um algoritmo de criptografia de chave pública com a propriedade de que qualquer método para quebrar a criptografia também pode ser usado para quebrar o subjacente problema NP-completo. Estes meios de quebrar a criptografia prova P = NP.

Answer 1

Eu estou respondendo a esta discussão antiga, porque é uma pergunta muito comum e importante, e todas as respostas aqui são imprecisos.

A resposta curta para a pergunta original é um inequívoco "não". Não há esquemas de criptografia conhecidos (deixe as chaves públicas-alone) que são baseados em um problema NP-completo (e, portanto, todos eles, sob reduções de tempo polinomial). Alguns são "mais perto" que outros, embora, por isso deixe-me elaborar.

Há muito para esclarecer aqui, então vamos começar com o significado de "baseado em um problema NP-completo." O consenso geral sobre a interpretação disso é: "pode ??ser provada segura em um modelo formal particular, assumindo que não existem algoritmos de tempo polinomial para problemas NP-completos". Para ser ainda mais preciso, vamos supor que nenhum algoritmo existe que sempre resolve um problema NP-completo. Esta é uma suposição muito seguro, porque isso é uma coisa muito difícil para um algoritmo para fazer - é aparentemente muito mais fácil para chegar a um algoritmo que resolve casos aleatórios do problema com boa probabilidade

.

Não há esquemas de criptografia têm tal prova um, no entanto. Se você olhar para a literatura, com muito poucas excepções (ver abaixo), os teoremas de segurança leia como o seguinte:

Teorema: Este esquema de criptografia é comprovadamente segura, assumindo que nenhuma polinômio de tempo existe algoritmo para resolver casos aleatórios de algum problema X .

Observe a parte "casos aleatórios". Para um exemplo concreto, podemos assumir que nenhum algoritmo de tempo polinomial existe para fatorar o produto de dois números primos aleatório n bits com alguma boa probabilidade. Isto é muito diferente (menos seguro) a partir assumindo que nenhum algoritmo de tempo polinomial existe para sempre factoring todas produtos de dois números primos aleatório n bits.

Os "casos aleatórios" versus "piores exemplos de casos" a questão é o que é tropeçar vários respondedores acima. Os esquemas de criptografia McEliece tipo são baseados em uma versão muito especial aleatória de decodificação de códigos lineares - e não sobre a versão atual de pior caso que é NP-completos

.

Empurrando além desta questão "casos aleatórios" exigiu uma pesquisa profunda e bela em ciência da computação teórica. Começando com o trabalho de Miklós Ajtai, descobrimos algoritmos criptográficos, onde a suposição de segurança é uma "pior caso" (mais seguro) pressuposto em vez de uma forma aleatória caso um. Infelizmente, as piores hipóteses de caso são para problemas que não são conhecidos por ser NP completo, e alguma evidência teórica sugere que não podemos adaptá-los a usar os problemas NP-completos. Para o interessado, olhar para cima "criptografia baseada rede".

Answer 2

Alguns sistemas criptográficos baseados em problemas NP-difíceis foram propostas (como a Merkle-Hellman cryptosystem baseado no problema de soma subconjunto, eo Naccache-Stern mochila cryptosystem base sobre o problema da mochila), mas eles foram todos quebrados. Por que é isso? Palestra 16 de Grandes Idéias em Teórica Ciência da Computação diz algo sobre isso, que eu acho que você deve tomar como definitivo. O que ele diz é o seguinte:

Idealmente, gostaríamos de construir um [criptográfica Pseudorandom Generator] ou sistema de criptografia cuja segurança foi baseado em um problema NP-completo. Infelizmente, os problemas NP-completos são sempre sobre o pior caso. Em criptografia, isso se traduziria em uma declaração como “não existe a mensagem de que é difícil de decodificar”, que não é uma boa garantia para um sistema criptográfico! A mensagem deve ser difícil de decifrar com probabilidade esmagadora. Apesar de décadas de esforço, de maneira nenhuma foi ainda descoberto se relacionar pior caso para caso média para problemas NP-completos. E é por isso que, se quisermos cryptosystems computacionalmente seguras, precisamos fazer suposições mais fortes do que P ? NP.

Answer 3

Esta foi uma questão em aberto em 1998:

Sobre a possibilidade de basear Cryptography no pressuposto de que P! = NP por Oded Goldreich, Rehovot Israel, Shafi Goldwasser

A partir do resumo: "Nossa conclusão é que a questão permanece em aberto"

.

-? Eu me pergunto se isso mudou na última década

Editar:

Tanto quanto eu posso dizer a questão ainda está aberta, com o recente progresso em direção a uma resposta de nenhum tal algoritmo existe.

Adi Akavia, Oded Goldreich, Shafi Goldwasser e Dana Moshkovitz publicado este papel na ACM em 2006: em baseando funções one-way em NP-difícil 'Nossos principais conclusões são as seguintes dois resultados negativos'

O site de Stanford Complexidade Zoo é útil na decripting o que esses dois resultados negativos significam.

Answer 4

Enquanto muitas formas foram quebrados, veja Merkle-Hellman , com base em uma forma de NP-completos 'Problema da mochila'.

Answer 5

Malha de criptografia ofertas a mensagem para levar para casa (mais) generalizada que na verdade pode-se projetar sistemas criptográficos onde quebrar o caso médio é tão duro como resolver um problema NP-hard particular (normalmente o Shortest Vector Problema ou o mais próximo Vector Problem).

eu posso recomendar a leitura da seção de introdução de http://eprint.iacr.org/2008/521 e depois perseguindo referências para os sistemas criptográficos.

Além disso, veja as notas de aula em http: //www.cs.ucsd. edu / ~ daniele / CSE207C / e links de perseguição para um livro se você quiser.

Answer 6

Googling para NP-completos e criptografia de chave pública encontra falsos positivos ... que são realmente inseguro. Este cartoonish pdf parece mostrar um algoritmo encyption chave pública baseada na minimium dominante conjunto de problemas . Ler mais ele então admite ter mentido que o algoritmo é seguro ... o problema subjacente é NP-Completo mas de uso no algoritmo de PK não preserva a dificuldade.

Outra Falso positivo Google achado: Cryptanalysis do sistema de criptografia Goldreich-Goldwasser-Halevi de Crypto ' 97 . Do abstrato:

No Crypto '97, Goldreich, Goldwasser e Halevi proposto um sistema de criptografia de chave pública baseada no problema mais próximo vetor em uma estrutura, que é conhecido por ser NP-hard. Mostramos que há uma grande falha no design do sistema que tem duas implicações: qualquer informação vazamentos texto cifrado no texto simples, eo problema de descodificar mensagens cifradas pode ser reduzido a um problema vetor mais próximo especial que é muito mais fácil do que o problema geral .

Answer 7

Há um site que pode ser relevante para os seus interesses:. Cryptography Post-Quantum

Answer 8

Aqui está o meu raciocínio. Corrija-me se eu estiver errado.

(i) `` quebra '' um sistema de criptografia é necessariamente um problema em NP e co-NP. (Quebra de um sistema de encriptação envolve a inversão da função de codificação, que é um-para-um e calculável em tempo polinomial. Assim, dado o texto cifrado, o texto simples é um certificado que podem ser verificadas em tempo polinomial. Assim consultando o texto simples com base na cifrado está em NP e co-NP).

(ii) Se houver um problema NP-hard em NP e co-NP, então NP = co-NP. . (Este problema seria NP-completos e em co-NP Desde qualquer linguagem NP é redutível a esta linguagem co-NP, NP é um subconjunto de co-NP Agora uso simetria:. Qualquer linguagem L em co-NP tem -L (seu complemento) em NP, donde -L é em co-NP --- que é L = --L está em NP.)

(iii) I pensar que é geralmente acreditava que NP! = Co-NP, caso contrário, existem provas polinomial porte que fórmulas booleanas não são satisfiable.

Conclusão:. Conjecturas Complexidade-teóricas implicam que cryptosystems NP-difíceis não existem

(Caso contrário, você tem um problema NP-hard em NP e co-NP, de onde NP = co-NP --- que se acredita ser falsa.)

Answer 9

Enquanto RSA e outros algoritmos criptográficos amplamente utilizados são baseados na dificuldade de fatoração de inteiros (que não é conhecido por ser NP-completo), existem alguns algoritmos de criptografia de chave pública com base em problemas NP-completos também. Uma busca no Google por "chave pública" e "NP-completo" irá revelar alguns deles.

(eu disse incorretamente antes que os computadores quânticos iria acelerar problemas NP-completos, mas isso não é verdade. Eu estou corrigido.)

Answer 10

Como apontado por muitos outros cartazes, é possível criptografia base sobre problemas NP-difíceis ou NP-completos.

No entanto, os métodos comuns para criptografia vão basear-se em matemática difícil (difíceis de crack, que é). A verdade é que é mais fácil de números serialize como uma chave tradicional do que para criar uma seqüência padronizada que resolve um problema NP-hard. Portanto, cripto prática é baseada em problemas matemáticos que ainda não está provado ser NP-hard ou NP-completo (por isso é concebível que alguns desses problemas estão em P).

Em ElGamal ou criptografia RSA, quebrá-lo requer a quebrar o logaritmo discreto, assim que olhar para este wikipedia artigo.

No algoritmo eficiente para calcular logaritmos discretos gerais logbg é conhecido. O algoritmo ingénuo é elevar b para maior e as potências mais elevadas k até que o g desejado é encontrado; este é às vezes chamado multiplicação julgamento. Este algoritmo requer tempo de funcionamento linear no tamanho do grupo G e, portanto, exponencial do número de dígitos no tamanho do grupo. Existe um algoritmo quântico eficiente devido ao Peter Shor no entanto ( http://arxiv.org/abs/ quant-ph / 9508027 ).

Computing logaritmos discretos é aparentemente difícil. Não só não é eficiente algoritmo conhecido para o pior caso, mas a complexidade do caso médio pode ser mostrado para ser pelo menos tão duro como o pior caso usando aleatório auto-redutibilidade.

Ao mesmo tempo, o problema inverso de exponenciação discreta não é (que pode ser calculado utilizando exponenciação eficientemente por quadratura, por exemplo). Esta assimetria é análogo ao que entre fatoração inteiro e multiplicação inteiro. Ambas as assimetrias têm sido exploradas na construção de sistemas de criptografia.

A crença generalizada é que estes são NP-completos, mas talvez não pode ser provada por isso. Note-se que os computadores quânticos podem quebrar a criptografia de forma eficiente!

Answer 11

Uma vez que ninguém realmente respondeu à pergunta que eu tenho para lhe dar a dica: "McEliece". Fazer algumas pesquisas sobre ele. É um algoritmo de criptografia NP-Hard comprovada. Ele precisa ó criptografia (n ^ 2) e o tempo de desencriptação. Ele tem uma chave pública de tamanho O (n ^ 2) também, o que é ruim. Mas há melhorias que reduzem todos esses limites.