Questions tagged [random-oracles]

The tag has no usage guidance.

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
303 views

A natural result that relativized to a random oracle is true with probability 1/2

There are several well known results regarding random oracles, e.g. $\mathsf{IP}^A \neq \mathsf{PSpace}^A$ for almost all oracles. Are there any known natural examples where a similar statement ...
1
vote
0answers
42 views

How can ORAMs be secure in the random oracle model with O(1) protected words of O(lg n) bits each?

This post assumes some knowledge about ORAMs on the reader's part. Very roughly, ORAMs are ways in which one can simulate a generic RAM program for $n$ steps in such a way that the memory access ...
1
vote
0answers
109 views

The meaning of separations in cryptography

From the paper of Impagliazzo and Rudich "Limits on the Provable Consequences of One-Way Permutations": We provide strong evidence that it will be difficult to prove that secure secret agreement is ...