Desirability of chaining an LCG in an authentication scheme Suppose that:


$E(k, x)$ is the encryption of data block $x$ with key $k$ using a block cipher.
$L_{Key}$ is the key size of the block cipher in bits.
$L_{Block}$ is the block size of the block cipher in bits.
$F(x) = (a \cdot x + c) \mbox{ mod } m$, so it's a linear congruential generator.
$m = 2^{L_{Block}}$ is the modulus to be used in $F$.
$a$ and $c$ are such that $F$ has a full period.
$K \leftarrow \{0, 1\}^{L_{Key}}$ is a secret key to be used with the block cipher.
$J \leftarrow \{0, 1\}^{L_{Block}}$ is a value that is derived in some way from $K$, perhaps through using $E$ and a constant.
$T \leftarrow \{0, 1\}^{L_{Block}}$ is an authentication tag.
$i$ is a one-based index.
$x_{i} \leftarrow \{0, 1\}^{L_{Block}}$ is the $i$th block in a stream of data to be verified.
$s$ is the number of data blocks.
$y_{i} = x_{i} \oplus J$.
$t$ is an intermediate value that is calculated prior to $T$. It is first calculated as $t = F(y_{1})$, after which it is recalculated as $t = F(y_{i} \oplus t)$.
$T = E(K, t)$.


Seems secure enough to me (I know that isn't a good assurance, but I know jack about cryptanalysis), assuming the block cipher is secure. Block ciphers typically invoke one or more modular addition operations, so I don't think computing $b \boxplus c$ (where $b = m \cdot x$) is going to be a slow operation. I have no clue as to how much slower the multiplication would be. Would it be too slow to make for a good authentication mode?

Update #1: If $a = 65537$, then computing $a \cdot x$ would only require shifting $x$ to the left by four places and then adding $x$ to the result, which would be much faster than if $a$ had a larger Hamming weight. How much of an improvement in speed would this provide over GCM?
Would it be too slow to make for a good authentication mode?


No, it would be too insecure for a good authentication mode.

In particular, given any message $M$ that's at least two blocks long, it's trivial to find a second message $M' \ne M$ that has the same tag (no matter what the key is); and hence one could be substituted for the other without detection.