Then Eve can use G to forge a signature. It is possible for the forged signature

˜

to pass the veri¬cation procedure because all items related to G in the sig-

nature usually can be canceled in the procedure of calculating the syndrome.

In addition, this can also happen to other secret keys. Thus it is possible for

Eve to forge a signature which can pass the other checks in the veri¬cation

procedure.

In Section 3.5 this method will be used to break the Alabbadi“Wicker scheme.

3.3 The Alabbadi“Wicker scheme

The three phases of the Alabbadi“Wicker scheme can be described as follows:

Setup phase: in the setup phase, each user chooses a t“error correcting binary

irreducible Goppa code C with length n = 2m and dimension k. The code is

described by an irreducible polynomial G(z) of degree t and coe¬cients in F2m .

Alice then selects a k — n binary generator matrix G and a (n ’ k) — n binary parity

check matrix H for the chosen code. She then chooses two k — n binary matrices

W and V such that

G = W + V, (3.1)

where the rank of W is k. This means that there exists an n — k binary right“inverse

matrix W ’R such that

W W ’R = Ik , (3.2)

where Ik is the identity matrix. The matrix W ’R is chosen such that GW ’R has

nonzero rank k < k. Then she generates a nonsingular n — n binary matrix R. The

¬nal step of initializing the signature scheme is the computation of the following

3.3 The Alabbadi“Wicker scheme 27

matrices:

H = R’1 H T , (3.3)

W = R’1 W ’R , (3.4)

W = W ’R GW ’R . (3.5)

Alice then publishes G(z), W ’R , H , W , W , t and t < t as public keys. The

private key consists of the matrices V , W , G, W ’R G, and R.

In addition a hash function h : F2k — F2n ’ F2k is made available to all users of

the system.

Signature phase: suppose user Alice wants to sign a k“bit message m. She then

selects two binary vectors at random: a n“bit vector e of weight t , and a k“bit

vector r of arbitrary but nonzero weight. The signature (s, x) of the message m is

then computed as follows:

x = (rG + h(m, e)V ) R,

s = e + h(m, e)W + xW ’R G R.

Finally, Alice transmits the triplet x, s, and m to Bob.

Veri¬cation phase: Bob gets a signature (x, s) along with the message m. The

signature validation is then performed as follows:

(i). The following expression is computed:

rG + h(m, e)V + e + h(m, e)W + xW ’R G R

x+s =

rG + h(m, e)G + e + xW ’R G R.

=

(ii). The syndrome is calculated:

(x + s)H = rG + h(m, e)G + e + xW ’R G RR’1 H T

= eH T .

(iii). The Berlekamp“Massey algorithm is applied to the above syndrome to obtain

the error vector e. If w(e) = t , Bob rejects the signature.

(iv). The hash h(m, e) of the message and the error vector is recovered from x, e,

and s by computing

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

e + h(m, e)W + xW ’R G R R’1 W ’R +

=

+xW ’R GW ’R + eW ’R

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

+xW ’R GW ’R + eW ’R

= h(m, e).

28 Digital signature schemes based on error“correcting codes

(v). Finally, Bob compares the result of the above computation to h(m, e), which

he can calculate himself. If they are equal, he accepts the signature as valid.

Apparently, the proposers of this scheme overlooked the fact that step (iii) of

this veri¬cation procedure will not work, since applying the Berlekamp“Massey algo-

rithm requires the parity check matrix to be in the usual form (1.1) [MS77, Section

12.9]. Obviously, if this step is to work, Alice has to select H to be in the usual

form, and should thus make H public.

3.4 Modifying the Alabbadi“Wicker scheme

Since the veri¬cation phase of the Alabbadi“Wicker scheme will not work unless

the parity check matrix H is in the usual form (1.1), and thus public, a revision of

the scheme is needed. This revision is made here by modifying the three phases as

follows:

Setup phase: Alice ¬rst calculates the public keys as in the original Alabaddi-

Wicker scheme, as described in the previous section. Suppose that the order of

coordinates in F2m is chosen to be canonical (it could also be chosen by each user

individually, but it would then have to be part of the public key as well). Further-

more, let H“ be the parity check matrix of the chosen Goppa code in the usual form

(1.1). Since the chosen matrix H is also a parity check matrix, Alice can ¬nd a

non-singular matrix M such that

H“ = M H.

Alice then publishes G(z), W ’R , H , W , W , t and t < t as public keys. The

private key consists of the matrices V , W , G, W ’R G, R and M .

Signature phase: suppose Alice wants to sign a k“bit message m. She then selects

two binary vectors at random: a n“bit vector e of weight t and a k“bit vector r

of arbitrary but nonzero weight. The signature (s, x) of the message m is then

computed in the following steps:

(i). Alice ¬nds a solution f to the equation f H“ = eH“ M T directly. This is pos-

T T

sible, since a solution surely exists (every syndrome occurs among all vectors

of Fn since we are dealing with a linear code). However, the solution will

2

obviously not be unique since no requirement on the weight is given. Thus f

satis¬es

f H T = eH“ .

T

(ii). Alice computes

x = (e + f + rG + h(m, e)V ) R,

s = e + h(m, e)W + xW ’R G R.

3.5 Cryptanalysis of the Alabbadi“Wicker scheme 29

Finally, Alice transmits the signature (x, s) and the message m to Bob.

Veri¬cation phase: Bob gets a signature (x, s) along with the message m. He

validates the signature in the following steps:

(i). The following expression is computed:

rG + h(m, e)V + f + h(m, e)W + xW ’R G R

x+s =

rG + h(m, e)G + f + xW ’R G R.