Criptografia sem premissas - buscando uma visão geral

25

Suponha que e um algoritmo rápido de tempo linear para SAT apareça amanhã. De repente, a RSA fica insegura, grande parte do nosso sistema de comunicação moderno está quebrado e precisamos reconsiderar como manter segredos um do outro.P=NP

Pergunta: Existe uma boa referência única (ou lista curta) para obter uma visão geral do que é possível em criptografia (e no campo aliado da "segurança") sem suposições de intratabilidade? Isso poderia salvar a civilização um dia e também seria bom examinar enquanto isso.

Discussão: A maioria das tarefas criptográficas que estudamos agora (OWFs, PRGs, PKE) é comprovadamente impossível no mundo (um mundo apelidado de "Algoritmica" em um influente ensaio de Impagliazzo), mas algumas coisas permanecem possíveis: comunicação com um bloco único ; compartilhamento secreto distribuído ; recuperação de informações privadas ; e algumas outras coisas legais. (Certos tipos de mecanismos físicos, como caixas trancadas , dispositivos que implementam transferência inconsciente e estados quânticos também podem ser úteis. É claro que sempre existe algum tipo de suposição física sobre quem pode ver quais informações.)P=NP

Pode-se distinguir entre segurança teórica da informação (que funciona contra um adversário computacionalmente ilimitado) e segurança "incondicional" (que pode exigir um adversário limitado, mas ainda mostra segurança sem suposições não comprovadas). Estou mais interessado no caso da teoria teórica.

Para começar, aqui está uma bibliografia de segurança teórica da informação (que, para meus propósitos, é incontrolavelmente longa e díspar).

Andy Drucker
fonte
Boa pergunta, essa não é realmente uma resposta, mas pode ser interessante. Alfred Menezes e Neal Koblitz têm uma boa série de artigos sobre "Another Look" , onde eles fazem algumas perguntas semelhantes às suas, mas também abordam toda a direção dos "modelos de segurança". Eu discuti brevemente nesta resposta , mas não tenho certeza se isso é muito aplicado a uma abordagem.
Artem Kaznatcheev
3
Eu suspeitaria que alguém possa usar esse algoritmo SAT para encontrar alternativas aos PKCs atuais e aos sistemas incondicionalmente seguros.
T ....
Observe que o RSA não é NP-Complete, portanto, exigir P = NP para fatorar pode ser um exagero.
user834
uma grande parte de dobradiças de criptografia modernos sobre suposições intratabilidade não de simplificação / conveniência, mas porque há melhores resultados / limites prováveis estão disponíveis a partir teoria da complexidade (esp média complexidade caso) ... ver também crypto.se
vzn
3
Aqui está uma pesquisa realizada pela Ueli Maurer que, embora um pouco datada, é bastante informativo: ftp.inf.ethz.ch/pub/crypto/publications/Maurer99.pdf

Respostas:

16

As frases-chave que você provavelmente está procurando são "criptografia teórica da informação" e "criptografia quântica". A pesquisa na literatura sobre esses tópicos resultará em muitos trabalhos do tipo que você está procurando. Alguns exemplos são destacados abaixo:

  • Para confidencialidade: o teclado único, o canal de escuta Wyner, compartilhamento secreto, troca de chaves quânticas etc.

  • Para integridade e autenticação: funções de hash universais.

  • Para o anonimato: comunicação anônima (por exemplo, redes DC, esquemas baseados em cebola, redes P2P baseadas na mistura rápida de passeios aleatórios), protocolos de limite de distância.

  • Para segurança baseada em suposições físicas: PUFs (funções fisicamente não clonáveis), códigos de integridade (Capkun et al.), Criptografia quântica, segurança usando TPMs ou hardware resistente a violações.

Existem muitos artigos sobre esses tópicos; muitos para resumir todos os resultados na literatura.

DW
fonte
Obrigado DW, eu sei que é muito terreno para resumir em uma resposta; Espero encontrar livros ou pesquisas úteis.
Andy Drucker
@ AndyDrucker, minha recomendação seria ler os documentos seminais ou de ponta sobre os tópicos de seu interesse. Não sei se você encontrará um livro que cubra todo o trabalho nessa área (alguns dos quais ocorreram nos últimos 5 a 10 anos). Mesmo que você tenha sorte e descubra algum livro, ele já começará a ficar para trás da literatura de pesquisa mais recente quando aparecer nas prateleiras.
DW
2
Eu nem aspiro ao estado da arte. Não existe um livro realmente atualizado para qualquer área do TCS; ainda assim, ainda é possível pegar os livros de Goldreich e orientar-se para os resultados e conceitos fundamentais da criptografia baseada na complexidade. Gostaria de saber se algo semelhante havia aparecido para o lado da teoria da informação.
Andy Drucker
4

Essa é uma pergunta bastante complexa, pois realmente não temos uma boa visão geral da área. Em parte, isso se deve ao fato de a teoria da informação e a comunidade de criptografia terem trabalhado em tópicos semelhantes sem realmente interagir o suficiente entre si. Muitos bons pontos foram dados acima. Gostaria apenas de acrescentar algumas observações extras:

  • Tivemos um grande número de trabalhos lidando com o problema do contrato de chave secreta (e comunicação segura) com uma determinada configuração. Aqui, uma configuração significa, por exemplo, que as partes no sistema (digamos Alice, Bob e Eve adversária) compartilham algumas informações correlatas provenientes de uma distribuição de probabilidade tripartida. Uma configuração alternativa pode consistir em canais ruidosos (por exemplo, Alice pode enviar informações a Bob e Eve através de canais ruidosos). Além disso, Alice e Bob estão conectados através de um canal de comunicação (que pode ou não ser autenticado). Essa linha de trabalho começou com Aaron Wyner nos anos 70, que introduziu o modelo de canal Wiretap, e foi posteriormente limpo por Maurer e outros nos anos 90. Além disso, muitas técnicas nessa área (amplificação de privacidade, reconciliação de informações) acabou sendo usada na configuração Quantum Key-Distribution (QKD). Uma boa quantidade de trabalho está sendo feita aqui até hoje, por exemplo, em áreas relacionadas, como extratores não maleáveis, etc. O modelo de armazenamento limitado também é uma configuração diferente da anterior, mas usa técnicas semelhantes e possui características semelhantes. objetivos.

  • Além do compartilhamento secreto, você encontrará vários trabalhos sobre computação multipartidária (MPC), teoricamente segura. Em particular, a linha de trabalhos iniciados pelo protocolo BGW é completamente teórica da informação.

  • Além disso, não sei até que ponto o escopo da pergunta vai: Se, por exemplo, P = NP realmente se mantém, mas podemos de alguma forma justificar a presença de um oráculo aleatório no céu, a criptografia simétrica ainda é possível. Às vezes, esses modelos são realmente usados ​​para provar a segurança de certas construções criptográficas (como funções de hash ou cifras de bloco), e as técnicas são completamente teóricas da informação.

  • As técnicas teóricas da informação em criptografia também surgem frequentemente como uma ferramenta intermediária nos resultados teóricos da complexidade, mas acho que isso está além do escopo da questão. (Veja o trabalho de Maurer em sistemas aleatórios e em amplificação indistinguível como um exemplo desse tipo de trabalho.)

Stefano Tessaro
fonte
"podemos de alguma forma justificar a presença de um oráculo aleatório no céu" o que você está falando exatamente aqui? Como a criptografia de chave 'pública' simétrica é possível aqui?
T ....
1
@JA Acredito que ele se refira ao modelo de oráculo aleatório de Bellare e Rogaway; veja, por exemplo, cseweb.ucsd.edu/~mihir/papers/ro.html . Este modelo é uma heurística, muitas vezes um útil, mas não há boas razões para ser cético: arxiv.org/abs/cs/0010019
Sasho Nikolov
ic .. o que exatamente acontece aqui? você tem uma idéia em um nível concreto? Todos os esquemas de chave simétrica da informação que vi são baseados na extração de informações comuns de correlatos e, portanto, possivelmente não podem ser transformados em uma versão de chave pública. Existe aqui uma idéia fundamental que permita uma solução viável de criptografia de chave pública que seja teoricamente segura?
T ....
2
Deixe-me elaborar: No modelo aleatório do Oracle, onde todas as partes têm acesso a um RO aleatório, as partes honestas que possuem uma chave secreta SK podem criptografar uma mensagem M com segurança como (R, M + RO (SK || R)), onde R é a aleatoriedade da criptografia (e é gerado recentemente em cada criptografia), + denota xor bit a bit (aqui suponha que o comprimento da saída do RO seja igual ao comprimento da mensagem). A segurança desse esquema depende apenas do oráculo aleatório ser aleatório. Por outro lado, é conhecido pelo trabalho de Impagliazzo e Rudich que a criptografia de chave pública não é possível no modelo de oráculo aleatório.
Stefano Tessaro
3

Alguns grupos de pesquisa na Europa adotaram essa linha de pesquisa; mais especificamente, por causa do meu interesse pela teoria da informação, me deparei com o trabalho de Ueli Maurer e sua escola, que é significativa do ponto de vista puramente teórico da informação (com o qual estou mais familiarizado) e também oferece algumas abordagens práticas da informação. segurança teórica.

Relacionados à linha de trabalho acima, alguns lugares que você talvez queira considerar são a tese de doutorado de Christian Cachin e também Renato Renner (mais quântico).

Obviamente, existe uma abordagem totalmente diferente com palavras-chave, incluindo BB84, Preskill-Shor, Artur Ekert, etc.

O acima exposto, é claro, reflete apenas minha experiência limitada, e certamente existem muitas outras abordagens e linhas de trabalho interessantes.

Mohammad Bavarian
fonte