The maximum ADD differential probability of XOR with three inputs, where one of the inputs satisfies a set of ADD differences: $\max_{dd}~\mathrm{adp}^{\oplus}_{\mathrm{SET}}(da, db, \{{dc}_0, {dc}_1, \ldots\} \rightarrow dd)$ . More...

#include "common.hh"
#include "adp-xor3.hh"
#include "max-adp-xor3.hh"
#include "max-adp-xor3-set.hh"

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

double	max_adp_xor3_set (gsl_matrix A[2][2][2][2], const uint32_t da, const uint32_t db, const uint32_t dc[ADP_XOR3_SET_SIZE], double p_dc[ADP_XOR3_SET_SIZE], uint32_t dd_max)

double	max_adp_xor3_set_exper (gsl_matrix A[2][2][2][2], const uint32_t da, const uint32_t db, const uint32_t dc[ADP_XOR3_SET_SIZE], double p_dc[ADP_XOR3_SET_SIZE], uint32_t dd_max)

Detailed Description

The maximum ADD differential probability of XOR with three inputs, where one of the inputs satisfies a set of ADD differences: $\max_{dd}~\mathrm{adp}^{\oplus}_{\mathrm{SET}}(da, db, \{{dc}_0, {dc}_1, \ldots\} \rightarrow dd)$ .

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

Date: 2012-2013

Function Documentation

double max_adp_xor3_set	(	gsl_matrix *	A[2][2][2][2],
		const uint32_t	da,
		const uint32_t	db,
		const uint32_t	dc[ADP_XOR3_SET_SIZE],
		double	p_dc[ADP_XOR3_SET_SIZE],
		uint32_t *	dd_max
	)

Compute the maximum differential probability over all output differences for a set of input differenecs: $\max_{dd} \mathrm{adp}^{\oplus}_{\mathrm{SET}}(da, db, \{{dc}_0, {dc}_1, \ldots\} \rightarrow dd)$ .

Complexity c: $O(n R) \le c \le O(2^{nR})$ , where $R$ is the size of the set of input differences $dc_r$ .

Parameters

A	transition probability matrices.
da	first input difference.
db	second input difference.
dc	set of input difference.
dd_max	maximum probability output difference.
p_dc	probabilities of the set of differentials corresponding to the set of differences (used for testing and debug only).

Returns: $\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}_{\mathrm{SET}}(da, db, \{{dc}_0, {dc}_1, \ldots\} \rightarrow dd)$ .

Algorithm Outline:

Compute the bounds for each of the differences in the set independently using max_adp_xor_bounds i.e. compute $B_{r}[k]$ - the bounds ror the differentials: $\mathrm{dp}(da[n-1:k],db[n-1:k],dc_r[n-1:k] \rightarrow dd[n-1:k])$ corresponding to the r-th input differences $dc_{r}$ in the set.
Compute a single array of bounds $B_{\mathrm{max}}$ as the maximum of the bounds $B_{r}[k]$ at every bit position $0 \le k \le n$ for every S-function state $0 \le i < A_{\mathrm{size}}$ : $B_{\mathrm{max}}[k][i] = \mathrm{max}_{r}~B[k][i],~ 0 \le k \le n,~ 0 \le i < A_{\mathrm{size}}$ .
Call max_adp_xor3_set_i with the array of bounds $B_{\mathrm{max}}[k][i]$ to compute the final maximum probability $\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}_{\mathrm{SET}}$ .

See Also: max_adp_xor3_set_i, max_adp_xor_bounds, max_adp_xor

double max_adp_xor3_set_exper	(	gsl_matrix *	A[2][2][2][2],
		const uint32_t	da,
		const uint32_t	db,
		const uint32_t	dc[ADP_XOR3_SET_SIZE],
		double	p_dc[ADP_XOR3_SET_SIZE],
		uint32_t *	dd_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	set of input difference.
dd_max	maximum probability output difference.
p_dc	probabilities of the set of differentials corresponding to the set of differences; normally set to 1 (used for testing and debug only).

Returns: $\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}_{\mathrm{SET}}(da, db, \{{dc}_0, {dc}_1, \ldots\} \rightarrow dd)$ .

See Also: max_adp_xor3_set

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

Compute an upper bound $B[k][i]$ on the maximum probability of the differential $(da[n-1:k],db[n-1:k],\{dc_0[n-1:k],dc_1[n-1:k],\ldots\} \rightarrow dd[n-1:k])$ , starting from initial state i of the S-function and given the upper bounds on the probabilities of the differentials $(da[n-1:j],db[n-1:j],\{dc_0[n-1:j],dc_1[n-1:j],\ldots\} \rightarrow dd[n-1:j])$ for $j = k+1, k+2, \ldots, n-1$ , where $\{dc_0[n-1:k],dc_1[n-1:k],\ldots\}$ is a finite set of input differences.

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.
dc	set of input differences.
dd_max	maximum probability output difference.
p_max	the maximum probability.

Algorithm Outline:

The bound for the set of differences is computed as the sum of the bounds of the differentials obtained from each of the elements of the set: $B[k][i] = \sum_{r}~B_{r}[k][i]$ , where $B_{r}[k][i]$ is an upper bound on the maximum probability of the differential corresponding to the r-th input difference $dc_{r}$ i.e. $\mathrm{dp}(da[n-1:k],db[n-1:k],dc_r[n-1:k] \rightarrow dd[n-1:k])$ computed as in max_adp_xor_i.

See Also: max_adp_xor3_set, max_adp_xor_i

Functions

Detailed Description

Function Documentation