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

add_to_span(x)
is_in_span(x)
rank()
span()
sboxUv2.algorithms.cython_functions.extract_affine_bases(z, dimension, end_condition='fixed dimension', n_threads=8)

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=8)

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.