Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [random-oracles]

The tag has no usage guidance.

6 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4 votes
0 answers

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 ...
Kaveh's user avatar
  • 21.7k
3 votes
0 answers

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 ...
Bolton Bailey's user avatar
3 votes
0 answers

Outputting true with probabiltiy $P(A|B)$ given $P(B), P(B|A)$, and a function which returns true with probability $P(A)$

I have a black-box function which returns true with probability $ P(A) $, that I don't know how to calculate. I receive evidence B, and I want to create a function which returns true with probability $...
Command Master's user avatar
2 votes
0 answers

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 ...
Pur2all's user avatar
  • 21
1 vote
0 answers

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 ...
Anonymous's user avatar
  • 101
1 vote
0 answers

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 ...
user34219's user avatar