# Finding maximal $n$-affine subset

We obtained $$l$$ vectors $$B_i$$ of $$c$$ bits $$b_{i,j}$$. These are an altered form of vectors $$A_i$$ where the last $$n$$ bits of each $$A_i$$ are an affine function of the other bits of that $$A_i$$.

We want an efficient algorithm yielding a maximal subset of vectors $$B_i$$ such that the last $$n$$ bits of each $$B_i$$ in the subset are an affine function of the other bits of that $$B_i$$.

By affine function, we mean there exist constant $$K$$ and $$c-n$$ constants $$K_j$$, each $$n$$-bit, such that for each $$i\in[0,l($$, the last $$n$$ bits of $$A_i$$ are $$K\oplus\left(\displaystyle\bigoplus_{j\in[0,c-n(}a_{i,j}\,K_j\right)$$.

$$n\ll c\ll l$$, and $$n$$ is known. The alterations have been caused by random communication errors (independent as a first order approximation), and are few enough that $$B_i=A_i$$ in most cases.

One application is cryptanalysis of an hypothetical affine $$n$$-bit MAC defined by unknown keys $$K$$ and $$K_j$$ (as there) with alteration in the available data. If the algorithm scaled well for large error rate, I could imagine application to the cryptanalysis of weak cryptosystems with some degree of linearity.

• $a_{i,j}$ seems to be a scalar but you say $K_j$ are vectors, and then take their dot product? – kodlu Jan 11 at 11:08
• $a_{i,j}$ is a bit, and by $a_{i,j}\cdot K_j$ I was trying to mean $K_j$ when $a_{i,j}=1$, or the $n$-bit zero vector otherwise. I removed that confusing dot. Also I changed some spurious $k$ to $n$. – fgrieu Jan 11 at 11:42