0
$\begingroup$

My question is essentially the same as this one.

The random oracle is a black box that does two things.

  1. Maintain a lookup table for any query that has already been asked.
  2. For all new queries, toss a bunch of coins to obtain a sufficiently long uniformly random bitstring.

As far as I can tell, 1. sounds straightforward. For 2., why not use randomness from a quantum measurement outcome to achieve the coin flip? What part of this black box fails as a valid instantiation of a random oracle?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ How exactly do you maintain a consistent lookup table across many (potentially disconnected) parties while maintaining confidentiality of all the queries made to the oracle? The randomness is not really the issue. $\endgroup$
    – Maeher
    Jun 13 at 15:20
  • $\begingroup$ @Maeher ah I see. I thought that unavailability of randomness was the reason why oracles weren't implementable in practice - your comment has clarified that. Can you also expand on your remark about confidentiality? Why can't the oracle and all queries made to it be publicly available for all parties to see? $\endgroup$
    – user1936752
    Jun 13 at 20:15
  • $\begingroup$ My query was due to this short video here youtube.com/watch?v=1vMyAAuF-jw which claims that our inability to create randomness is the issue. $\endgroup$
    – user1936752
    Jun 13 at 20:19

1 Answer 1

Reset to default
2
$\begingroup$

For 2., why not use randomness from a quantum measurement outcome to achieve the coin flip? What part of this black box fails as a valid instantiation of a random oracle?

Actually, it is precisely equivalent.

This is not a proposed implementation; instead, it is a model of how an ideal Random Oracle works. We never actually do this; instead, this is what we hope an implementation of a Random Oracle is indistinguishable from.

"Toss a bunch of coins" is shorthand for "Pick some random bits; those bits are uniformly distributed and each bit is independent of any other set of random bits". How that are actually done (whether with physical fair coins or through doing Quantum Measurements) is actually immaterial.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the reply. So my background is from the claim made in the video here: youtube.com/watch?v=1vMyAAuF-jw. He says the reason random oracles don't exist is the inability to add randomness. But we do have a source of true randomness in nature so random oracles could exist in practice? $\endgroup$
    – user1936752
    Jun 13 at 20:17
  • 1
    $\begingroup$ @user1936752: the speaker on youtube is exaggerating slightly (but only slightly); we could implement the random oracle precisely as specified in the model, however it would be highly impractical. It is assumed that all parties (including the adversary) has access to this random oracle - would you have a centralized random oracle server that everyone could access? I suppose you could, but in practice, we use a deterministic function (e.g. SHA-3). The youtube speaker didn't consider the centralized Oracle server possibility, probably because it is so wildly impractical compared to, say, SHA3 $\endgroup$
    – poncho
    Jun 13 at 20:27
  • $\begingroup$ Thanks for the comment. Is there any issue with oracle queries being public? One of the other users mentioned confidentiality of oracle queries under my question $\endgroup$
    – user1936752
    Jun 14 at 15:09
  • $\begingroup$ @user1936752: well, I'm pretty sure if the adversary could listen into the Oracle queries that the honest party makes, well, all sorts of bad things could happen... $\endgroup$
    – poncho
    Jun 14 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.