Segurança Provável e Reduções

A segurança provável demonstra que quebrar um esquema criptográfico é pelo menos tão difícil quanto resolver um problema considerado intratável, fornecendo uma redução explícita do problema assumidamente difícil para qualquer ataque ao esquema.

Definition

Uma redução de segurança é uma prova que transforma qualquer adversário eficiente que quebra um esquema criptográfico em um algoritmo eficiente que resolve um problema assumido como difícil, mostrando assim que o esquema é seguro, a menos que esse problema seja fácil.

Scope

Este tópico abrange a metodologia baseada em redução das provas criptográficas: a estrutura de uma redução de segurança, o ajuste e a segurança concreta, os estilos de prova baseados em jogos e baseados em simulação, os modelos de oráculo aleatório e padrão, e os limites e críticas da abordagem. Aborda como as garantias de segurança são declaradas e argumentadas. Exclui as suposições de dificuldade específicas e as definições e modelos de adversários, que são tratados em tópicos irmãos.

Core questions

• Como uma redução traduz um ataque a um esquema em uma solução para um problema difícil?
• Qual é a diferença entre provas baseadas em jogos e provas baseadas em simulação?
• O que significa o 'ajuste' de uma redução para os parâmetros de segurança do mundo real?
• O que são os modelos de oráculo aleatório e padrão, e por que o primeiro é controverso?
• Quais são os limites e as armadilhas comuns dos argumentos de segurança provável?

Key concepts

• redução de segurança
• provas baseadas em jogos
• provas baseadas em simulação
• reduções ajustadas vs. frouxas
• segurança concreta
• modelo de oráculo aleatório
• modelo padrão
• vantagem desprezível
• suposição de dificuldade

Key theories

Metodologia de prova reducionista

Para provar a segurança de um esquema, assume-se um adversário que o quebra e constrói-se, usando esse adversário como uma sub-rotina, um algoritmo que resolve o problema difícil subjacente — assim, um ataque bem-sucedido contradiria a suposição de dificuldade.

O modelo de oráculo aleatório

Muitos esquemas eficientes são provados seguros idealizando uma função hash como um oráculo verdadeiramente aleatório; o modelo permite provas para construções práticas, mas é heurístico, já que nenhuma função real é um oráculo aleatório.

Mechanisms

Em uma redução, o provador assume um adversário hipotético que quebra o esquema com uma vantagem não desprezível e constrói um invólucro que incorpora uma instância do problema difícil na visão do adversário, executa o adversário e usa sua saída para resolver o problema. As provas baseadas em jogos progridem através de uma sequência de jogos indistinguíveis do esquema real para um onde o adversário claramente não pode vencer. O ajuste da redução — quanta vantagem e tempo de execução são perdidos — determina os tamanhos de chave necessários para um nível de segurança alvo.

Clinical relevance

A segurança provável é o padrão pelo qual os esquemas criptográficos ganham confiança e padronização: os processos AES, SHA-3 e pós-quânticos do NIST pesaram fortemente as provas de segurança, e protocolos como o TLS 1.3 foram acompanhados por análises reducionistas e verificadas por máquina. Compreender as reduções permite que os profissionais julguem o que uma alegação de segurança garante e não garante, e escolham parâmetros que levem em conta o ajuste da redução.

Evidence & guidelines

A prática moderna favorece provas no modelo padrão sempre que viável e trata as provas de oráculo aleatório como forte evidência heurística, em vez de garantias absolutas. Estruturas assistidas por ferramentas (EasyCrypt, CryptoVerif) fornecem provas verificadas por máquina. A análise de segurança concreta (exata), que quantifica a vantagem do adversário em função dos recursos, é preferida em relação a declarações puramente assintóticas para a definição de parâmetros reais.

History

A metodologia reducionista surgiu com a revolução definicional do início dos anos 1980 e foi sistematizada ao longo dos anos 1990. Bellare e Rogaway introduziram o modelo de oráculo aleatório (1993) para provar a segurança de esquemas práticos, e mais tarde a análise de 'segurança concreta' para quantificar as garantias. O resultado de Canetti, Goldreich e Halevi de 1998, mostrando esquemas seguros no modelo de oráculo aleatório, mas inseguros quando instanciados, acirrou o debate sobre modelos idealizados.

Key figures

• Mihir Bellare
• Phillip Rogaway
• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali

Seminal works

• bellare1993
• katz2020
• goldreich2001

Frequently asked questions

Uma prova de segurança significa que um esquema nunca pode ser quebrado?

Não. Uma prova mostra que quebrar o esquema implica resolver um problema assumido como difícil dentro de um modelo especificado. Se a suposição falhar, o modelo for irrealista ou a implementação desviar-se do esquema analisado, os ataques permanecem possíveis. As provas reduzem, mas não eliminam, o risco.

Por que o modelo de oráculo aleatório é considerado controverso?

Ele modela uma função hash como uma função perfeitamente aleatória, o que nenhuma função concreta realmente é. As provas neste modelo são uma forte evidência e permitem esquemas eficientes, mas existem esquemas (artificiais) seguros no modelo, mas inseguros quando o oráculo é substituído por qualquer hash real, portanto, tais provas são heurísticas.