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

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 ). $10^{1000}$

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?

complexity-theory cryptography asymptotics 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:

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.

$2^{1024}$

$G$ $O(|G|)$ $\text{P}=\text{NP}$ $O(\log |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