Quais idiomas foram bloqueados criptograficamente com êxito?

Uma observação associada à criptografia assimétrica é que algumas funções são (acredita-se que sejam) fáceis de executar em uma direção, mas difíceis de inverter. Além disso, se houver alguma informação de 'alçapão' que permita que a operação inversa seja computada rapidamente, o problema se tornará candidato a um esquema de criptografia de chave pública.

Os problemas clássicos de alçapões, tornados famosos pela RSA, incluem o problema de fatoração e o problema de log discreto. Na mesma época em que a RSA foi publicada, Rabin inventou um sistema de criptografia de chave pública baseado em encontrar raízes quadradas discretas (isso mais tarde foi provado ser pelo menos tão difícil quanto fatorar).

Outros candidatos surgiram ao longo dos anos. O KNAPSACK (logo após o RSA), a curva elíptica "logaritmos" com parâmetros específicos e os problemas de base mais curta da rede são exemplos de problemas cujos problemas de alçapão são usados ​​em outros esquemas publicados. Também é fácil ver que esses problemas devem residir em algum lugar do NP.

Isso esgota meu conhecimento das funções do alçapão. Também parece esgotar a lista na Wikipedia também.

Espero que possamos obter uma lista wiki da comunidade de idiomas que admitem alçapões e literatura relevante. A lista será útil. As demandas crescentes de criptografia também mudam quais funções do alçapão podem ser a base dos sistemas de criptografia. A explosão do armazenamento em computadores possibilita esquemas com grandes tamanhos de chave. O espectro perpétuo da Computação Quântica invalida esquemas que podem ser quebrados com um oráculo para encontrar subgrupos abelianos ocultos. O sistema de criptografia totalmente homomórfico de Gentry funciona apenas porque descobrimos funções de alçapão que respeitam os homomorfismos.

Estou especialmente interessado em problemas que não são NP-Complete.

É importante distinguir entre funções de alçapão e criptografia de chave pública. Embora as funções de alçapão produzam esquemas de criptografia de chave pública, alguns dos candidatos que você mencionou implicam apenas em criptografia de chave pública e não necessariamente fornecem funções de alçapão. De fato, Gertner, Malkin e Reingold mostram que não há construção de caixa preta de uma função de alçapão a partir de um "predicado de alçapão" (que pode ser pensado como um esquema de criptografia de chave pública de um bit).

Exemplos clássicos de funções de alçapão são as funções RSA e Rabin. Um exemplo clássico de um predicado de alçapão é decidir o módulo de Residuosidade Quadrática como um composto, devido a Goldwasser e Micali. As construções baseadas em log discreto e em rede que você menciona produzem criptografia de chave pública diretamente, sem passar por funções de alçapão.

Abaixo está uma lista (não abrangente) de construções de esquemas de criptografia de chave pública, a maioria das quais não é conhecida por executar funções de alçapão.

• Sistema criptográfico de chave pública El Gamal (incluindo variantes de curva elíptica). A segurança é baseada na suposição Decisional Diffie Hellman. Não passa por funções de alçapão (mas consulte o item Peikert-Waters abaixo para uma função de alçapão cuja segurança é baseada na segurança semântica de El Gamal).

  [Taher El Gamal: um sistema de criptografia de chave pública e um esquema de assinatura baseado em logaritmos discretos. CRYPTO 1984: 10-18]

• Ajtai-Dwork, Regev. A segurança é baseada no SVP exclusivo em treliças. Não se sabe que implica funções de alçapão.

  [Miklós Ajtai, Cynthia Dwork: um sistema de criptografia de chave pública com equivalência de pior caso / caso médio. STOC 1997: 284-293]

  [Oded Regev: Novas construções criptográficas baseadas em treliça. STOC 2003: 407-416]

• Regev, Peikert. A segurança é baseada na dureza de aprender com erros (isso inclui uma redução do SVP). Não se sabe que implica funções de alçapão.

  [Oded Regev: em redes, aprendendo com erros, códigos lineares aleatórios e criptografia. STOC 2005: 84-93]

  [Chris Peikert: sistemas de criptografia de chave pública do pior problema de vetor mais curto: resumo estendido. STOC 2009: 333-342]

• Peikert, Waters. A segurança é baseada na decisão de Diffie Hellman e em problemas de treliça. Conhecido por implicar funções de alçapão (através de funções com alçapão com perdas).

  [Chris Peikert, Brent Waters: funções de alçapão com perdas e suas aplicações. STOC 2008: 187-196]

• Lyubashevsky, Palácio, Segev. A segurança é baseada na soma de subconjuntos. Não se sabe que implica funções de alçapão.

  [Vadim Lyubashevsky, Adriana Palacio, Gil Segev: primitivos criptográficos de chave pública comprovadamente tão seguros quanto a soma de subconjuntos. TCC 2010: 382-400]

• Stehlé, Steinfeld, Tanaka, Xagawa e Lyubashevsky, Peikert, Regev. A segurança é baseada na dureza do anel LWE. A vantagem dessas em relação às propostas anteriores é o tamanho menor da chave. Não se sabe que implica funções de alçapão.

  [Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa: Criptografia eficiente de chave pública com base nas redes ideais. ASIACRYPT 2009: 617-635]

  [Vadim Lyubashevsky, Chris Peikert, Oded Regev: sobre treliças ideais e aprendizado com erros sobre anéis. EUROCRYPT 2010: 1-23]