3 ms·

You say that, but if I ask you for some random bits, how do I know you're just not just returning something from a pseudorandom generator with a seed you know?

You say that, but if I ask you for some random bits, how do I know you're just not just returning something from a pseudorandom generator with a seed you know? From the paper: The main challenge for any client receiving randomness from a third-party provider, such as a hardware security module, is to verify that the bits received are truly random and freshly generated. Although certified randomness is not necessary for every use of random numbers, the freshness requirement is especially important in applications such as lotteries and e-games, in which several parties (which may or may not trust each other) need to ensure that a publicly distributed random number was generated on demand. Moreover, certified randomness can be used to verify the position of a dishonest party.

rcxdude 2y ago
There are multiple cryptographic techniques that already exist for this, that allow an arbitrary number of parties to have confidence that a chosen number was indeed random, so long as at least one of them (which can include themselves) is honest.
- magicalhippo 2y ago
  Sure, my point was just that someone saying "trust me bro, my diode is legit" ain't enough. Anyway, some links or keywords to such techniques would be appreciated.
  - lazide 2y ago
    and ‘trust me bro, my quantum chip is legit’ is better?
    - andreareina 2y ago
      Good thing Scott Aaronson's protocol isn't that.
    - magicalhippo 2y ago
      The whole point of the result here, which is an implementation of this[1] paper, is exactly that you don't have to take anyone's word for how good their quantum chip is, but rather that you can yourself verify that it is good. From the referenced paper: The problem is, how do we convince a skeptic over the Internet, with no access to our hardware, that the bits were indeed random, and not secretly backdoored? In our protocol, a classical verifier uses a small random seed to generate n-qubit challenge circuits C1, C2, . . . pseudorandomly. The verifier then submits these Ci’s one at a time, presumably over the standard Internet, to a quantum computer server. For each Ci, the server needs to respond quickly—say, in less than one second—with independent samples s1, . . . , sk from Ci’s output distribution [...]. The verifier, at its leisure, can then calculate the so-called Linear Cross-Entropy Benchmark [...]. If the LXEB scores are sufficiently large, our analysis shows that the verifier can then be confident, under plausible computational assumptions, that there must be Ω(n) bits of genuine min-entropy in the returned samples. In other words: even a quantum computer should need exp(n) time to generate samples that pass the LXEB test and yet are secretly deterministic or nearly-deterministic functions of Ci. Further: Here, we not only complete the analysis that SA announced in 2018: we also prove security, in the random oracle model, against an adversary who could be arbitrarily entangled with the QC. This goes beyond what SA claimed in 2018, and indeed addresses one of the central open problems raised at that time. [1]: https://arxiv.org/abs/2303.01625 https://arxiv.org/abs/2303.01625

rcxdude 2y ago

There are multiple cryptographic techniques that already exist for this, that allow an arbitrary number of parties to have confidence that a chosen number was indeed random, so long as at least one of them (which can include themselves) is honest.

magicalhippo 2y ago
Sure, my point was just that someone saying "trust me bro, my diode is legit" ain't enough. Anyway, some links or keywords to such techniques would be appreciated.
- lazide 2y ago
  and ‘trust me bro, my quantum chip is legit’ is better?
  - andreareina 2y ago
    Good thing Scott Aaronson's protocol isn't that.
  - magicalhippo 2y ago
    The whole point of the result here, which is an implementation of this[1] paper, is exactly that you don't have to take anyone's word for how good their quantum chip is, but rather that you can yourself verify that it is good. From the referenced paper: The problem is, how do we convince a skeptic over the Internet, with no access to our hardware, that the bits were indeed random, and not secretly backdoored? In our protocol, a classical verifier uses a small random seed to generate n-qubit challenge circuits C1, C2, . . . pseudorandomly. The verifier then submits these Ci’s one at a time, presumably over the standard Internet, to a quantum computer server. For each Ci, the server needs to respond quickly—say, in less than one second—with independent samples s1, . . . , sk from Ci’s output distribution [...]. The verifier, at its leisure, can then calculate the so-called Linear Cross-Entropy Benchmark [...]. If the LXEB scores are sufficiently large, our analysis shows that the verifier can then be confident, under plausible computational assumptions, that there must be Ω(n) bits of genuine min-entropy in the returned samples. In other words: even a quantum computer should need exp(n) time to generate samples that pass the LXEB test and yet are secretly deterministic or nearly-deterministic functions of Ci. Further: Here, we not only complete the analysis that SA announced in 2018: we also prove security, in the random oracle model, against an adversary who could be arbitrarily entangled with the QC. This goes beyond what SA claimed in 2018, and indeed addresses one of the central open problems raised at that time. [1]: https://arxiv.org/abs/2303.01625 https://arxiv.org/abs/2303.01625