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.

  • $\begingroup$ $a_{i,j}$ seems to be a scalar but you say $K_j$ are vectors, and then take their dot product? $\endgroup$ – kodlu Jan 11 at 11:08
  • $\begingroup$ $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$. $\endgroup$ – fgrieu Jan 11 at 11:42

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.