sboxUv2.algorithms package

This module contains the advanced fundamental algorithms that are needed in different parts of sboxU—or can be of independent interest.

More precisely, at this stage, it contains: - the vector space search ([AC:BonPerTia19]), - the affine space search easily derived from said vector space search. - a dedicated data structure that determines the Gauss-Jordan basis of a set of vectors (and thus in particular its rank).

Submodules

sboxUv2.algorithms.cython_functions module

class sboxUv2.algorithms.cython_functions.BinLinearBasis

Bases: object

Stores the Gauss-Jordan basis of a vector space.

For a given vector space, this basis is uniquely defined (it is for example the smallest one if you were to rank all the basis of a vector space in lexicographic order), meaning that testing the equality of the BinLinearBasis of two vector spaces is enough to test their equality.

It provides efficient method to add a new dimension to the span of the corresponding vector space, and to test if an element is the corresponding vector space.

It is a thin wrapper for the cpp_BinLinearBasis C++ class. Check out its documentation for more information.

It only supports vectors of length at most 64 since, under the hood, it stores each vector in a uint64_t.

add_to_span(self, x: int) → bool

Adds a vector to the vector space spanned by this BinLinearBasis. If x is actually already in said space, i.e., if it is spanned by the current basis vectors, then does nothing. Otherwise, builds a new echelonized basis that will contain one more element, this new basis spanning the previous space V as well as x+V.

The echelonizing step means that this function has a run time that is proportional to the current size of the basis.

Parameters:: x – The integer representing the binary vector to add to the vector space corresponding to this BinLinearBasis.
Returns:: True if adding the element has indeed increased the dimension of the vector space, False if the BinLinearBasis is actually left unchanged by this operation (i.e. if the element was already in the vector space it spans. This output is equal to self.is_in_span(x).

basis_vectors(self) → list[BinWord]: Returns: An ordered list containing the integers corresponding to the vectors forming the basis of the vector space corresponding to this BinLinearBasis instance.

is_in_span(self, x: int) → bool

Tests if a vector is contained in the vector space spanned by this basis.

Parameters:: x – the integer representation of the binary vector to test.
Returns:: True if the binary vector corresponding to x is spanned by the vectors in this basis (or, equivalently, if it is in the vector space that has this basis as its Guss-Jordan basis), False otherwise.

rank(self) → int: Returns: The rank of the set of vectors constituting this BinLinearBasis, i.e., the number of elements in the basis.

span(self) → std_vector[BinWord]

Computes the full vector space spanned by the vectors in the basis.

Returns:: An ordered list of integers, one per vector in the vector space spanned by this basis.

sboxUv2.algorithms.cython_functions.BinLinearMap_from_masks(masks: list[BinWord], N: int, M: int) → BinLinearMap

Builds a BinLinearMap such that the image of the inputs with the lowest MSBs corresponds to a specific basis, and such that the other inputs are mapped to 0.

Parameters:

masks – a list containing the integer representation of the target binary vectors
N – the intended input dimension for the output.
M – the length of the output. It is assumed that the elements in basis are of length at most M.

Returns:

A BinLinearMap L from N bits to M bits such that L(1 << i) = basis[i] for all i < len(basis) and L(1<<i)=0 for all i >= len(basis).

sboxUv2.algorithms.cython_functions.BinLinearMap_from_range_and_image(inputs: list[BinWord], outputs: list[BinWord], N: int, M: int) → BinLinearMap

class sboxUv2.algorithms.cython_functions.F2LinearSystem

Bases: object

Implements a linear system of equation over F_2.

Is optimized for the specific case of large systems where equations are added one by one.

It has two modes, the selection being made during initialization.

If self.echelonize is set to True, then only a set of independent equations is kept in memory, which can lead to a significant memory saving: instead of adding a redundant equation, it simply does nothing. However, it also means that the addition of new equations has a time complexity which is at worst linear in the total number of (independent) equations currently in the system. Since the rank is evaluated in real time (i.e., every time an equation is added), it could be used during the higher level computation itself.

If self.echelonize is set to False, then equations are simply appended to the system without any further consideration. Redundant equations will not be simplified, but each addition is added in a constant (and small) time.

Regardless of the value of self.echelonize, the solutions can only be obtained once the system is fully known.

Under the hood, it uses the cpp_F2LinearSystem C++ class. Checks its documentation for more information.

add_equation(self, variable_indices: list[BinWord]) → bool

Adds an equation to the system corresponding to the sum of the variables with the given indices. If the input is a list [0, 1, 3], then the equation x_0+x_1+x_3=0 is added to the system.

If the system was initialized with echelonize set to True, then the running time is at worst proportional wit the rank of the current system as the system will get re-echelonized. If it was set to False, then the run time is constant.

Parameters:: variable_indices (list) – a list containing the indices of the variables involved in the linear equation to be added to the system.
Returns:: If echelonize is False, then always returns True. Otherwise, returns True if the equation has increased the rank of the system, and False if the new equation was already in the span of the previous equations.

kernel_as_bits(self) → list[bytes]

Solves the system, removes unwanted solutions, and returns a basis of its kernel as list of bytes (each bytes being a list of that contains either 0 or 1.

This method is less space-efficient than kernel_as_bytes because each bit needs a full byte of space; however, it means that the conversion between bits and bytes is done in the C++ world instead of the python world.

Returns:: A list where each entry is of type bytes. The bit with index i then corresponds to the value of x_i, and is simply equal to y[i], where y is one of bytes contained in the output list.

kernel_as_bytes(self) → list[bytes]

Solves the system, removes unwanted solutions, and returns a basis of its kernel as list of bytes (each bytes being essentially a list of 8-bit unsigned char).

Returns:: A list where each entry is of type bytes. The bit with index i then corresponds to the value of x_i, and it can be obtained by computing e.g. (y[i >> 3] >> (i & 0x7)) & 1, where y is one of bytes contained in the output list.

rank(self) → int

The current rank of the system, if it is known. If it isn’t, throws an Exception.

If you want to know the rank of a system that is not echelonized, you need to compute it by hand using the size of the kernel.

Returns:: If self. echelonize is set to True, then returns the current rank of the system. Otherwise, throws an Exception.

remove_solution(self, solution_indices: list[BinWord]) → None

Ensures that the space spanned by the Kernel of the system does not contain a specific value. If said value was indeed in the kernel, then the kernel dimension is decreased. If it actually was not in it, then nothing it will have no impact.

The input describes the indices where the unwanted solution is set to 1. For example, if the input is [0, 1, 3], and if the system has 5 variables, then the solution (1,1,0,1,0) will be removed from the Kernel.

In practice, this does not change the system of equations. Instead, a post-processing step is performed once the kernel is known to remove the (potential) contributions of all the solutions that have been removed using this method.

Parameters:: solution_indices (list) – A list of indices corresponding to the positions set to 1 in the unwanted solution.

sboxUv2.algorithms.cython_functions.complete_basis(basis: list[BinWord], N: int) → list[BinWord]

sboxUv2.algorithms.cython_functions.complete_basis_reversed(basis: list[BinWord], N: int) → list[BinWord]

sboxUv2.algorithms.cython_functions.extract_affine_bases(z, dimension, end_condition='fixed dimension', n_threads=MAX_N_THREADS)

Returns a list containing precisely the GJB basis of each affine space of dimension d contained in the list z, interpreted like a set of binary vectors. The GJB basis consists of an offset (the smallest element in the affine space), and the GJB basis of its linear part.

The inner working of this algorithms are explained in [AC:BonPerTia19].

Parameters:

z – a list of positive integers, each being interpreted as a binary vector.
dimension – the dimension of the vector spaces to search.
end_condition – a string describing what the search is supposed to return. If specified (default is ‘fixed dimension’, then must be either: - ‘fixed dimension’: the function returns exactly one basis for each space of the given dimension, even when the presence of a space of higher dimension causes multiple lower-dimension spaces to appear. - ‘just one’: the function returns the first vector space of the given dimension found. - ‘all dimension’: if a vector space of a dimension higher than dimension is found in z, then its basis (which larger than dimension) will be in the output.

Returns:

A list of list B^i, each list B^i consisting of an offset followed by the GJB basis of a vector space. The corresponding affine space is entirely contained in z.

sboxUv2.algorithms.cython_functions.extract_bases(z, dimension, end_condition='fixed dimension', n_threads=MAX_N_THREADS)

Returns a list containing precisely the GJB basis of each vector space of dimension d contained in the list z, interpreted like a set of binary vectors.

The inner working of this algorithms are explained in [AC:BonPerTia19].

Parameters:

z – a list of positive integers, each being interpreted as a binary vector.
dimension – the dimension of the vector spaces to search.
end_condition – a string describing what the search is supposed to return. If specified (default is ‘fixed dimension’, then must be either: - ‘fixed dimension’: the function returns exactly one basis for each space of the given dimension, even when the presence of a space of higher dimension causes multiple lower-dimension spaces to appear. - ‘just one’: the function returns the first vector space of the given dimension found. - ‘all dimension’: if a vector space of a dimension higher than dimension is found in z, then its basis (which larger than dimension) will be in the output.

Returns:

A list of list B^i, each list B^i corresponding to the GJB basis of a vector space that is entirely contained in z. z is always considered to contain 0, even if it is not in it.

sboxUv2.algorithms.cython_functions.generating_BinLinearMap(basis: list[BinWord], N: int) → BinLinearMap

Builds a full rank BinLinearMap such that the image of the inputs with the lowest MSBs corresponds to a specific basis.

Parameters:

basis – a list containing the integer representation of the binary vectors in the basis
N – the intended input dimension for the output. It is assumed that the elements in basis are of length at most N.

Returns: A BinLinearMap L from N bits to N bits such that L(1 << i) = basis[i] for all i < len(basis) and such that L is a bijection.

sboxUv2.algorithms.cython_functions.generating_BinLinearMap_r(basis: list[BinWord], N: int) → BinLinearMap

sboxUv2.algorithms.cython_functions.is_affine(l: list[BinWord], give_basis=False)