Os limites inferiores assintóticos são relevantes para a criptografia?

16

Pensa-se que um limite inferior assintótico, como dureza exponencial, implica que um problema é "inerentemente difícil". A criptografia que é "inerentemente difícil" de quebrar é considerada segura.

No entanto, uma assintótica limite inferior não descarta a possibilidade de que uma enorme, mas finita classe de instâncias de problemas são fáceis (ex. Todas as instâncias com tamanho inferior a ).101000

Existe alguma razão para pensar que a criptografia baseada em limites inferiores assintóticos conferisse algum nível específico de segurança? Os especialistas em segurança consideram essas possibilidades ou são simplesmente ignorados?

Um exemplo é o uso de funções de alçapão baseadas na decomposição de grandes números em seus fatores primos. Em algum momento, isso foi considerado inerentemente difícil (acho que exponencial era a conjectura), mas agora muitos acreditam que pode haver um algoritmo polinomial (como existe para o teste de primalidade). Ninguém parece se importar muito com a falta de um limite inferior exponencial.

Eu acredito que outras funções de alçapões foram propostas que são consideradas difíceis de serem usadas em NP (veja a pergunta relacionada ), e algumas podem até ter um limite inferior comprovado. Minha pergunta é mais fundamental: importa qual é o limite inferior assintótico? Caso contrário, a segurança prática de qualquer código criptográfico está relacionada a algum resultado de complexidade assintótica?

Micah Beck
fonte
Bem-vinda! Não é totalmente duplicado, mas muito relacionado: esta questão . Para melhorar a pergunta, dê exemplos concretos onde você acha que o problema é ignorado. Você não quer lutar contra moinhos de vento!
Raphael

Respostas:

2

Tentarei dar uma resposta parcial, já que não estou totalmente ciente de como esse problema é considerado por toda a comunidade criptográfica (talvez repassar no crypto.SE ?).

Eu diria que existem dois "tipos" de criptografadores: Teórico e Prático . Não tentarei diferenciá-los (todo criptografador prático também é um pouco teórico ..), mas direi que, para criptografia teórica - esse problema não importa. Para qualquer parâmetro de segurança, haverá um tamanho de instância que fornecerá esse nível de segurança, e geralmente é com isso que nos preocupamos.

21024

GO(|G|)P=NPO(registro|G|)G

Tocou.
fonte
Essa resposta não é muito satisfatória para mim, talvez porque eu não seja especialista o suficiente para descobrir como ela aborda minha pergunta. É certo que não estudo a teoria da complexidade há 25 anos, mas compreendo muitos dos conceitos subjacentes. Tendo pesquisado algumas das referências vinculadas, parece que as caracterizações de complexidade usadas são assintóticas , então ainda não consigo descobrir como elas podem dar garantias úteis sobre classes finitas de instâncias.
Micah Beck