mockturtle

2009-11-09 10:12:38 UTC

Hi all,

for a research of mine I would need a special type of signature that I

would call "inheritable". Since cryptography is not my main field of

research, I am not sure if such a thing exists and, if it exists, what

its "official" name is. I was wondering if you could give me some

"pointers" or at least some keywords to google for.

Let me explain what I mean with "inheritable signature". I apologize

if the explanation is quite long, but I discovered that if I try to

be shorter, several misunderstanding can arise.

== The original setup (with no signature, nor bad guys) ==

My setup is the following: suppose you have

+ a "source" S,

+ several "intermediate node" I_k, k=1, ..., N

+ a sequence W of M (b-bit) words w_1, w_2, ..., w_M that you want

to send to a destination D. Consider words w_k as elements of some

Galois field GF(2^b) with 2^b elements.

+ an integer R such that R < N and R divides M (suppose this R

exists. In pratice I would pad the data sequence to have the

divisibility condition fulfilled)

For some reasons that would be too long to explain here, you want to

send W to D using the following procedure

* The source send sequence W to every intermediate node

* Each source I_k extract a random R-dimensional (row) vector r_k

* The data sequence is reorganized into a matrix C with R rows and M/

R columns, that is (with matlab notation)

C = [ w_1, w_2, ..., w_R; w_{R+1}, w_{R

+1}, ... ; ...; .... w_M ]'

* Matrix C is left multiplied by r_k to obtain

u_k = r_k * C (1)

Product, of course, is carried out in GF(2^b).

* Vector u_k is sent to D

* Destination node D can recover C by collecting R different u_k and

solving the corresponding linear system. [Note: this supposes that

the set of corresponding r_k is linearly independent. Suppose this

condition satisfied by some external means]

=== The bad guy ===

The kind of attack I want to counteract here is where one intermediate

node I_bad does not send a vector computed with (1), but some "junk

data", so that D would not recover W.

[Please note an *important* point: the attack succedes when D

_does_not_recover_ W. ]

=== An easy solution ===

There is an easy solution to the attack above:

1) D recovers W by using R vectors u_k,

2) it checks that the recovered data is compatible with the

others u_k. More precisely, if C_maybe represents the matrix

associated with recovered data, node D checks that

u_k = r_k * C_maybe (2)

is satisfied for every k.

It is possible to show that if at least R+1 nodes send correct data,

test (2) will fail whenever some node

*sends_data_that_causes_a_bad_reconstruction*.

=== So, what is a "inheritable signature" and why do you need it? ===

A problem with the solution outlined above is that it requires to do

the reconstruction step. Moreover, if the bad vector was used to

recover W, D must redo the reconstruction again with different input

vectors until it finds the bad ones. I would like to be able to spot

the bad vectors without carrying out the reconstruction step.

A solution could be to

1) The source S "signs" (in some way, I do not know how, this is

what my question is about) the sequence W to produce the signed

sequence W_S

2) Each node I_k processes W_S as described above to produce a

"signed" vector u_{S,k}

3) Node D checks for the correctness of every u_{S,k} before using

it in the reconstruction procedure.

The problem is to use in 1) a "signature" that can be "inherited" by

each u_{S,k}, in the sense that one can easily check in 3) the

integrity of u_{S,k}.

An example of inheritable signature would be a CRC (that is, I append

to W a sequence of values obtained by processing W with some linear

function). That "signature" enjoys the inherability property, but, of

course, is so easy to forge to be useless.

Any pointers?

Thank you in advance for your help (and excuse me for the long

explanation).

for a research of mine I would need a special type of signature that I

would call "inheritable". Since cryptography is not my main field of

research, I am not sure if such a thing exists and, if it exists, what

its "official" name is. I was wondering if you could give me some

"pointers" or at least some keywords to google for.

Let me explain what I mean with "inheritable signature". I apologize

if the explanation is quite long, but I discovered that if I try to

be shorter, several misunderstanding can arise.

== The original setup (with no signature, nor bad guys) ==

My setup is the following: suppose you have

+ a "source" S,

+ several "intermediate node" I_k, k=1, ..., N

+ a sequence W of M (b-bit) words w_1, w_2, ..., w_M that you want

to send to a destination D. Consider words w_k as elements of some

Galois field GF(2^b) with 2^b elements.

+ an integer R such that R < N and R divides M (suppose this R

exists. In pratice I would pad the data sequence to have the

divisibility condition fulfilled)

For some reasons that would be too long to explain here, you want to

send W to D using the following procedure

* The source send sequence W to every intermediate node

* Each source I_k extract a random R-dimensional (row) vector r_k

* The data sequence is reorganized into a matrix C with R rows and M/

R columns, that is (with matlab notation)

C = [ w_1, w_2, ..., w_R; w_{R+1}, w_{R

+1}, ... ; ...; .... w_M ]'

* Matrix C is left multiplied by r_k to obtain

u_k = r_k * C (1)

Product, of course, is carried out in GF(2^b).

* Vector u_k is sent to D

* Destination node D can recover C by collecting R different u_k and

solving the corresponding linear system. [Note: this supposes that

the set of corresponding r_k is linearly independent. Suppose this

condition satisfied by some external means]

=== The bad guy ===

The kind of attack I want to counteract here is where one intermediate

node I_bad does not send a vector computed with (1), but some "junk

data", so that D would not recover W.

[Please note an *important* point: the attack succedes when D

_does_not_recover_ W. ]

=== An easy solution ===

There is an easy solution to the attack above:

1) D recovers W by using R vectors u_k,

2) it checks that the recovered data is compatible with the

others u_k. More precisely, if C_maybe represents the matrix

associated with recovered data, node D checks that

u_k = r_k * C_maybe (2)

is satisfied for every k.

It is possible to show that if at least R+1 nodes send correct data,

test (2) will fail whenever some node

*sends_data_that_causes_a_bad_reconstruction*.

=== So, what is a "inheritable signature" and why do you need it? ===

A problem with the solution outlined above is that it requires to do

the reconstruction step. Moreover, if the bad vector was used to

recover W, D must redo the reconstruction again with different input

vectors until it finds the bad ones. I would like to be able to spot

the bad vectors without carrying out the reconstruction step.

A solution could be to

1) The source S "signs" (in some way, I do not know how, this is

what my question is about) the sequence W to produce the signed

sequence W_S

2) Each node I_k processes W_S as described above to produce a

"signed" vector u_{S,k}

3) Node D checks for the correctness of every u_{S,k} before using

it in the reconstruction procedure.

The problem is to use in 1) a "signature" that can be "inherited" by

each u_{S,k}, in the sense that one can easily check in 3) the

integrity of u_{S,k}.

An example of inheritable signature would be a CRC (that is, I append

to W a sequence of values obtained by processing W with some linear

function). That "signature" enjoys the inherability property, but, of

course, is so easy to forge to be useless.

Any pointers?

Thank you in advance for your help (and excuse me for the long

explanation).