International Association for Cryptologic Research

International Association
for Cryptologic Research

Advances in Cryptology – ASIACRYPT 2025

Practical Cryptanalysis of Pseudorandom Correlation Generators Based on Quasi-abelian Syndrome Decoding


README

SOFTWARE REQUIREMENTS

This artifact is mostly comprised of either pure Python or SageMath scripts.
We used SageMath version 10.4 (using Python 3.12.5) under Linux, installed
using conda-forge.

To exploit the full power of the attacks described in the companion paper, a
convex optimization solver must be available. CLARABEL and MOSEK are
supported. MOSEK offers higher performance, but requires the user to obtain
a license. At the time of writing, a license for non-commercial use can be
obtained in a few minutes by filling an online form. Note that MOSEK is
multi-threaded so that the indicated running times and memory requirements
may vary with the number of available CPUs.

This section describe how to install SageMath using conda in a fresh conda
environnment. This is mostly taken from [the SageMath installation guide]
(https://doc.sagemath.org/html/en/installation/conda.html).

First, create a fresh conda environment with SageMath:

conda create --name QASD_artifact sage

Then activate it:

conda activate QASD_artifact

Install the extra convex solvers (required to actually attack some
parameters). The cvxpy package includes the CLARABEL open-source convex
solver. It can be installed with:

pip install cvxpy

It is sufficient to demonstrate sparse interpolation by convex optimization
but performance are much less than using the MOSEK commercial software. MOSEK
can be installed with:

pip install mosek

A license file can be obtained (free for academic use) at [this page]
(https://www.mosek.com/products/academic-licenses/). The license file must
be available in one of the default search paths, which includes
$HOME/mosek/. Without license, MOSEK will fail with an error similar to:

mosek.Error: rescode.err_missing_license_file(1008): License cannot be located. The default search path is ':/home/username/mosek/mosek.lic:'.

GUIDED TOUR OF SOURCES

tools and functions

main scripts

test scripts

RUNNING THE UNIT TESTS

The two test scripts generate random sparse polynomials, evaluate them on
random evaluation points, and finally try to interpolate them.

The test_easy.sage script was written to unit-test specific functions that
deal with "easy" sparse interpolation scenarios (with one or two monomials
only). Once SageMath has been installed, running:

sage test_easy.sage

should terminate (in about a minute) without errors. The expected output is:

...
Ran 4 tests in 53.866s

OK

The test_socp.sage script tests sparse interpolation using a convex solver.
Therefore it requires either cvxpy or mosek to be installed. It is capable
of dealing with more monomials. It is also used as a benchmarking tool
(see below).

If cvxpy is installed:
```shell
sage test_socp.sage -q 3 -t 4 -m 200 -n 10 --solver cvxpy

should terminate in a few seconds with `Success --- Solution found`.

If mosek is installed:
```shell
sage test_socp.sage -q 3 -t 4 -m 200 -n 10 --solver mosek

should terminate in a few seconds with Success --- Solution found.

TIME AND SPACE REQUIREMENTS OF CONVEX SOLVERS

Table 4 in the article gives the time and memory required to interpolate
sparse polynomials using convex solvers. Reproducing the table requires at
least 8h and 300GB of memory to run the tests.

We used the /usr/bin/time -v system tool to measure time and memory usage
(beware: this is not the time builtin bash command). The reported numbers
for memory are the Maximum resident set size output.

The following commands reproduce Table 4.

/usr/bin/time -v sage test_socp.sage -q 3 -t 3 -n 20 -m  80 --solver mosek
/usr/bin/time -v sage test_socp.sage -q 3 -t 3 -n 21 -m  84 --solver mosek
/usr/bin/time -v sage test_socp.sage -q 3 -t 3 -n 22 -m  88 --solver mosek

/usr/bin/time -v sage test_socp.sage -q 3 -t 4 -n 20 -m 160 --solver mosek
/usr/bin/time -v sage test_socp.sage -q 3 -t 4 -n 21 -m 168 --solver mosek
/usr/bin/time -v sage test_socp.sage -q 3 -t 4 -n 22 -m 176 --solver mosek

/usr/bin/time -v sage test_socp.sage -q 4 -t 3 -n 11 -m  94 --solver mosek
/usr/bin/time -v sage test_socp.sage -q 4 -t 3 -n 12 -m 102 --solver mosek
/usr/bin/time -v sage test_socp.sage -q 4 -t 3 -n 13 -m 110 --solver mosek

/usr/bin/time -v sage test_socp.sage -q 4 -t 4 -n 11 -m 239 --solver mosek
/usr/bin/time -v sage test_socp.sage -q 4 -t 4 -n 12 -m 264 --solver mosek
/usr/bin/time -v sage test_socp.sage -q 4 -t 4 -n 13 -m 288 --solver mosek

SUCESS PROBABILITY OF THE SPARSE INTERPOLATION

Figure 5 and 7 in the article show the success probability of the sparse interpolation procedure as a function of the number of available random evaluation points.

There is no ready-made script that will reproduce these figures. Moreover, they each contain about 500 data point, and each data point requires a non-negligible computation time. However, any individual point can easily be verified:

Figure 5

sage test_socp.sage -q 4 -t 3 -n 6 -m 35 --ntrials 1000 2>&1 | grep "total successes"     # 2s / trial --- 360MB RAM
...
sage test_socp.sage -q 4 -t 3 -n 10 -m 70 --ntrials 100 2>&1 | grep "total successes"      # 20s / trial --- 2.3GB RAM

Figure 7

sage test_socp.sage -q 4 -t 4 -n 8 -m 120 --ntrials 100 2>&1 | grep "total successes"     # 20s / trial --- 750MB RAM
...
sage test_socp.sage -q 4 -t 4 -n 10 -m 160 --ntrials 100 2>&1 | grep "total successes"      # 60s / trial --- 4.5GB RAM

In all cases, this is supposed to display something like:

2025-10-03 13:59:13,314 [test] Info --- Done. 32 total successes

And the success ratio is relatively easy to obtain by diving the number of successes by the number of trials.

SPLITTING PROBABILITY ESTIMATION BY MONTE-CARLO SAMPLING

A t-sparse polynomial in n variables over GF(q) can be written as a k-variate
polynomial with coefficients in the (n-k) remaining variables, as in
equation4 (4) (with k=1) and equation (5) (with k=2) in the paper. The
multinom.py python script estimates the distribution of the minimum number
of terms among all the $(q-1)^k$ "sub-polynomials".

This is done by randomly sampling a t-term polynomial according to the chosen
sparse distribution (uniform or regular), computing the decomposition for all
possible binomial(n, k) subsets of k variables, and counting how the t
initial terms distribute in the $(q-1)^k$ sub-polynomials.

multinom.py is a pure Python script that does just this. It relies on the
Numpy library for improved performance (experiments were performed with
Python 3.10.14 and Numpy v2.2.4).

It was used to generate Tables 2, 3 and 5 in the paper. The script is
simple-minded: it does 1M random trials, and prints the current empirical
distribution every 100 iterations. The output format is human-readable.

Regenerating the tables in the paper can be done as follows.

Table 2

python3 multinom.py -q 4 -n 13 -t 27 -k 1 --regular
python3 multinom.py -q 4 -n 19 -t 17 -k 1
python3 multinom.py -q 8 -n 10 -t 49 -k 1 --regular

Table 3

python3 multinom.py -q 4 -n 16 -t 42 -k 2 
python3 multinom.py -q 4 -n 19 -t 81 -k 2 --regular
python3 multinom.py -q 4 -n 17 -t 66 -k 2

Table 5

python3 multinom.py -q 3 -n 25 -t 152 -k 3 --regular
python3 multinom.py -q 3 -n 30 -t  64 -k 2 --regular
python3 multinom.py -q 4 -n 20 -t  33 -k 1 
python3 multinom.py -q 4 -n 21 -t  27 -k 1 --regular

GENERATION OF QASD INSTANCES

The gen_instances.sage SageMath script generates QASD instances in the
format described in QASD.format and prints them to the standard output.

The --debug option adds the description of the sparse polynomials to the
file (this is helpful to check if parts of the right solution are recovered
later on).

mkdir -p instances

# parameters from the Crypto 2023 paper (with n==25, 30, 35)
sage gen_instances.sage --regular -q 3 -n 25 -c 2 -t 152 > instances/crypto23_2_152.txt            # 20min / 3.5GB RAM
sage gen_instances.sage --regular -q 3 -n 25 -c 4 -t 64  > instances/crypto23_4_64.txt             # 1h / 9.5GB RAM

# parameters from the F4OLEage (Asiacrypt 2024) paper
sage gen_instances.sage --regular -q 4 -n 14 -c 3 -t 27  > instances/f4oleage_aggressive.txt        # 3 min / 540 MB RAM
sage gen_instances.sage --regular -q 4 -n 14 -c 4 -t 27  > instances/f4oleage_conservative.txt      # 4 min / 650 MB RAM

# parameters from the Eurocrypt 2025 paper --- 80 bits of security
sage gen_instances.sage --regular -q 4  -n 14 -c 9 -t 9  > instances/ec25_4_9_9.txt                 # 10min / 1.2GB RAM
sage gen_instances.sage --regular -q 8  -n  8 -c 2 -t 49 > instances/ec25_8_2_49.txt                # 8min /  500MB RAM
sage gen_instances.sage --regular -q 16 -n  6 -c 6 -t 15 > instances/ec25_16_6_15.txt               # 50min / 1.8GB RAM
sage gen_instances.sage           -q 4  -n 16 -c 2 -t 42 > instances/ec25_4_2_42.txt                # 2min /  425MB RAM
sage gen_instances.sage           -q 4  -n 19 -c 5 -t 17 > instances/ec25_4_5_17.txt

# parameters from the Eurocrypt 2025 paper --- 128 bits of security
sage gen_instances.sage --regular -q 4  -n 14 -c 2 -t 81 > instances/ec25_4_2_81.txt
sage gen_instances.sage --regular -q 4  -n 14 -c 5 -t 27 > instances/ec25_4_5_27.txt
sage gen_instances.sage --regular -q 8  -n  8 -c 3 -t 49 > instances/ec25_8_3_49.txt
sage gen_instances.sage --regular -q 16 -n  6 -c 9 -t 15 > instances/ec25_16_9_15.txt
sage gen_instances.sage           -q 4  -n 17 -c 2 -t 66 > instances/ec25_4_2_66.txt
sage gen_instances.sage           -q 4  -n 18 -c 4 -t 33 > instances/ec25_4_4_33.txt

##### toy instances

# Crypto 2023 like
sage gen_instances.sage --regular -q 3 -n 20 -c 2 -t 64  > instances/crypto23_toy.txt

# F4OLEage like
sage gen_instances.sage --regular -q 4 -n 9 -c 2 -t 9    > instances/f4oleage_toy.txt
sage gen_instances.sage --regular -q 4 -n 10 -c 2 -t 14  > instances/f4oleage_semitoy.txt

RUNNING THE ATTACK

Toy instance

The process is first illustrated with an easy toy instance (scaled down version of F4OLEage), where sigma = a1*e1 + e0

First, generate the instance

mkdir -p instances
sage gen_instances.sage --regular -q 4 -n 9 -c 2 -t 9 > instances/f4oleage_toy.txt

The attack is split into several scripts that perform well-delimitated tasks and write their output to auxiliary files. This form of checkpointing was helpful for debugging (if the latter stages fail, then the output of the preliminary steps is still available). The first step consists in finding valid "evaluation points" for the sub-polynomials of e0 and storing them into an auxiliary file with the .out extension.

rm -f instances/f4oleage_toy.txt.out
sage presolve.sage instances/f4oleage_toy.txt > instances/f4oleage_toy.presolve

Then, using this information, the "meat" of the attack consists in trying to interpolate all the sub-polynomials of e0. When a monomial of e0 is identified, it is immediately written out in a file. The solver tries to read this file before attempting any operation and does nothing if the process has completed.

In this toy example, convex solvers are not required, hence the --dumb option.

sage solve.sage --dumb --presolve instances/f4oleage_toy.presolve instances/f4oleage_toy.txt

This is supposed to succeed. At this stage, e0 should have been completely identified. The next step computes the new polynomial sigma' = sigma - e0 = a1*e1. It "peels off" e0 and exposes e1. The process validates e0 in passing.

sage peel.sage instances/f4oleage_toy.txt --poly instances/f4oleage_toy.txt.out > instances/f4oleage_toy_step2.txt

Then we can attack e1:

rm -f instances/f4oleage_toy_step2.txt.out
sage presolve.sage instances/f4oleage_toy_step2.txt > instances/f4oleage_toy_step2.presolve
sage solve.sage --dumb --presolve instances/f4oleage_toy_step2.presolve instances/f4oleage_toy_step2.txt
sage peel.sage instances/f4oleage_toy_step2.txt --poly instances/f4oleage_toy_step2.txt.out

At this stage, e0 and e1 have both been recovered.

q=4, c=2, t=42, n=16, uniform noise

This parameter set has been proposed at Eurocrypt 2025, and is practically broken (without convex solver).

In this case the "presolve" steps dominates the total running time. Because the initial polynomial is split according to TWO variables, the -k 2 options is given to presolve.sage.

mkdir -p instances
sage gen_instances.sage -q 4  -n 16 -c 2 -t 42    > instances/ec25_4_2_42.txt               # 20min /   2GB RAM
sage presolve.sage -k 2 instances/ec25_4_2_42.txt > instances/ec25_4_2_42.presolve          # 20h   / 400MB RAM
sage solve.sage --dumb --presolve instances/ec25_4_2_42.presolve instances/ec25_4_2_42.txt  # quick
sage peel.sage instances/ec25_4_2_42.txt --poly instances/ec25_4_2_42.txt.out > instances/ec25_4_2_42_step2.txt

q=4, c=2, t=66, n=17, uniform noise

This parameter set has been proposed at Eurocrypt 2025, and is practically broken (without convex solver).

mkdir -p instances
sage gen_instances.sage -q 4  -n 17 -c 2 -t 66  > instances/ec25_4_2_66.txt
sage presolve.sage instances/ec25_4_2_66.txt -k 2 > instances/ec25_4_2_66.txt.presolve           # 24h
sage solve.sage --dumb --presolve instances/ec25_4_2_66.txt.presolve instances/ec25_4_2_66.txt
sage peel.sage instances/ec25_4_2_66.txt --poly instances/ec25_4_2_66.txt.out > instances/ec25_4_2_42_step2.txt

Toy instance with convex solvers

This is a scaled-down version the parameters proposed in the F4OLEage article, with uniform noise (Asiacrypt 2024).

mkdir -p instances
rm -f instances/f4oleage_semitoy.txt.out
sage gen_instances.sage -q 4 -n 10 -c 2 -t 24  > instances/f4oleage_semitoy.txt                         # very quick
sage presolve.sage instances/f4oleage_semitoy.txt > instances/f4oleage_semitoy.presolve                 # very quick

Attempting interpolation without using the convex solvers is quite likely to fail (5% success rate):

sage solve.sage --dumb --presolve instances/f4oleage_semitoy.presolve instances/f4oleage_semitoy.txt    # fails quickly

However, using the convex solvers it should succeed.

sage solve.sage --presolve instances/f4oleage_semitoy.presolve instances/f4oleage_semitoy.txt           # 3 min / 3.5GB RAM

The description of e0 should be available in instances/f4oleage_semitoy.txt.out.

F4OLEage / aggressive

This section describes the attack against the proposed parameters. It succeeds with probability 61%.

mkdir -p instances
rm -f instances/f4oleage_aggressive.txt.out
sage gen_instances.sage --regular -q 4 -n 14 -c 3 -t 27  > instances/f4oleage_aggressive.txt        # 3 min / 540 MB RAM
sage presolve.sage instances/f4oleage_aggressive.txt > instances/f4oleage_aggressive.presolve       # 5 min / 250MB RAM

Trying without complex solvers succeeds with probability about 5%.

sage solve.sage --dumb --presolve instances/f4oleage_aggressive.presolve instances/f4oleage_aggressive.txt    # quick

Trying with complex solvers succeeds with probability about 61%. Each of the 33 run of MOSEK takes about 1h on 32 cores and requires about 300GB of RAM. The process can be parallelized, by running all of this commands in parallel.

# X3
sage solve.sage --just-run  9 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 10 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 11 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X4
sage solve.sage --just-run 12 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 13 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 14 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X5
sage solve.sage --just-run 15 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 16 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 17 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X6
sage solve.sage --just-run 18 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 19 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 20 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X7
sage solve.sage --just-run 21 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 22 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 23 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X8
sage solve.sage --just-run 24 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 25 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 26 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X9
sage solve.sage --just-run 27 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 28 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 29 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X10
sage solve.sage --just-run 30 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 31 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 32 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X11
sage solve.sage --just-run 33 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 34 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 35 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X12
sage solve.sage --just-run 36 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 37 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 38 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X13
sage solve.sage --just-run 39 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 40 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 41 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt

# X14
sage solve.sage --just-run 42 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 43 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt
sage solve.sage --just-run 44 --presolve instances/foleage_aggressive.presolve instances/foleage_aggressive.txt