Leveled Isogeny Problem with Hints

This repository includes code accompaining the paper "Leveled Isogeny Problems with Hints". We refer to the paper for a more detailed discussion of the code.

The reference sage code from FESTA (https://github.com/FESTA-PKE/FESTA-SageMath) is imported as a submodule. To download it clone this repository with git clone --recurse-submodules https://github.com/KULeuven-COSIC/liph.

To run the combinatorial attack call sage --python -O festa_attack.py in the main directory. The script will generate a random instance of FESTA and publish, together with the public key, some leaked bits of the secret scalars. Using those bits, the secret isogeny is recovered.

Project structure

The folder contain the following code:

• festa_attack.py: full FESTA attack, i.e. given half of the bits of alpha and alpha^-1 recover the secret isogeny
• comb_attack.py: functions to run the combinatioral part of the attack
• /precomp: scripts to prepare the attack by precomputing the square values and the corresponding isogeny; the file FESTA_128.py includes precomputed values for the 128 bit version of FESTA;
• /isolib: isogeny helpers
• '/stats`: statistics to support Section 5.1;
• circ_mat.py: highly unoptimized combinatorial attack for circulant matrices
• Automated_Coppersmith: experiments using Automated Coppersmith