A bank creating an encryption key, a state drawing a lottery, and a hospital assigning patients to a trial all need the same thing: a random number that nobody in the room, and nobody who built the machine generating random output, could have known in advance. Ordinary computers aren’t optimized for randomness. They follow recipes. Left alone, they cycle, repeat, or leak the rhythm of their own clocks. As a result, modern systems keep asking for fresh and increasing volumes of unpredictability. The challenge is proving, publicly, that supposedly random output was not predetermined.[1]
There are two interleaved problems, one technical, one civic. The technical problem is how to harvest unpredictability. The civic problem is trust. A chip that claims to listen to heat or radioactive decay still sits in a box someone designed. A cloud service that sells random bits still runs software someone can change. A quantum lab that measures a superposition still owns the device that reports the outcome. If the owner already knows the number, or can steer it, a lottery is no longer a game of chance, and the key is no longer secret. Society has long lived with a bargain: inspect the factory, audit the firmware, and hope the operator is honest.
A new paper, Unconditional Certified Randomness without Structure, by Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja, Bhaskar Roberts, Joseph Slote, and Avishay Tal, asks whether that bargain can be renegotiated. Can an ordinary computer user, with no quantum hardware of their own, look at a single answer from an untrusted quantum device and prove that the answer was not predetermined?
In this research, certified randomness means verifiable unpredictability. Someone posts a public puzzle. An untrusted device returns one candidate solution. Anyone who can look up the same puzzle can check whether that solution is valid. If it is, the solution itself is treated as a random string. The guarantee rests on the idea that, among all answers that would have passed the check, the device could not have deterministically chosen one without doing work the proof treats as infeasible.
Older methods asked the physical world to do more of the work, which made them hard to use outside a lab. One approach put two quantum machines in separate rooms and treated their coordinated answers as proof that the numbers were not faked. The catch is that the rooms must stay sealed from each other. If a hidden wire or a leaked signal connects them, the proof collapses. Another used a single machine, but only if it kept talking to the checker over many rounds and never dropped a fragile quantum state in between. Even then, only a trusted third party holding a secret key could confirm that the answers were valid. A third party produced a pile of samples and called them certified, but checking those samples could take a classical computer longer than anyone would wait.
The new protocol is meant to remove those requirements. There is one machine. The puzzle is public. The machine sends back one answer. After that, there is no further conversation. Anyone with an ordinary computer can grade the pair and decide whether the answer counts as certified random.
The puzzle is a search problem introduced by Yamakawa and Zhandry: Picture a long password. Only passwords from a narrow public family are allowed, and each character, in its own place, must pass a public hash test. Almost every candidate fails. A classical computer can ask the hash about only a relatively limited number of strings, making discovery by ordinary search like finding a needle in a haystack.
A quantum computer, in contrast, can query that same public test in superposition: it can ask about many candidate characters at once, then use the family’s design rule to assemble one password that works. It is not hunting down a password it already had in mind. It is sampling one valid password from a space too large to have marked in advance. That sample is the answer it returns.
The system splits the work deliberately: The puzzle is a classical public object, modeled as a random oracle: a hash everyone can query that behaves like an unstructured black box. The untrusted device is a quantum computer that can query that object in superposition. The verifier is a classical computer that checks only two things: that the reported string belongs to the allowed family of passwords, and that each character passes the hash. If both checks succeed, the string is the output. Quantum hardware is the sampler a classical machine cannot cheaply imitate. Classical hardware is the notary anyone can use.
A passing answer cannot have been chosen in advance. If the quantum computer already knew which password it would return, it would have had to check almost every character of that password against the public test, and it is not allowed to perform that many checks. A machine limited to a realistic number of queries almost never inspects any single valid password in full. As a result, a machine that returns a valid password cannot return one it had already picked. The accepted password must be one of many that could have passed.
The quantum computer’s work cannot be watched without disturbing it, so the proof uses a thought experiment instead. After the machine returns a password, imagine changing parts of the public test and asking whether it would still return that same password. A character it never evaluated can be changed without effect. A character it evaluated cannot. The places that cannot be rewritten without changing the answer are the places the machine must have inspected. That inferred inspection is what the rest of the argument uses.
The proof must show that a passing password was not predefined. Earlier arguments either leaned on an unproven conjecture or only handled a cheater who could not keep asking new questions after seeing earlier answers. This paper removes both limits. The researchers shrank the family of allowed passwords so that learning a few characters a cheater inspected is enough to narrow the target to a short list. They also made a “yes” from the public test less common. The honest quantum method still works after that change. The tweak is small: it can be copied from an ordinary public test by reading a few extra bits. Those two changes prove that a passing answer was not predefined, without extra assumptions, even if the cheater asks many follow-up questions.
The proof still holds if the cheater has unlimited computing power, provided it cannot query the public test more than a very high cap allows. As the puzzle grows, an accepted password becomes harder to have guessed in advance. A larger instance of the same construction can raise that unpredictability further.
The proof treats the public test as a black box with no hidden pattern. The quantum computer can learn about it only by asking questions. Real hash functions are built to behave that way, which is why cryptographers often prove a design in this setting before they test a specific hash. In that setting, the paper shows that one machine, one answer, a public check, no extra assumption, and a long string of follow-up questions can hold together.
The thought experiment only identifies a few characters the quantum computer must have inspected. The original Yamakawa–Zhandry passwords were built as if the device would inspect a much larger set. That gap is why the researchers shrank the family of allowed passwords and made a “yes” from the public test less likely. Later work will ask whether the thought experiment can be strengthened so that more inspected characters survive. If it can, the patch may be unnecessary. If it cannot, the next job is to turn the patched puzzle into a public test and a password family that real machines can run.
A lottery commission needs a draw it can be certified under audit. A key-generation ceremony needs a cryptographic key that outside observers can check was not planted. A scientific collaboration needs a shared random seed that does not collapse into an argument over whose hardware to trust. None of those uses needs two sealed laboratories or a secret key held by the checker. They need a puzzle that is hard to solve on an ordinary computer, easy to check in public, and unwilling to accept a favorite chosen in advance.
The demand for numbers nobody could have predicted will keep rising. The paper’s contribution is to show that, in a precise theoretical sense, that demand can be met by a homework assignment a quantum machine can finish, and an ordinary machine can grade, in public, after the fact, without taking the operator’s word for it.
This AI-created article is shared at no charge for educational and informational purposes only.
Red Sky Alliance is a Cyber Threat Analysis and Intelligence Service organization. We provide indicators of compromise information (CTI) via a notification/Tier I analysis service (RedXray) or an analysis service (CTAC). For questions, comments, or assistance, please contact the office directly at 1-844-492-7225 or feedback@redskyalliance.com
- Reporting: https://www.redskyalliance.org/
- Website: https://www.redskyalliance.com/
- LinkedIn: https://www.linkedin.com/company/64265941
Weekly Cyber Intelligence Briefings:
REDSHORTS - Weekly Cyber Intelligence Briefings
https://attendee.gotowebinar.com/register/7855487668891299929
[1] https://six3ro.substack.com/p/true-randomness-checked-in-public
Comments