Systems and methods for practical near-term position verification from certified randomness

A system, comprising:

• a first classical verifier executing a first classical verifier computer program;
• a second classical verifier executing a second classical verifier computer program;
• and
• a quantum prover executing a quantum prover computer program, wherein the quantum prover has access to a quantum computer;
• wherein:
• the first classical verifier computer program and the second classical verifier computer program share a long secret string comprising a secret string, a first random input, a second random input, and a random hash key that identifies one of a plurality of keyed cryptographic hash functions;
• the first classical verifier computer program and the second classical verifier computer program generate a challenge according to a certified randomness protocol using the secret string;
• the first classical verifier computer program and the second classical verifier computer program sample a keyed cryptographic hash function from the plurality of keyed cryptographic hash functions using the random hash key;
• the first classical verifier computer program and the second classical verifier computer program each encrypt the challenge using an output of the keyed cryptographic hash function on a combination of the first random input and the second random input;
• the first classical verifier computer program sends the encrypted challenge, the first random input, and the random hash key to the quantum prover;
• the second classical verifier computer program sends the second random input to the quantum prover computer program;
• the quantum prover computer program receives the encrypted challenge, the first random input and the second random input;
• the quantum prover computer program decrypts the encrypted challenge using the random hash key, the first random input, and the second random input;
• the quantum prover computer program executes a random quantum computation based on the certified randomness protocol and the challenge using the quantum computer;
• the quantum prover computer program sends, a result of the random quantum computation to both the first classical verifier computer program and the second classical verifier computer program;
• the first classical verifier computer program and the second classical verifier computer program determine that the result of the random quantum computation was received within a time threshold;
• the first classical verifier computer program and the second classical verifier computer program compare the result received by the first classical verifier and the result received by the second classical verifier to ensure that they match;
• and
• the first classical verifier computer program and the second classical verifier computer program determine that the result passes the certified randomness protocol using the secret string.