IQPwn

tl;dr This repository implements the algorithms in this paper for forging quantum data to pass the "test of quantumness" from this paper.

(... slightly embellished for dramatic effect)

---

In [SB2009], a cryptographic protocol is presented for testing the quantum capabilities of an untrusted party. The authors show that under certain cryptographic assumptions, a prover can only pass the interactive test if they are IQP-capable (roughly, if they can run quantum circuits). The code in this repository breaks those assumptions. In particular, this repository contains an implementation of the algorithms described here for extracting the protocol's secret key. It also contains timing code to generate the plots in the paper.

Requirements

• Julia (tested on version 1.2.0)
• The following Julia packages:
  • Primes
  • ArgParse
• Optional: Python 3 + matplotlib for generating timing plots

Breaking the IQP protocol

The authors of [SB2009] posed an online challenge, where the winner would be the first person to generate samples passing their test of quantumness for a specific instance of an IQP circuit they posted online. The code in this repository does exactly that.

Their code, which can be used to generate test instances of the protocol and also contains their challenge program, is located at quantumchallenges.wordpress.com. When compiled and run, that code can be used to generate text files containing input data (called X-programs) for IQP challenges.

The examples directory of this repository contains an sample X-program I generated (see below for key), as well as the challenge X-program and a set of samples that should win the challenge.

You can use the code in this repository in a couple ways. Take the example program I generated, examples/example_q487.xprog.

To generate samples passing the verification test, run

julia IQPwn.jl examples/example_q487.xprog

Note: It appears there is an error in their verification code. It counts samples that are non-orthogonal to the secret vector, instead of orthogonal to it (despite the fact that their paper asks for orthogonal samples). To generate non-orthogonal samples and get satisfying output from their verification procedure, add the --non_orth flag to the command above.

To output the secret key in base64, run

julia IQPwn.jl examples/example_q487.xprog -s base64

To output a binary string instead of base64, use -s bin. The examples directory also contains a Python script b64tobin to convert keys in base64 format to binary.

To print all options, simply run

julia IQPwn.jl --help

If you'd like to verify the samples generated by the commands above, the secret key for examples/example_q487.xprog is:

11001101111000001110001010011111101101111111110111010010111110100001000010010001011011111001111010001101100010111000000011011101010010100010000100110110110001110110011111110110111101010001011101000000010011110001101011010000100010110011110011011

Generating timing plots

This repository also contains code to time and characterize the key extraction, and generate the plots in my paper. To generate the timing data, run

cd benchmark
julia run.jl

(if that's taking too long, the number of iterations and problem sizes can be adjusted in run.jl).

Now that the data has been generated, the plots can be generated by running the following scripts:

python plotcandkeys.py
python plottiming.py

Requires matplotlib.