17 views

Skip to first unread message

Nov 9, 2009, 5:12:38 AM11/9/09

to

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).

Nov 17, 2009, 6:58:42 AM11/17/09

to

On Nov 9, 5:12=A0am, mockturtle <framefri...@gmail.com> wrote:

> 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. =A0I 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". =A0I apologize

> if the explanation is quite long, =A0but I discovered that if I try to

> be shorter, several misunderstanding can arise.

>

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

>

> My setup =A0is the following: suppose you have

>

> =A0 =A0 + a "source" S,

> =A0 =A0 + several "intermediate node" I_k, k=3D1, ..., N

> =A0 =A0 + a sequence W of M (b-bit) words w_1, w_2, ..., w_M that you wan=

t

> to send to a destination D. =A0Consider words w_k as elements of some

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

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

> exists. =A0In 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

>

> =A0 * The source send sequence W to every intermediate node

>

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

>

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

> R columns, that is (with matlab notation)

> =A0 =A0 =A0 =A0 =A0 =A0 =A0C =3D [ w_1, w_2, ..., w_R; w_{R+1}, w_{R

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

>

> =A0 * Matrix C is left multiplied by r_k to obtain

>

> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0u_k =3D r_k * C =A0 =A0 =A0 =A0 =A0 =

=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (1)

>

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

>

> =A0 * Vector u_k is sent to D

>

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

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

> the set of corresponding r_k is linearly independent. =A0Suppose this

> condition satisfied by some external means]

>

> =3D=3D=3D The bad guy =3D=3D=3D

>

> 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: =A0the attack succedes when D

> _does_not_recover_ W. ]

>

> =3D=3D=3D An easy solution =3D=3D=3D

>

> There is an easy solution to the attack above:

>

> =A0 =A0 =A01) D recovers W by using R vectors u_k,

> =A0 =A0 =A02) it checks that the recovered data is compatible with the

> others u_k. =A0More precisely, if C_maybe represents the matrix

> associated with =A0recovered data, node D checks that

>

> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0u_k =3D r_k * C_maybe =A0 =A0 =

=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (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*.

>

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

=3D=3D=3D

>

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

> the reconstruction step. =A0Moreover, 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. =A0I would like to be able to spot

> the bad vectors without carrying out the reconstruction step.

>

> A solution could be to

>

> =A0 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

>

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

> "signed" vector u_{S,k}

>

> =A0 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). =A0That "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).

I just list some of signatures I know:

aggregate signature/sequential aggregate signature

Verifiably Encrypted Signature

forward-secure signature

multi-signature/sequential multi-signature

transitive signature

Maybe some of these are helpful to you.

Sincerely,

Zhuo

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu