Certified randomness using a trapped-ion quantum processor | Hacker News Reader

Certified randomness using a trapped-ion quantum processor

nature.com

27 pointswahsmail19 comments

I have a reverse biased OA91 germanium diode here that cost $0.05 and does the same thing. Has the desperate search for applications of "quantum computing" really come to this?

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.

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.

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.

and ‘trust me bro, my quantum chip is legit’ is better?

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

Good thing Scott Aaronson's protocol isn't that.

Not the same thing, this is about verifiable randomness, where you can't manipulate it, though I think you can still generate multiple runs and only submit the one that works for your ends, you can't finegrained manipulate it.

Indeed, the business model of selling a worse and much more expensive version of something that everybody already has [1] is a bit questionable.

[1] https://en.wikipedia.org/wiki/RDRAND

Counterpoint to your comment: Mechanical calculators were cheaper, more reliable, and well understood. Early computers were bulky, expensive and needed a skilled team to operate, until they transformed everything. Quantum tech may follow the same arc.

Love the "may". Why should we assume it will follow a similar trajectory? For one, the bulky computers of olde were already useful. These machines were not built on the vague promise of future usefulness. Second, even theoretically, quantum computers are not that useful. Take a look at [1] and tell me what you think is useful enough to justify 200 billions in investments.

[1] https://en.wikipedia.org/wiki/Quantum_algorithm?wprov=sfla1

Can you share any circuits or techniques (or reliable pointers) for getting the randomness from the noise shout accidentally biasing the results? I’m needing a good random source for a side- interest of mine.

Sure here's something very simple take [0].

This is for RF, and you probably need less bandwidth. Search on Robert Penfold hobby designs for noise generators for audio too. In practice you'll need to do a few things to get a good digital noise source with proper entropy.

1) Shield it! What you want is noise from the bandgap transition not from your local radio station or ambient "cosmic" noise.

2) Thermally stabilise it.

3) Convert to a digital stream. A Schmitt gate with properly set hysteresis to get clean edge transitions and a 1-bit sampling circuit.

The whole design should cost you a few bucks and be buildable in hours. Maybe use a USB audio dongle (minus the DC block capacitors) as an easy-in for your digital side.

[0] https://www.radiohobbyist.org/blog/?p=1884

[1] https://www.geeksforgeeks.org/schmitt-trigger/

4) add a Von Neumann extractor (or similar/better) in the digital domain for good measure (pseudocode):

  function von_neumann_extractor(input_bits):
    output_bits = []
    i = 0
    
    while i + 1 < length(input_bits):
      bit1 = input_bits[i]
      bit2 = input_bits[i + 1]
  
      if bit1 != bit2:
        output_bits.append(bit1)
      # else: discard the pair
  
      i += 2
  
    return output_bits

See: https://en.m.wikipedia.org/wiki/Randomness_extractor

Thanks! This will definitely be useful as I anticipate that setting the threshold for the Schmidt trigger will be imperfect.

Thank you! This will be useful!

I usually settle on this design: https://hackaday.io/project/184643-schrdingers-trigger

The zener design works well, but I find the signal it produces is a little too fast to sample conveniently (it works a bit too well). The two-transistor design produces a similar but slower signal. 2N5551 works nicely.

Then one hex inverter configured as a cheap two-stage inverting amplifier, and another that cleans up the signal into nice 5V with sharp transitions. An optoisolator is another option for the second stage, but adds another part to the design.

Then I shove a Von Neumann extractor on an Attiny261A (high bandwidth parallel output) or Attiny10 (if just true/false output), I have a little assembly program for that. It takes the signal in, and outputs 8 bits out in parallel, plus one bit that toggles every time a new output is ready. It's not power efficient, I never use this design on a battery, so I never optimized for sleep modes and so on. Instead I optimized to push a little more bandwidth out and try to sample the signal in a balanced way.

Finally, I just grab that with something like a Pi Pico or ESP32 and push it out MQTT. I get something like 100-300 bytes per second depending on the voltage I'm driving the transistors at (anything over 13V gets a little spicy for the first hex inverter, but add a heatsink to it, and it's fine).

I have some KiCAD files for a finished board for all this, also has space for a boost converter (the transistors need 10-12V usually to generate a nice signal). I just finished it yesterday, if you leave me your contact I'm happy to let you know when I publish it. Otherwise, just check here in like 1-2 weeks and I'll probably have it up by then: https://github.com/seanboyce/

Perfect! Thank you! I’ll check the GitHub in a while.

It's a long weekend over here, so I managed to load up the code, BOM, KiCAD files, production files, and assembly instructions. Also some scope trace images of what the signal should look like at different stages:

https://github.com/seanboyce/TRNG

I didn't specifically design this for other people to easily replicate, but should not be too hard with some solder paste and a hot air rework station.

The assembly code is extensively commented-- I realize AVR assembly is not most people's native dialect, haha.

I hope you enjoy!

Reply on news.ycombinator.com