Does quantum-sourced randomness allow a potential random oracle instantiation?

user1936752

6/13/24, 2:57 PM

My question is essentially the same as this one.

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

Maintain a lookup table for any query that has already been asked.
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?

1 + 3

randomness

random-oracle-model

Maeher

6/13/24, 3:20 PM

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.

user1936752

6/13/24, 8:15 PM

@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?

user1936752

6/13/24, 8:19 PM

My query was due to this short video here https://www.youtube.com/watch?v=1vMyAAuF-jw which claims that our inability to create randomness is the issue.

Score:2

Crypto

poncho

6/13/24, 4:58 PM

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.

+ 4

user1936752

6/13/24, 8:17 PM

Thanks for the reply. So my background is from the claim made in the video here: https://www.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?

poncho

6/13/24, 8:27 PM

@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

user1936752

6/14/24, 3:09 PM

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

poncho

6/14/24, 3:45 PM

@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...

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Does quantum-sourced randomness allow a potential random oracle instantiation?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.