Questions tagged [random-oracles]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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
2answers
193 views

Is true randomness and the physical Church-Turing thesis incompatible?

As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
5
votes
1answer
104 views

Is $UP\not=NP$ with respect to random oracle?

It is shown in An average-case depth hierarchy theorem for Boolean circuits a random oracle makes $PH$ infinite. Is it possible to also show $UP\not=NP\not=\Sigma_2^P\not=\Sigma_3^P\not=\Sigma_4^P\...
3
votes
1answer
112 views

Almost-P and related definitions

I'm pretty sure this has a trivial answer but it's always faster to ask the community :-) I understand that, relative to a random oracle, P=BPP. But this is sometimes phrased via the shorthand "...
6
votes
2answers
161 views

What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

In this article Chang et al. provide a counterexample by giving an oracle $A$ such that $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$. I wanted to know if there are more examples like this.
9
votes
1answer
254 views

Can a random oracle change which TFNP problems are strongly hard-on-average?

I've been thinking about the following question at various times since I saw this question on Cryptography. Question Let $R$ be a TFNP relation. ​ Can a random oracle help P/poly to break $R$ ...
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 ...
7
votes
1answer
179 views

“Largest” class properly contained in PSPACE for a random oracle

Green [1] showed that $PP^{PH}$ is properly contained in $PSPACE$ relative to some oracle. Around the same time, in the famous "voting polynomials" paper [2], it was shown that $PP$ is properly ...
18
votes
2answers
578 views

For a random oracle R, does BPP equal the set of computable languages in P^R?

Well, the title pretty much says it all. The interesting question above was asked by commenter Jay on my blog (see here and here). I'm guessing both that the answer is yes and that there's a ...
6
votes
1answer
348 views

What are alternatives to the random oracle model for modelling hash functions?

I was looking for more realistic alternatives to the ROM for describing hash functions in theoretical proofs. I came across the common reference string model (where hash functions can be modeled as ...
4
votes
0answers
302 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 ...