is trying to forge a signature, not to obscure G).

32 Digital signature schemes based on error“correcting codes

To obtain a signature for the message m, Eve ¬rst calculates the vector x of the

signature pair (x, s) from the implicit equation

˜ ˜˜

x = h(m, e)V + xY R. (3.13)

Then she can calculate s from

˜ ˜˜

s = e + h(m, e)W + xY R. (3.14)

Eve can now send the triple (m, x, s) as a message with a forged signature to Bob.

This triple will be shown to pass the signature validation of the Alabbadi“Wicker

scheme. Bob follows the veri¬cation procedure to get

˜ ˜˜

(x + s)H = h(m, e)V + e + h(m, e)W RH

˜ ˜˜

= h(m, e)G + e RR’1 H T

= eH T .

It is obvious that the signature (x, s) will pass the ¬rst three steps of the veri¬cation

phase. Now Bob looks at the fourth step:.

sW + xW + eW ’R = sR’1 W ’R + xW + eW ’R

˜

eW ’R + h(m, e) + xY W ’R + xW + eW ’R

=

eW ’R + h(m, e) + xW + xW + eW ’R

=

= h(m, e).

So the forged signature has passed all steps of the veri¬cation and Bob will accept

the signature as a valid one (from Alice).

Example

As an example, Eve will now forge a signature using the Alabaddi“Wicker scheme.

The same [6, 3, 3]“code that Alabbadi and Wicker chose for their example in [AW95]

will be used here. The public and private keys for their example of the scheme are:

« « «

110110 011100 101100

G = 1 0 1 1 0 1 ,H = 1 0 1 0 1 0 ,W = 1 1 1 1 0 1 ,

111000 110001 111010

« «

1 0 0 0 0 0 100 0 0 0

¬1 1 0 0 0 0· ¬1 1 0 0 0 0·

«

011010 ¬ · ¬ ·

¬0 0 0 1 0 1 · ’1 ¬ 0 1 1 1 0 0·

V = 0 1 0 0 0 0 ,R = ¬ ·,R = ¬ ·,

¬1 1 1 1 0 1· ¬0 0 1 0 0 1·

000010 ¬ · ¬ ·

1 0 0 1 1 0 1 0 1 0 1 1

0 0 0 0 0 1 000 0 0 1

3.5 Cryptanalysis of the Alabbadi“Wicker scheme 33

« « « «

0 0 1 011 001 101

0 1 1· ¬1 1 0· ¬0 1 0· ¬1 0 0·

¬

¬ · ¬ · ¬ · ¬ ·

1 1 1· ¬1 1 1· ¬1 1 0· ¬0 0 0·

W ’R

¬

=¬ ·,H = ¬

¬ 1 1 1 ·,W = ¬ 0 1 0 ·,W = ¬ 0 0 1 ·.

· ¬ · ¬ ·

0 1 0·

¬

¬ · ¬ · ¬ · ¬ ·

1 0 0 1 1 0 1 1 1 1 0 0

1 0 1 001 101 001

Suppose that Eve has recovered the parity check matrix H as described in Section

˜˜˜ ˜

3.5.2 (or otherwise). Now she will calculate the analogous matrices R, G, W and Y

from the public keys of the Alabbadi“Wicker scheme.

˜

First Eve calculates R’1 from Equation (3.7):

«

100000

¬0 1 0 0 1 1·

¬ ·

¬0 1 1 1 0 0·

˜

R’1 = ¬¬ 1 0 1 0 1 0 ·.

·

¬ ·

0 0 1 0 0 0

000001

Note that many choices are possible here since H T |W ’R is not a full“rank matrix.

˜ ˜

Now she inverts this matrix to get R (note that R’1 is a full“rank matrix, so this

is possible). «

100000

¬1 1 0 1 1 1·

¬ ·

¬0 0 0 0 1 0·

˜

R=¬ ¬ 1 1 1 1 0 1 ·.

·

¬ ·

1 0 0 1 1 0

000001

˜ ˜

The matrices R and R’1 are indeed not equal to R and R’1 . However, this does

not e¬ect Eve™s ability to forge a signature.

˜˜ ˜

Similarly, Eve calculates the analogous matrices G, W and Y from equations

(3.10), (3.11) and (3.12):

«

000001

¬0 0 0 0 1 0·

« «

100011 000010 ¬ ·

¬0 0 0 0 0 0·

˜ ˜ ˜

G = 0 1 0 1 0 1 ,W = 0 0 0 1 0 0 ,Y = ¬ ¬ 0 0 0 0 1 1 ·.

·

001110 000011 ¬ ·

0 0 0 0 1 0

000011

˜ ˜ ˜ ˜

The matrix V follows from the equation G=W +V:

«

10 0001

˜ =0 1 0 0 0 1 .

V

00 1101

34 Digital signature schemes based on error“correcting codes

Suppose Eve wants to sign the message m = (001) and selects the error vector

e = (000001). As in [AW95], the hash value is taken to be h(m, e) = (011).

According to Equations (3.13) and (3.14) of the forgery steps, Eve calculates the

signature pair (x, s) of the message m as x = (101111) and s = (111100).

The veri¬cation of this signature pair goes as follows: in the ¬rst step, x + s =

(010011). Then the syndrome is calculated to be (010011)H = (001) in the second

step. Now suppose that Bob is able to recover the error vector from the above

syndrome. Clearly, the recovered error vector will be e = (000001), since the last

column of H is exactly (001)T . Finally, the expression