Pesquisar na Wikipédia Pesquisar Doar Criar uma conta Entrar

Wiki Loves Monuments: Participe do maior concurso fotográfico do mundo enviando suas imagens, e ajude na preservação da nossa cultura. As melhores
fotos serão premiadas!
Mais informação

[ocultar]

Oráculo randômico 12 línguas

Conteúdo ocultar Artigo Discussão Ler Editar Ver histórico Ferramentas Aspeto ocultar

Início Texto
Em criptografia, um oráculo randômico é um oráculo (uma caixa-preta teórica) que responde para cada consulta única com uma
Aplicações
Pequeno
resposta (verdadeiramente) randômica, escolhida uniformemente do seu domínio de respostas. Se uma consulta é repetida, a
Limitações
mesma resposta será dada para cada consulta submetida. Padrão
Cifra ideal
Grande
Ver também Dizendo em outras palavras, um oráculo randômico é uma função matemática que mapeia cada possível consulta a uma reposta
Referências (fixa) randômica do seu domínio de saída. Largura

Oráculos randômicos como abstrações matemáticas foram primeiramente usados em provas criptográticas rigorosas no trabalho de Padrão
Mihir Bellare e Phillip Rogaway (1993).[1] Desde então, eles são usados tipicamente quando as funções criptográficas de hash não Largo
podem ser provadas possuir as propriedades matemáticas necessárias na prova. Um sistema que é provado seguro quando todas
as funções de hash são substituidas por um oráculo randômico é descrito como sendo seguro no modelo de oráculo randômico, em Cor (beta)

oposição a seguridade no modelo padrão [en] de criptografia. Automático

Claro
Aplicações Noite
Na prática, oráculos randômicos são usados como um substituto ideal para funções criptográficas de hash em esquemas onde fortes
premissas sobre aleatoriedade são necessárias para a saída da função de hash. Tal prova geralmente mostra que um sistema ou
protocolo é seguro mostrando que um atacante precisa ter um comportamento impossível do oráculo ou resolver algum problema
matemático acreditamento difícil, para quebrar o protocolo. Nem todas as funções de hash criptográfico requerem oráculos
randômicos: Esquemas que requerem apenas algumas propriedades que tem uma definição no modelo padrão (como resistência a
colisões, resistência de imagem reversa, resistência de segunda imagem reversa, etc) podem, geralmente, ser provados seguros
dentro do modelo padrão (como o Cripto-Sistema de Cramer-Shoup).

Oráculos randômicos foram considerados há muito tempo em estudos de complexidade computacional (como, por exemplo, Bennett
& Gill[2]), e muitos esquemas foram provados seguros usando o modelo de oráculo randômico, por exemplo, OAEP, RSA-FDH e
PSS. Fiat e Shamir (1986)[3] mostraram uma grande aplicação de oráculos randômicos - a remoção de interação dos protocolos para
criação de assinaturas digitais. Impagliazzo e Rudich (1989)[4] mostraram a limitação de oráculos randômicos - que sua existência,
por si, não é suficiente para troca de chaves secretas. Bellare e Rogaway em 1993[1] advogaram seu uso em construções
criptográficas. Nesta definição, o oráculo randômico produz uma string de bits de tamanho infinito que pode ser truncada para o
tamanho desejado.

Quando um oráculo randômico é usado em uma prova de segurança, ele é oferecido a todos os participantes, inclusive os
adversários. Um único oráculo pode ser tratado como vários oráculos, adicionando uma string de bits fixa no início da consulta (por
exemplo, consultas formatadas como "1|x" ou "0|x" pode ser consideradas como chamadas para dois oráculos separados,
similarmente, "00|x", "01|x", "10|x" e "11|x" podem ser usadas para representar chamadas a quatro oráculos separados).

Limitações
Nenhuma função computável por um algoritmo finito pode implementar um oráculos verdadeiramente randômico (que, por definição,
requer uma descrição infinita).

De fato, certas assinaturas artificiais e esquemas de encriptação são conhecidos por provarem segurança no modelo de oráculo
randômico, mas são trivialmente inseguros quando qualquer função real é usada no lugar no oráculo randômico.[5][6] No entanto,
para qualquer protocolo natural, uma prova de segurança no modelo de oráculo randômico é uma forte evidência de segurança
prática do protocolo.[7]

Em geral, se um protocolo é provado seguro, ataques ao protocolo precisam desconsiderar o que foi provado ou quebrar uma das
premissas da prova; por exemplo, se uma prova é baseada na dificuldade de fatoração de inteiros, para quebrar essa premissa, o
atacante precisa descobrir uma algoritmo de fatorização rápido. Em vez disso, para quebrar a premissa do oráculo randômico, o
atacante precisa descobrir alguma propriedade desconhecida ou indesejada na função de hash; para boas funções de hash, para as
quais tais propriedades são acreditadas inexistentes, o protocolo pode ser considerado seguro.

Cifra ideal
Uma cifra ideal é um oráculo de permutação aleatória que é usado no modelo do cifrador de blocos idealizado. Uma permutação
randômica decifra para texto cifrado em um, e apenas um, texto e vice-versa, de modo que haja uma correspondência um-para-um.
Algumas provas criptográficas permitem não só a permutação "direta" para todos os participantes, mas também a permutação
"inversa".

É possível construir um cifrador ideal a partir de um oráculo randômico usando uma Cifra Fiestel de 14 rodadas.[8]

Ver também
Máquina oráculo

Referências
1. ↑ a b Bellare, Mihir; Rogaway, Phillip (1 de dezembro de 1993). «Random oracles are practical: a paradigm for designing efficient
protocols» . New York, NY, USA: Association for Computing Machinery. CCS '93: 62–73. ISBN 978-0-89791-629-5.
doi:10.1145/168588.168596 . Consultado em 30 de outubro de 2023
2. ↑ Bennett, Charles H.; Gill, John (fevereiro de 1981). «Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1» . SIAM
Journal on Computing (em inglês). 10 (1): 96–113. ISSN 0097-5397 . doi:10.1137/0210008 . Consultado em 30 de outubro de 2023
3. ↑ Fiat, Amos; Shamir, Adi (2006). Odlyzko, Andrew M., ed. «How To Prove Yourself: Practical Solutions to Identification and Signature
Problems» . Berlin, Heidelberg: Springer Berlin Heidelberg (em inglês): 186–194. ISBN 978-3-540-18047-0. doi:10.1007/3-540-47721-
7_12 . Consultado em 30 de outubro de 2023
4. ↑ Russell Impagliazzo and Steven Rudich: Limits on the Provable Consequences of One-Way Permutations STOC 1989: pp. 44–61
5. ↑ Canetti, Ran; Goldreich, Oded; Halevi, Shai (2000). «The Random Oracle Methodology, Revisited» . doi:10.48550/[Link]/0010019 .
Consultado em 30 de outubro de 2023
6. ↑ Gentry, Craig; Ramzan, Zulfikar (2004). Lee, Pil Joong, ed. «Eliminating Random Permutation Oracles in the Even-Mansour Cipher» .
Berlin, Heidelberg: Springer. Lecture Notes in Computer Science (em inglês): 32–47. ISBN 978-3-540-30539-2. doi:10.1007/978-3-540-
30539-2_3 . Consultado em 30 de outubro de 2023
7. ↑ Koblitz, Neal; Menezes, Alfred J. (2015). «The Random Oracle Model: A Twenty-Year Retrospective» (PDF). Another Look. Consultado
em 6 de março de 2015
8. ↑ Holenstein, Thomas; Künzler, Robin; Tessaro, Stefano (6 de junho de 2011). «The equivalence of the random oracle model and the ideal
cipher model, revisited» . ACM (em inglês): 89–98. ISBN 978-1-4503-0691-1. doi:10.1145/1993636.1993650 . Consultado em 30 de
outubro de 2023

Categorias: Criptografia Teoria da criptografia

Esta página foi editada pela última vez às 16h21min de 13 de novembro de 2023.

Este texto é disponibilizado nos termos da licença Atribuição-CompartilhaIgual 4.0 Internacional (CC BY-SA 4.0) da Creative Commons; pode estar sujeito a condições adicionais. Para mais detalhes, consulte as condições de utilização.

Política de privacidade Sobre a Wikipédia Avisos gerais Código de conduta Programadores Estatísticas Declaração sobre cookies Versão móvel