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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.