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

1 . A method, comprising:

sharing, by a first classical verifier and a second classical verifier, 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;

generating, by the first classical verifier and the second classical verifier, a challenge according to a certified randomness protocol using the secret string;

sampling, by the first classical verifier and the second classical verifier, a keyed cryptographic hash function from the plurality of keyed cryptographic hash functions using the random hash key;

encrypting, by each of the first classical verifier and the second classical verifier, the challenge using an output of the keyed cryptographic hash function on a combination of the first random input and the second random input;

sending, by the first classical verifier, the encrypted challenge, the first random input, and the random hash key to a quantum prover;

sending, by the second classical verifier, the second random input to the quantum prover;

receiving, by the quantum prover, the encrypted challenge, the first random input and the second random input;

decrypting, by the quantum prover, the encrypted challenge using the random hash key, the first random input, and the second random input;

executing, by the quantum prover, a random quantum computation based on the certified randomness protocol and the challenge;

sending, by the quantum prover, a result of the random quantum computation to both the first classical verifier and the second classical verifier;

determining, by the first classical verifier and the second classical verifier, that the result of the random quantum computation was received within a time threshold;

comparing, by the first classical verifier and the second classical verifier, the result received by the first classical verifier and the result received by the second classical verifier to ensure that they match; and

determining, by the first classical verifier and the second classical verifier that the result passes the certified randomness protocol using the secret string.

2 . The method of claim 1 , wherein the challenge is generated using a randomness in the secret string, wherein the randomness comprises bits selected from the secret string.

3 . The method of claim 1 , wherein the challenge comprises a description of a quantum circuit.

4 . The method of claim 1 , wherein the keyed cryptographic hash function comprises a salted hash function or a hash-based message authentication code (HMAC).

5 . The method of claim 1 , wherein the time threshold is based on a physical distance between at least one of the first classical verifier and the second classical verifier, and the quantum prover.

6 . The method of claim 1 , wherein the certified randomness protocol comprises a process for generating the challenge, a process for proving certified randomness using the challenge to generate the result, and a process for verifying that the result passes the certified randomness protocol.

7 . The method of claim 1 , further comprising:

generating, by the first classical verifier and the second classical verifier, a second challenge according to the certified randomness protocol using the secret string;

encrypting, by each of the first classical verifier and the second classical verifier, the second challenge using the output of the keyed cryptographic hash function on a combination of the first random input and the second random input;

sending, by the first classical verifier, the second encrypted challenge to the quantum prover, wherein the second encrypted challenge is sent before the result is received;

sending, by the second classical verifier, the second random input to the quantum prover;

receiving, by the quantum prover, the second encrypted challenge and the second random input;

computing, by the quantum prover, the second challenge using the random hash key, the first random input, and the second random input to decrypt the encrypted challenge;

running, by the quantum prover, a certified randomness prover on the second challenge to obtain a second result;

sending, by the quantum prover, the second result to both the first classical verifier and the second classical verifier;

determining, by the first classical verifier and the second classical verifier, that the second result was received within the time threshold;

comparing, by the first classical verifier and the second classical verifier, the second result received by the first classical verifier and the second result received by the second classical verifier to ensure that they match; and

determining, by the first classical verifier and the second classical verifier that the second result passes the certified randomness protocol.

8 . The method of claim 1 , wherein the first classical verifier and the second classical verifier comprises classical electronic devices, and the quantum prover comprises a classical electronic device with access to a quantum computer.

9 . The method of claim 1 , further comprising:

agreeing, by the first classical verifier and the second classical verifier, to a selection of the certified randomness protocol; and

publishing, by the first classical verifier or the second classical verifier, the selected certified randomness protocol to the quantum prover.

10 . The method of claim 1 , wherein the secret string comprises random bits and is known to only the first classical verifier and the second classical verifier.

11 . A system, comprising:

a first classical verifier electronic device;

a second classical verifier electronic device; and

a quantum prover electronic device that is communication with a quantum computer;

wherein:

the first classical verifier electronic device and the second classical verifier electronic device are configured to 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 electronic device and the second classical verifier electronic device are configured to generate a challenge according to a certified randomness protocol using the secret string;

the first classical verifier electronic device and the second classical verifier electronic device are configured to sample a keyed cryptographic hash function from the plurality of keyed cryptographic hash functions using the random hash key;

the first classical verifier electronic device and the second classical verifier electronic device are each configured to 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 electronic device is configured to send the encrypted challenge, the first random input, and the random hash key to the quantum prover electronic device;

the second classical verifier electronic device is configured to send the second random input to the quantum prover electronic device;

the quantum prover electronic device is configured to receive the encrypted challenge, the first random input and the second random input;

the quantum prover electronic device is configured to decrypt the encrypted challenge using the random hash key, the first random input, and the second random input;

the quantum prover electronic device is configured to execute a random quantum computation based on the certified randomness protocol and the challenge using the quantum computer;

the quantum prover electronic device is configured do send, a result of the random quantum computation to both the first classical verifier electronic device and the second classical verifier electronic device;

the first classical verifier electronic device and the second classical verifier electronic device are configured to determine that the result of the random quantum computation was received within a time threshold;

the first classical verifier electronic device and the second classical verifier electronic device are configured to compare the result received by the first classical verifier electronic device and the result received by the second classical verifier electronic device to ensure that they match; and

the first classical verifier electronic device and the second classical verifier electronic device determine that the result passes the certified randomness protocol using the secret string.

12 . The system of claim 11 , wherein the challenge is generated using a randomness in the secret string, wherein the randomness comprises bits selected from the secret string.

13 . The system of claim 11 , wherein the challenge comprises a description of a quantum circuit.

14 . The system of claim 11 , wherein the keyed cryptographic hash function comprises a salted hash function or a hash-based message authentication code (HMAC).

15 . The system of claim 11 , wherein the time threshold is based on a physical distance between at least one of the first classical verifier electronic device and the second classical verifier electronic device, and the quantum prover electronic device.

16 . The system of claim 11 , wherein the certified randomness protocol comprises a process for generating the challenge, a process for proving certified randomness using the challenge to generate the result, and a process for verifying that the result passes the certified randomness protocol.

17 . The system of claim 11 , wherein:

the first classical verifier electronic device and the second classical verifier electronic device are configured to generate a second challenge according to the certified randomness protocol using the secret string;

the first classical verifier electronic device and the second classical verifier electronic device are configured to encrypt the second challenge using the output of the keyed cryptographic hash function on a combination of the first random input and the second random input;

the first classical verifier electronic device is configured to the second encrypted challenge to the quantum prover electronic device, wherein the second encrypted challenge is sent before the result is received;

the second classical verifier electronic device is configured to the second random input to the quantum prover electronic device;

the quantum prover electronic device computer program receives is configured to receive the second encrypted challenge and the second random input;

the quantum prover electronic device computes is configured to compute the second challenge using the random hash key, the first random input, and the second random input to decrypt the encrypted challenge;

the quantum prover electronic device is configured to run the certified randomness prover on the second challenge to obtain a second result;

the quantum prover electronic device is configured to send the second result to both the first classical verifier electronic device and the second classical verifier electronic device;

the first classical verifier electronic device and the second classical verifier electronic device are configured to determine that the second result was received within the time threshold;

the first classical verifier electronic device and the second classical verifier electronic device are configured to compare the second result received by the first classical verifier electronic device and the second result received by the second classical verifier electronic device to ensure that they match; and

the first classical verifier electronic device and the second classical verifier electronic device are configured to determine that the second result passes the certified randomness protocol.

18 . The system of claim 11 , wherein the first classical verifier electronic device and the second classical verifier electronic device comprises classical electronic devices, and the quantum prover electronic device comprises a classical electronic device with access to a quantum computer.

19 . The system of claim 11 , wherein:

the first classical verifier electronic device and the second classical verifier electronic device are configured to agree to a selection of the certified randomness protocol; and

the first classical verifier electronic device or the second classical verifier electronic device is configured to publish the selected certified randomness protocol to the quantum prover.

20 . The system of claim 11 , wherein the secret string comprises random bits and is known to only the first classical verifier electronic device and the second classical verifier electronic device.