Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [random-oracles]

The tag has no usage guidance.

14 questions
Filter by
Sorted by
Tagged with
31 views

### Impossibility of uniform generation in random world

I specify that this is a cross-post from crypto.stackexchange but I didn't get satisfactory answers. I was reading Limits on the provable consequences of one way permutations by Impagliazzo and Rudich ...
• 21
57 views

### Invertible function with hard to find collisions in the Random Oracle Model

This question is inspired by this tweet. I discussed this with some people at my institution when this came out and came to the conclusion that this was probably possible using lattice-based ...
107 views

• 12.9k
243 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 "...
• 4,031
203 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.
• 355
294 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
116 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 ...
203 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 ...
• 4,020
741 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 ...
• 13.8k
473 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 ...
• 325
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 ...