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
    Commented Jan 11, 2019 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
    Commented Jan 11, 2019 at 11:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.