"Inheritable" signatures?
mockturtle
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).
hzh...@gmail.com
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