The syzygy distinguisher

This repository contains an experimental implementation of the syzygy distinguisher presented in https://eprint.iacr.org/2024/1193 (see https://github.com/randriam/syzygies for legacy magma code).

Description

We are interested in computing wether a Betti number of the linear strand ($j=i+1$) is zero or not:

$$\beta_{i,j} = \dim_{\mathbb{K}} \text{Tor}_i(M, \mathbb{K})_j \stackrel{?}{=}0 \text{, for }M = \mathcal{C}^{\langle\cdot\rangle} = \bigoplus_{r \ge 0} \mathcal{C}^r$$

To do so, we build a matrix whose kernel is the $r$-th Koszul cohomology space and use block Wiedemann algorithm to check if $dim(ker) = \beta_{r,r+1} >0$ :

$$\bigwedge^{r+1} \mathcal{S_1} \xrightarrow{d} \bigwedge^r \mathcal{S_1} \bigotimes \mathcal{C} \xrightarrow{d'} \bigwedge^{r-1} \mathcal{S_1} \bigotimes \mathcal{C}^{\langle 2 \rangle}$$

Where :

• $\mathbb K= \mathbf{GF}(2)$

• $\mathcal{S}=\mathbb K[x_0, \ldots ,x_k]$

• $\mathcal{S_1}=\langle x_0, \ldots ,x_k \rangle$, the $\mathbb K$-vector space generated by monomials of degree 1

• $\mathcal{C}$ is a binary code of dimension $k$ and length $n$ such that $\mathcal{C}^{\langle 2 \rangle} = \mathbb K^n$

• $r$ is where we expect to distinguish

The procedure is as follows:

• First, we compute the matrix of $d'$ on a basis of a complement of $\mathrm{im}(d)$. The basis we take is:

$$\left( x_{i_1}\wedge \dots \wedge x_{i_r} \otimes c_i|i_1 < \dots < i_r, i \leq i_r \right)$$

• Then, we run block Wiedemann algorithm, if we find a non trivial vector then $\beta_{r,r+1} &gt; 0$ and if we don't find a vector then with high probability $\beta_{r,r+1} = 0$

• The matrix construction is done in python using numpy and numba in order to get good performances.

• The block Wiedemann part is done in C/C++ using cado-nfs/linalg/bwc highly efficient module.

Installation

1. Clone the repository with cado-nfs (submodule):

   git clone --recurse-submodules https://github.com/piperrier/dyztynguysher.git

2. Compile cado-nfs:

   cd cado-nfs; make

3. Add cado-nfs to your path, we will use cado-nfs/linalg/bwc module:

    export PATH="$PATH:/<cado-dir>/build/<hostname>/linalg/bwc"

4. Create a python env with: sage<=10.6, python>=3.12, numpy<=2.2, numba<=0.61 We provide an environment.yml file, with a conda environement called syz.

   conda env create -f environment.yml             # Create the syz environment from file
   conda activate syz                              # Activate syz environment

Usage

• From the dyztynguysher directory, activate the env and start a sage interpreter:

  conda activate syz
  sage

Get an overview

• To see the doc of the class and get an overview of the project:

  load("syz.py")
  help(Instance)

Run the distinguisher

1. On the sage interpreter, load syz.py:

   load("syz.py")

2. Create an instance:

   # Default idir = <dyztynguysher_dir>/instance  
   # Default wdir = /tmp/wdir
   
   h48 = Instance("hamming", 15, 11, 8, "128", "64", "2x2", idir="/nvme/user/instance", wdir="/nvme/user/wdir")
   C = codes.HammingCode(GF(2),4)
   G = C.generator_matrix()
   G = id_on_left(G) # ensure that the generator matrix of the code is identity on the left
   h48.set_code_matrix(G)
   
   print(h48) # Print instance information

3. Run the distinguisher with the conditioning of your choice:

   • RAW
   • RAWPAD
   • RED
   • REDPAD

   h48.construct_and_write_matrix(ConditioningType.RAWPAD)
   h48.run(ConditioningType.RAWPAD)
   h48.check_solution(ConditioningType.RAWPAD)

Draw a matrix

1. Create an instance and write it a bin:

   h48 = Instance("hamming", 15, 11, 8, "128", "64", "2x2")
   C = codes.HammingCode(GF(2),4)
   G = C.generator_matrix()
   h48.set_code_matrix(G)
   h48.construct_and_write_matrix(ConditioningType.RAWPAD)

2. Draw it:

   h48.pretty(ConditioningType.RED, dpi = 400)

Get a sage matrix (to do test)

1. Create an instance and write/collect it:

   h48 = Instance("hamming", 15, 11, 8, "128", "64", "2x2", idir="/nvme/user/instance", wdir="/nvme/user/wdir")
   C = codes.HammingCode(GF(2),4)
   G = C.generator_matrix()
   h48.set_code_matrix(G)
   h48.construct_and_write_matrix(ConditioningType.RAWPAD)
   #h48.construct_and_collect_matrix(ConditioningType.RAWPAD) # h48.S is a ndarray of uint32-ndarray

2. Use the sage_from_bin(path, name, nrows, ncols) or matrix_to_sage(matrix, nrows, cols) to get a sage matrix:

   nrows, ncols = RawPad.get_dim(h48.nrows, h48.ncols)
   matrix = sage_from_bin("Srawpad", h48.idir, nrows, ncols)
   #matrix = matrix_to_sage(h48.S, nrows, ncols)

Create your own conditioning

1. Create a class in conditioning.py

2. Fix all the case match/case in syz.py

Block Wiedemann & Complexity

References for Block wiedemann:

• Don Coppersmith, 1994

• Emmanuel Thomé, 2022: slide 1, slide 2

Complexity:

• krylov+mksol: $(1 + n/m + w/n) \times N$ matrix-times-vector products, where w = 64 when working over GF(2) on a 64 bits processor

• lingen: $(m+n) \times Nlog(N) \times (m + n + log(N))$

Probability of success:

• The matrix shouldn't have a non-zero eigenvalue of high multiplicity

Conditioning & Reduction

1. RAW:
   Construct the whole rectangular matrix ($nrows&lt;ncols$).

   $nrows = k \binom{k}{r} - \binom{k}{r+1}$

   $ncols = n \binom{k}{r-1}$

2. RAWPAD:
   Construct the whole rectangular matrix and pad with random rows to obtain a square matrix.
   With a great probability the random row wont change the kernel of the matrix.

   $nrows = ncols = n \binom{k}{r-1}$

3. RED: Construct the whole reduced matrix

   We delete $r \binom{k}{r}$ rows that have obvious pivots and $k\binom{k}{r-1}$ columns that are all zero.

   $nrows = k \binom{k}{r} - \binom{k}{r+1} - r \binom{k}{r}$

   $ncols = n \binom{k}{r-1} - k\binom{k}{r-1}$

4. REDPAD:
   Construct the whole reduced matrix and pad with random rows to obtain a square matrix.
   With a great probability the random row wont change the kernel of the matrix.

   $nrows = ncols = n \binom{k}{r-1} - k\binom{k}{r-1}$

Reduction ratio:

• We delete $\frac{k}{n}$ of the columns

• We delete $\frac{r}{k}\times\frac{1}{1-1/r}$ of the rows

Potential improvements

• Multithreading when constructing the matrix
• Improve theoretical matrix reduction before construction
• Use MPI option of cado-nfs to run block Wiedemann on multiple computers and reach harder instances:
  • more cpu
  • amortize the high memory cost (lingen: fft → 5 times input size)
• Refactor conditioning
• Take advantage of the recursive structure of the cohomology matrix
• Black box, don't construct the matrix