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

> - 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.
-- 
"Curiousity killed the cat, but for a while I was a
suspect" -- Steven Wright
Security Guru for Hire http://www.li
ghtconsulting.com/~travis/ -><-
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098
0C55 1484

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com

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 majordomometzdowd.com

* Travis H.:

> 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,

I wouldn't call that "linear" if b /= 0,
"affine" is probably better.
But I'm not familiar with the cryptographic term, maybe
it's
different.

> but how exactly does XOR get involved, and are there
+-linear
> functions and xor-linear functions?  Are they disjoint?
 etc.

It refers to arithmetic over GF(2), the field with two
elements.  In
this field, XOR is addition, and AND is multiplication.

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com

http://
www.garlic.com/~lynn/rfcidx14.htm#4492

4492 I
     Elliptic Curve Cryptography (ECC) Cipher Suites for
Transport Layer 
Security (TLS), Blake-Wilson S., Bolyard N., Gupta V., Hawk
C., Moeller 
B., 2006/05/16 (35pp) (.txt=72231) (Refs 2246, 3268, 3279,
3280, 4346, 
4366) (was draft-ietf-tls-ecc-12.txt)

------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomometzdowd.com