Quantum evaluation of isogenies

Download and unpack qisog-20181030.tar.gz:

    wget https://quantum.isogeny.org/qisog-20181030.tar.gz
    gunzip qisog-20181030.tar
    tar -xf qisog-20181030.tar
    cd qisog-20181030

The software has been tested under Linux. Times mentioned below are on one core of a 3.5GHz Haswell CPU.

Bit-operation simulator

To run:

    cd bits
    make

This takes 8 minutes. If you don't have clang++, try changing clang++ to g++ in bits/Makefile.

Copies of the expected outputs are in bits/*.exp. In particular, bits/*cost.exp shows various bit-operation counts. For example:

Some outputs also have matching Sage scripts:

    cd bits
    sage pointtest.sage | cmp - pointtest.exp
    sage pointtest3.sage | cmp - pointtest3.exp
    sage elligatortest2.sage | cmp - elligatortest2.exp
    sage csidhtest.sage | cmp - csidhtest.exp
    python crandom.py | sage csidhtest2.sage | cmp - csidhtest2.exp

Internally, the core of the simulator is bits/bit.h, counting the number of NOTs, XORs, ANDs, and ORs. The value method decapsulates the value of a bit.

Mathematical calculations of failure probabilities

Probabilities are computed for the 74 CSIDH-512 primes, with C = 5. These parameters are set at the top of each script. Each output line indicates the number of iterations and the failure probability for that number of iterations. Each failure probability is printed in the form a * 2^(-b), where a (rounded to three digits after the decimal point) is between 0.500 inclusive and 1.000 exclusive, and b is a nonnegative integer.

To compute failure probabilities for iteration1 (each iteration tries to reduce the top nonzero exponent), in a realistic model where each l-isogeny step has failure chance 1/l:

    cd chances
    sage top1exact.sage 210 > top1exact.out.210

Here 210 asks for results for 0, 1, ..., 209 iterations. This takes 7 seconds. Changing 210 to 500 increases the time to 40 seconds.

To compute failure probabilities for iteration2 (each iteration tries to reduce the top nonzero exponent and the next exponent having the same sign), in a realistic model where each l-isogeny step has failure chance 1/l:

    cd chances
    sage top2exact.sage 110 50 upper > top2exact.out.110.50.upper

Here 110 asks for results for 0, 1, ..., 109 iterations; 50 indicates the number of bits of precision in the calculation; upper computes upper bounds on failure probabilities (while lower would have computed lower bounds). This takes 164 seconds. Changing 110 50 to 350 512 increases the time to 6143 seconds, and then changing lower to upper increases the time to 9908 seconds.

To compute failure probabilities for iteration1 (each iteration tries to reduce the top nonzero exponent), in a pessimistic model where each isogeny step has failure chance 1/3:

    cd chances
    sage top1crude.sage 500 > top1crude.out.500

Here 500 asks for results for 0, 1, ..., 499 iterations. This takes 92 seconds. Changing 500 to 1000 increases the time to 790 seconds.

Experiments

The following programs need libsodium installed.

To run 10000000 iteration1 experiments in the realistic model:

    cd chances
    make
    ./top1trials > top1trials.out

This takes 83 seconds.

To run 10000000 iteration2 experiments in the realistic model:

    cd chances
    make
    ./top2trials > top2trials.out

This takes 94 seconds.

To run 10000000 iteration1 experiments in the pessimistic model:

    cd chances
    make
    ./top1ctrials > top1ctrials.out

This takes 72 seconds.


Version: This is version 2018.10.31 of the "Software" web page.