Oráculo randômico

Em criptografia, um oráculo randômico é um oráculo (uma caixa-preta teórica) que responde para cada consulta única com uma resposta (verdadeiramente) randômica, escolhida uniformemente do seu domínio de respostas. Se uma consulta é repetida, a mesma resposta será dada para cada consulta submetida.

Dizendo em outras palavras, um oráculo randômico é uma função matemática que mapeia cada possível consulta a uma reposta (fixa) randômica do seu domínio de saída.

Oráculos randômicos como abstrações matemáticas foram primeiramente usados em provas criptográticas rigorosas no trabalho de 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 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 oposição a seguridade no modelo padrão [en] de criptografia.

Aplicações

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

↑ ^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
↑ 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
↑ 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
↑ Russell Impagliazzo and Steven Rudich: Limits on the Provable Consequences of One-Way Permutations STOC 1989: pp. 44–61
↑ Canetti, Ran; Goldreich, Oded; Halevi, Shai (2000). «The Random Oracle Methodology, Revisited». doi:10.48550/ARXIV.CS/0010019. Consultado em 30 de outubro de 2023
↑ 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
↑ 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
↑ 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

[bellrog-1] 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/ARXIV.CS/0010019. Consultado em 30 de outubro de 2023

[gentry_ramzan-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

[anotherloook-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]