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

[leichter_jerrold at emc.com]

| > - 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.
XOR is the same as addition mod 2.  The integers mod 2 form a field
with XOR as the addition operation and integer multiplication (mod 2,
though that has no effect in this case) as the multiplication.

If you think of a stream of n bits as a member of the vector space
of dimension n over the integers mod 2 treated as a field, then
adding two of these - the fundamental linear operation - is XOR'ing
them bit by bit.

The thing I've always wondered about stream ciphers is why we only
talk about linear ones.  A stream cipher is fundamentally constructed
of two things:  A stream of bits (alleged to be unpredictable) as
long as the plaintext; and a combining function that takes one
plaintext bit and one stream bit and produces a ciphertext bit.
The combining function has to conserve information.  If you only
combine single bits, there are only two possible functions:  XOR
and the complement of XOR.  But consider RC4:  It actually generates
a byte at a time.  We just choose to use that byte as a vector of
8 bits.  For plaintexts that are multiples of 8 bits long - just
about everything these days - there are many possible combining
functions.  Most aren't even close to linear.

Other than post by a guy - Terry someone or another - on sci.crypt
a number of years ago - I've never seen any work in this direction.
Is there stuff I'm not aware of?
							-- Jerry


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