the meaning of linearity, was Re: picking a hash function to be encrypted

[James Muir]

Travis H. wrote:
>> - Stream ciphers (additive)
> 
> This reminds me, when people talk about linearity with regard to a
> function, for example CRCs, exactly what sense of the word do they
> mean?  I can understand f(x) = ax + b being linear, but how exactly
> does XOR get involved, and are there +-linear functions and xor-linear
> functions?  Are they disjoint?  etc.

If you have a linear algebra book handy, look up "linear transformation".

Briefly, a function T from a vector space V to another vector space W 
(where V and W are defined over the same field) is called a
linear transformation if it satisfies

i) T(u +_V v) = T(u) +_W T(v)
ii) T(c *_V u) = c *_V T(u)
iii) T(0_V) = 0_W

CRC is a linear transformation because

CRC(u + v) = CRC(u)+CRC(v).

-James

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com