The maximum XOR differential probability of ADD: $\max_{dc} \mathrm{xdp}^{+}(da, db \rightarrow dc)$ . More...

#include "common.hh"
#include "xdp-add.hh"

Functions
void	max_xdp_add_i (const int i, const uint32_t k, const uint32_t n, double p, WORD_T dd, gsl_matrix A[2][2][2], gsl_vector B[WORD_SIZE+1], gsl_vector C, const WORD_T da, const WORD_T db, WORD_T dd_max, double *p_max, uint32_t A_size)

void	max_xdp_add_bounds (gsl_matrix A[2][2][2], gsl_vector B[WORD_SIZE+1], const WORD_T da, const WORD_T db, WORD_T *dd_max, uint32_t A_size)

double	max_xdp_add (gsl_matrix A[2][2][2], const WORD_T da, const WORD_T db, WORD_T dd_max)

double	max_xdp_add_exper (gsl_matrix A[2][2][2], const WORD_T da, const WORD_T db, WORD_T dc_max)

double	max_xdp_add_lm (WORD_T da, WORD_T db, WORD_T *dc_ret)

Detailed Description

The maximum XOR differential probability of ADD: $\max_{dc} \mathrm{xdp}^{+}(da, db \rightarrow dc)$ .

Author: V.Velichkov, vesse.nosp@m.lin..nosp@m.velic.nosp@m.hkov.nosp@m.@uni..nosp@m.lu

Function Documentation

double max_xdp_add	(	gsl_matrix *	A[2][2][2],
		const WORD_T	da,
		const WORD_T	db,
		WORD_T *	dd_max
	)

Compute the maximum differential probability over all output differences: $\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$ . Complexity c: $O(n) \le c \le O(2^n)$ .

Parameters

A	transition probability matrices.
da	first input difference.
db	second input difference.
dd_max	maximum probability output difference.

Returns: $\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$ .

See Also: max_xdp_add, max_xdp_add_i, max_adp_xor

void max_xdp_add_bounds	(	gsl_matrix *	A[2][2][2],
		gsl_vector *	B[WORD_SIZE+1],
		const WORD_T	da,
		const WORD_T	db,
		WORD_T *	dd_max,
		uint32_t	A_size
	)

Compute an array of bounds that can be used in the computation of the maximum differential probability.

Parameters

A	transition probability matrices.
B	array of size `A_size` rows by (`n` + 1) columns containing upper bounds on the maximum probabilities of all `j` bit differentials $n \ge j \ge 1$ beginning from any state `i:` `A_size` $> i \ge 0$ .
da	first input difference.
db	second input difference.
dd_max	maximum probability output difference.
A_size	size of the square transition probability matrices (equivalently, the number of states of the S-function).

See Also: max_xdp_add_i, max_adp_xor_bounds

double max_xdp_add_exper	(	gsl_matrix *	A[2][2][2],
		const WORD_T	da,
		const WORD_T	db,
		WORD_T *	dc_max
	)

Compute the maximum differential probability by exhaustive search over all output differences. Complexity: $O(2^n)$ .

Parameters

A	transition probability matrices.
da	first input difference.
db	second input difference.
dc_max	maximum probability output difference.

Returns: $\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$ .

See Also: max_xdp_add

void max_xdp_add_i	(	const int	i,
		const uint32_t	k,
		const uint32_t	n,
		double *	p,
		WORD_T *	dd,
		gsl_matrix *	A[2][2][2],
		gsl_vector *	B[WORD_SIZE+1],
		gsl_vector *	C,
		const WORD_T	da,
		const WORD_T	db,
		WORD_T *	dd_max,
		double *	p_max,
		uint32_t	A_size
	)

Compute an upper bound $B[k][i]$ on the maximum probability of the differential $(da[n-1:k], db[n-1:k] \rightarrow dc[n-1:k])$ starting from initial state i of the S-function i.e. $\mathrm{dp}(da[n-1:k],db[n-1:k] \rightarrow dc[n-1:k]) = L A_{n-1} A_{n-2} \ldots A_{k} C^{i}_{k-1}$ , given the upper bounds on the probabilities of the differentials $(da[n-1:j], db[n-1:j] \rightarrow dc[n-1:j])$ for $j = k+1, k+2, \ldots, n-1$ , where $L = [1~1~\ldots~1]$ is a row vector of size A_size and $C^{i}_{k-1}$ is a unit column vector of size A_size with 1 at position $i$ and $C^{i}_{-1} = C$ .

Parameters

i	index of the state of the S-function: `A_size` $> i \ge 0$ .
k	current bit position: $n > k \ge 0$ .
n	word size.
p	the estimated probability at bit position `k`.
dd	output difference.
A	transition probability matrices.
B	array of size `A_size` rows by (`n` + 1) columns containing upper bounds on the maximum probabilities of all `j` bit differentials $n \ge j \ge 1$ beginning from any state `i:` `A_size` $> i \ge 0$ .
C	unit row vector of size `A_size` rows, initialized with 1 at state index `i`.
da	first input difference.
db	second input difference.
dd_max	maximum probability output difference.
p_max	the maximum probability.
A_size	size of the square transition probability matrices (equivalently, the number of states of the S-function).

See Also: max_adp_xor_i

double max_xdp_add_lm	(	WORD_T	da,
		WORD_T	db,
		WORD_T *	dc_ret
	)

The maximum differential probability over all output differences: in linear time as proposed in [Lipmaa, Moriai, FSE 2001]: $\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$ . Complexity c: $O(n)$ .

Parameters

da	first input difference.
db	second input difference.
dc_ret	maximum probability output difference.

Returns: $\mathrm{max}_{dc}~\mathrm{xdp}^{+}(da,db \rightarrow dc)$ .

See Also: max_xdp_add

Functions

Detailed Description

Function Documentation