IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.10, October 2006

220

Secure and Fast Digital Signatures using BCH Codes
Omessaâd HAMDI*, Sami HARARI** and Ammar BOUALLEGUE***,(*),(***)SYSCOM Laboratory, National school of engineering of Tunis, Tunisia
SIS Laboratory, South University of Toulon and Var , France(*),(**)

Summary
In this paper, we present new practical digital signatureschemes based on chained BCH code. Their safety rests on
the well-known Syndrome Decoding problem (SD). We
introduce the first practical and secure digital signaturescheme using a generator matrix as key. Then, we
generate a signature scheme faster than the only practicalone based on Niederreiter cryptosystem.
Key words:
Cryptography, Coding theory,Ddigital signature, Public key size.

Introduction
Since the introduction of public key cryptography in the
70’s [1], many cryptosystems have been proposed andmany cryptographic schemes have been broken. The mostused cryptosystems rely on number theory problem likethe factorization problem [3] and the discrete logarithm
over suitable group [2]. The McEliece cryptosystem [5]and the Neiderreiter variante [6] rely on coding theory,
they are ones of the few cryptosystems, which are very
secure and which are not broken although they do not rely
on number theory. These cryptosystems present many
advantages: they are very fast for both encryption anddecryption and the best attacks complexity are exponential
in the length of the code. These cryptosystems have thedrawback to have a large public key which is a generator
matrix or a check parity matrix of a long code. Anotherdrawback related to the belief that we can not deduce a
digital signature from these public key cryptosystems. In
2001, Courtois, Finiasz and Sendrier [15] introduced thefirst signature scheme based on McEliece cryptosystem.
Firstly, they have presented a scheme based on McEliece
cryptosystem using generator matrix. With the proposed
secure parameters, this scheme is impractical. Secondly,
they have introduced a short practical signature based on
the Neiderreiter variant using the parity check matrix as
key. This scheme has the drawback to have a slow
signature algorithm.
In this paper, we introduce new performant digital
signature schemes based on coding theory similar to those
based on McEliece and Niederreiter cryptosystems. The

Manuscript received September 5, 2006.
Manuscript revised October 25, 2006.

idea of our schemes consists in considering a chained
BCH code. The resulting code will be a secret code which
will be scrambled and permuted to obtain the public code.
The paper is organized as follows: We, first, define“chained BCH code”. Then, we introduce a digital
signature scheme using the generator matrix of chained
BCH code. Unlike, the scheme based on the McEliece
cryptosystem, our scheme has practical parameters and it
is performant in terms of public key size and in signature
length.
Before concluding, we present the dual version of thisscheme. This second scheme permits to skirt the drawbackof the signature based on Neiderreiter cryptosystem.

2. Definition
In order to build a system based on chained error
correcting codes, we need a family of linear codes withgiven parameters, that has some "good" cryptographic
properties. Each code of this family should have apolynomial complexity decoding algorithm.
The family must be large enough to avoid an exhaustive
attack and each code Ci of the family is defined by its
generator matrix ( respectively a check parity matrix)
M i . The obtained system from chaining these codes
called "chained error correcting code " has a resulting
generator matrix (respectively a parity check matrix) withthe following form:
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝

M1
0
M = ...
...

0
... 0
Mk
...

0
0
...

0
0
...
0

0

0

0

Ml

⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠

In our case, codewords and syndromes are stocked intables. To decode a word, we compare it to the tableelements and we take the nearest one to this word or theequal syndrome. So, the decoding operation is very fast. It
consists, only, in some n length vector comparison.

IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.10, October 2006



3. Signature with chained BCH code (BCHS1)•

3.1. Algorithm parametersnElements of GF ( 2 ) are called words and elements of

C i are called codewords of C i . A code is usually definedby its generating matrix. The distance between two words

•
•

221

Secret parameters

A family Γ of l BCH codes. The chained BCH code
is defined by its generator matrix G .
A secret binary permutation matrix P .
A secret binary invertible matrix S .
Public parametersnof GF ( 2 ) is the Hamming distance, that is the numberof positions in which they differ. The weight of a word of

GF ( 2 n ) is its Hamming distance to zero-words.
Γ denotes a family of linear codes. A code C i of Γ will
be defined by its length n , its dimension k i and its
correction capacity ti .
In order to obtain an efficient digital signature, we needan algorithm able to compute a signature for any document
and a fast verification algorithm to anyone.
Thus, the most BCH codes can not satisfy the first point.
In fact, if we consider a random word of length n ( n is
the length of the chosen code), it is usually chosen at a
distance greater than the decoding capacity of this code. In
other terms, we can find a word which is not decodable.
One solution to this problem is to obtain an algorithm ablento decode any word of the space GF ( 2 ) . In [8],N.Courtois, M.Finiasz and N.Sendrier have introduced amethod named complete decoding to solve this problem.
Complete decoding consists in finding the nearestncodeword to any given word of the space GF ( 2 ) . To
achieve this goal, we do not decode at the correction
capacity t but at a distance c = t + δ .
In [8], authors evaluate the smallest δ for which thevolume of the sphere with radius δ is greater than 2⎧

δ min = min ⎨δ ∈ Ν⎩i +δ∑C > 2
i
n

i =0

n −k

n− k

.

⎫
⎬ (1)
⎭

Nextly, we denote by BCH [n, k i , t i ] a BCH code oflength n , of dimension k i and correction capacity t i .
The chosen BCH codes set is formed by BCH [15,11,1] ,BCH [15,11,2] completed by one bit and BCH [15,11,3]
completed by two bits using (1).

The public key of our scheme consists in:• A matrix G ' defined by:

G ' = S .G.P
The matrix G is obtained from chaining BCH codes. By
the algorithm construction, G ' is a permuted andscrambled generating matrix.

3.2. Key generation
In our scheme, the public key is deduced from the secretkey as described in section 2. In this section, we need
only to describe how the secret key and exactly thegenerating matrix G is obtained.
We consider a family Γ of BCH codes. A code C i isby its length n = 15 , its dimension
k i ∈ {5,7,11} and its correction capacity t i . Codes of Γ

definedare chosen randomly.
The generated matrix G results from chained BCH code.
So, G is diagonal in blocs whose diagonal is formed byelementary generating matrices of used codes (see section
2).
To hide the G structure, we permute its columns and thenit will be multiplied by an invertible matrix to obtain the
public key G ' .

3.3. Signing a document
In the present section, we describe the signature of amessage M by our new scheme.



Signing algorithm

The document M to be signed is given by a binary
sequence of length N .
The first step, that a signer must do, is to choose
parameters shown in the previous section. Indeed, thesigner chooses a random generator of codes, an invertible
matrix S and a permutation matrix P.

IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.10, October 2006

222

In the second step, he constructs the generating matrix Gof chained linear error correcting code. Then, he calculates
the matrix product:

G ' = S .G.P

and publishes this entity G ' .
The third stage is the signature: the signer who wants tosign the message M , formed by a binary sequence oflength N bits, permutes his message by multiplying it by
the inverse of P . Then, he splits his message in words oflength n to get a family of words mi . He applies
systematic decoding, that means he looks for the nearest
codeword and he keeps the first k i bits of every mi ( k irepresents dimension of used code to decode mi ).
The concatenated blocks obtained after decoding represent
a binary chain of length K which depends on generated
codes. This sequence will be multiplied by a matrix S
to obtain a chain y of length K .

−1

y is the signature of M .
Let’s regroup this in an algorithmo Parameters:- A family of l BCH codes of length n = 15 and of
dimension k i ∈ {5,7,11}. The resulting matrix G of thechained codes is a diagonal matrix..
- The N × N binary permutation matrix P .
- The K × K binary random invertible matrix S .
o Public key:

G ' = S .G.P

oSecret key :oSignature:{S , G, P}

M is a document to be signed of length N .
- Compute ρ = h (M )−1
- Compute x = ρ .P
- Split x in ( x1 , x 2 ,..., x l ) ; x i , i = 1..l are sequencesof n bits- Decode a i = dec k i ( x i ) ; i = 1..l ;- a = ( a1 , a 2 ,..., a l ) has a length K =

∑ ki
i

-

y = a.S −1

y is the signature.
correction capacities of used codes. He multiplies y by
the resulting generator matrix G ' to get a binary chain bof length N and he compares the distance between b
and h (M ) to the sum of the used codes capacity
correction.
The signature is valid if the following condition issatisfied:d H (b, h ( M )) < ∑ c ii

3.4. Implementation
In this section, the key generation, signature andverification algorithms will be implemented and discussed
in more details.


Key Generation

This is certainly the most complicated part of thealgorithm. It is certainly less critical than the signature andverification, but the nature of the operations (e.g. inversion
of a K × K matrix) requires careful coding if areasonable performance is expected. The key generation
involves the following steps:- Select a random N × N permutation matrix P andconstruct the invertible scramble matrix S as follows:
S = S1 × S 2 , where S 1 is a lower triangular matrix overGF (2) with random entries and S 2 is an upper
triangular matrix over GF ( 2) with random entries and−1with diagonal elements equal to 1. The inverse S is−1−1−1easily computed as S = S 2 × S 1- Generate randomly the family of BCH codes.
The public key G ' is computed as S .G.P , and thesecret key consists of S , G and P .
Signature cost

The signature algorithm is very fast. It consists in:- One multiplication of a binary vector of length N by amatrix N × N . Therefore it requires N / 2 binary
operations.
- One multiplication of a binary vector of length K by a2

matrix K × K . Therefore it requires
operations.

K 2 / 2 binarykControl algorithm

To control the validity of the signature, the verifier
receives the message M , its signature y and the sum of- l decoding operations which has a cost of K 2 i binary
operations.

IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.10, October 2006



Verification cost223

of l BCH codes will be chained to obtain a large code of

The verification algorithm is very fast since it consists ina multiplication of a K length binary vector by a matrix
K × N . Therefore, it requires K ⋅ N / 2 binary
operations.

3.5 Performances
Our scheme is determinist to sign and to verify the validityof the signature. Indeed, it permits to sign all messages
since the signer, who possesses the secret key ( S , G , P ) ,can sign any message after completing BCH [15,7,2] andBCH [15,5,3] .
Moreover, our algorithm permits to verify every signatures
for every message by anyone possessing the public key
G' .
Indeed, the verifier calculates

y.G ' = y.S .G.P = a.G.P
Then, he codes the text a to get a text x ' . By
multiplying x ' by P , the distance between the obtained

message and the original text must be inferior to thecompleted codes correction capacities sum.
In our implementation, we have chosen to sign a binary
sequence of length 1000 with BCH [15,5, c = 1] ,BCH [15,7, c = 3] and BCH [15,5, c = 5] ( c is thecorrection capacity of completed code calculated with (1) ).
The obtained signature is of overage length K = 500
bits.
The table 1 summarizes the efficiency of our scheme
BCHS1 compared with McEliece signature.

length N =

l

l

i =1

i =1

∑ n and dimension K = N − ∑ k i .

4.1. Signature parameters
 Secret parameters- A family of l BCH codes.
The parity check matrix of each code is stocked in a large
matrix H which we call parity check matrix of chained
BCH code (see section 2).
- A binary permutation matrix P over GF ( 2) .
- A binary invertible matrix S over GF ( 2) .


Public parameters

The public parameter used to validate the signature is the
public matrix H ' deduced from the secret parameters{S , H , P}. It is a parity check matrix of an equivalent
code of chained BCH code.
We need, also, a hash function with an output of length
N −K.

4.2. Signature algorithm


Signing a document

The message M to be signed is a binary sequence.
- Compute ρ = h (M ) .
- Compute a = S

−1

.P .

- Split the sequence a in n − k i length blocs ai

Tab 1: Signature with chained BCH code BCHS1 compared tothe one based on the one based on McEliece cryptosystem- If a i is a syndrome then stock the correspondent error

Signature

Else modify one bit and try to code, if it is a syndromethen stock the modified bit in a sequence σ ' else
remodify, again, another bit, etc...

Data
size
Signature
lengthKeysize (bit)McEliece

BCHS1

65536

1000

65392

500

4292069312

5000004. Signature with dual version of chained
BCH Code (BCHS2)
As the first scheme, we consider a set of l BCH codes oflength n = 15 and of dimension k i ∈ {5,7,11}. The set

bi of length n in the message b .

−1- Compute y = P .b
- Compute σ = S .σ 'The Signature is formed by ( y , σ ) .

Verification algorithm

In the verification step, we have the message M , thesignature ( y , σ ) .
- Compute ρ = h (M ) .

IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.10, October 2006

224

ρ ' = H '. y t .
- Compute ς = σ + σ ' .
The signture is valid if ς = ρ

4.3. Implementation aspects

Let’s regroup the signature algorithm in a flow diagram:

The complexity of the signature is based specially on
decoding with the chained BCH code.
The decoding operation is done by blocs using elementary
codes. It consists in testing if an ( n − k i ) tuples is a

- ComputeMρ = h(M )a = S −1 . ρ( a1 ,.., a l )Signature cost

syndrome.
The BCH code of length n = 15 and of dimension
k i = 11 correcting t i = 1 error is a perfect code so all( n − k i ) tuples are syndromes.
The BCH code of length n = 15 and of dimension
k i = 7 correcting t i = 2 errors (or of dimension
k i = 5 correcting t i = 3 errors) has C nti syndromes.
The probability to have a decodable ( n − k i ) tuples is:

j++

σ'= 0

a i ⊕ = 1 >> j

j=0

P=

C nti
1
≈
n − ki2
2

So, for each bloc of length n − k i with k i ∈ {5,7,11} isNon − kiof
2
random bit modification to obtain a decodable n − k i

a i :syndrome

the dimension of the i

Yes

' th

used code, we needtuples. Then, the complexity of signature is:bi = dec( a i )σ i '⊕ = 1 >> j(b1 ,.., bl )(σ ' 1 ,.., σ ' l )y = P −1 .b

σ = S .σ '( N − K )(n − k i ti
C n + ( N − K )) + N
2

 Verification cost
The verification cost is the complexity of the syndrome
determination from the error.
So, the verification requires( c + 2)( N − K )binary operations with c =

l

∑c

i

i =1

( y, σ )M
Fig 1: Signature with dual version of chained BCH code

4.4. Security
There are two broad types of attacks:
 Decoding attack: Information Set decoding (IS)Our schemes are based on the well known problem NPcomplete:IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.10, October 2006

225

Syndrome Decoding (SD)Instance : Let H be a ( n − k ) × n binary matrix , s a

Tab 2 New signatures schemes BCHS1 and BCHS2 comparedto the one based on Neiderreiter cryptosystembinary vector of size n − k and an integer p .
Question : Is there a binary vector x of size n of weight

Signaturesmaller or equal to p such that Hx = s ?

Data
Size
Signature
lengthKeysize (bit)Signature
cost
Verification
cost
IS
attackworkfactor +Structuralattackt

The most efficient algorithms in our case are based on theinformation set decoding. A first analysis was done by Lee
and Brickell in [12], Stern in [13] , Leon in [11] and atlast by Canteaut and Chabaud in [14] which is the mostefficient one.
Consider a binary code of length n , of dimension k andof correction capacity t , if one uses information set
decoding, one chooses a random set of k columns, anerror is decodable when its support doesn’t meet the krandom columns. The probability for an error to be

C nt − kdecodable is then Pdec =
.
C nt
P(k )
Pdec

P(k ) corresponds to the cost of Gaussianelimination, P (k ) can be first thought as a cost inO(k 3 ) .

where



Structural attack

BCHS2

144

1000

900

132

500

1350

223

219

219

233 *

220 **

216 **

210

218

216

280

288

285

2119

2106

295

: the document is hashed t! times,: the document is hashed only one time:the IS attack workfactor is the one of the Canteaut and Chabaudalgorithm.

**+

The signature BCHS2 has the following proporties
compared to the signature based on Niederreiter
cryptosystem:- It has a signature algorithm faster 157000 times,- It has a public key size smaller 23 times,- It has a verification algorithm slower 42 times,- It has a signature longer 10 times

5. A variant that improves the security

The complexity of this attack on our signature scheme
public key can be measured by searching exhaustively for
all possible combination of permutation ( N !), secretcode ( 3 ) and invertible matrix ( 0.29 × 2 ). Then, foreach secret key, one has to test wether this key is the goodone.
In the case of our scheme, the complexity of this attack
can be increased due to the fact that the secret code isformed by three BCH codes. We can apply permutations
to the elementary BCH codes to increase their number.
l

BCHS1

*

Then the estimated work factor WF to find a word ofweight t can be estimated as follow:

WF =NeiderreiterK

In this variant, we will introduce a "random" sequence inthe signature to increase the security of the previous
scheme. The principle consists in transforming a syndrome
to another syndrome by modifying some random bits. As
calculated for the previous scheme, the probability toobtain a decodable n − k i tuples for a code c i of lengthn and dimension k i is 1/2. This modification requiresn − kiattempt and if we re-sign the same text, we have2
−60
to obtain the same signature.
a probability of 2
The new scheme algorithm is as follow:- Computeρ = h(M ) .

.ρ .
- Split the sequence a in n − k i length blocs a i- Compute a = S−1IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.10, October 2006

226

- If a i is a syndrome then modify it in another syndromeby modifying a random bit and stock the modified bit in asequence σ ' and, then, store the correspondent error biof length n in the message b .
Else modify a bit until obtaining a syndrome andtransform it to another syndrome then stock the modified
bit in the sequence σ ' .
−1- Compute y = P .b
- Compute σ = S .σ 'The Signature is formed by ( y , σ ) .
The complexity of this algorithm is:( N − K )(( n − k i )C + ( N − K )) + N
tinwhich is very close to the one of the previous scheme.
With this algorithm, we preserve the same performances
and we improve the security.

6. Conclusion
In this paper, we have defined a new signature scheme
based on the well known Syndrome Decoding problem SD.
Our schemes consist in chaining a family of BCH codeswith various dimensions. The resulting matrix of chaining
these codes forms the trapdoor of our algorithm.
The main contribution in this paper consists, firstly, in
generating a practical digital signature using generator
matrix and, secondly, in introducing another scheme fasterthan the only practical and secure signature scheme basedon coding theory.
Our schemes offer, also, a fast and short signature withless public key size than the signature based on McEliece
and Neiderreiter public key cryptosystem.

References[1] W.Deffie and M.E. Hellman, New directions incryptography, IEEE Transactions on information theory, vol 22,
N°.6, pp.644-654 , 1976.
[2] T.ElGamal, A public-key cryptosystem and a signaturescheme based on discrete logarithms, Advances in Cryptography,
Crypto’84, pp.10-18, 1985.
[3] R.L. Rivest, A. Shamir and L.M. Adleman, A method for
obtaining digital signatures and public key cryptosystems,
Communications of the ACM, Vol.21, No.2, pp.120- 126, 1978.
[4] E.R. Berlekamp, R.J. McEliece, and H.C.A. van Tilborg, On
the inherent intractability of certain coding problems, IEEE
Transactions on Information Theory, Vol.24, No.3, pp.384386 ,1978.
[5] R.J. McEliece. A public-key cryptosystem based on algebraic
coding theory; DSN Prog. Rep., Jet Propulsion Laboratory,
California Inst. Technol., Pasadena, CA, pp. 114-116,January
1978.

[6] H.Neiderreiter. Knapsack-type crytosystems and algebraic
coding theory. Prob. Contr. Inform. Theory, 15(2):157-166, 1986.
[7] S.harari, Anew authentification algorithm, Proceeding of
Coding Theory and Applications, Lectures Notes in Computers
Sciences 388, pp91-105 , 1988.
[8] N.Courtois, M.Finiasz, N.Sendrier. How to acheive a
McEliece based digital signature scheme. Rapport de recherche
INRIA n°4118, ISSN 0249-6399, Fevirier 2001.
[9] P. Veron. A fast identification scheme. In IEEE Symposiumon Information Theory, Canada, 1995.
[10] Jacques Stern. A new identification scheme based on
syndrome decoding. In Douglas R. Stinson, editor, Advances in
Cryptology-CRYPTO ’93, volume 773 of Lecture Notes in
Computer Science, pages 13-21. Springer-Verlag, 22-26
August 1993.
[11] J.S.Leon, A probabilistic algorithm for computing
minimum weights of large error-correcting codes. IEEE
Trans. Inform. Theory, IT-34(5), pp. 1354-1359, 1988.
[12] P.J.Lee and E.F. Brikell, An observation on the security of
McEliece’s public key cryptosystem, Lecture notes in Computer
Science , Advances in Cryptology, Eurocrypt’88, pp. 275-280 ,
1989.
[13] J.stern, A method for finding codewords of small weight,
Coding Theory and Applications, Lecture Notes in Computer
Science 434, pp. 173-180.
[14] A.Canteaut and H.Chabbane, A further improvement of theworfactor in an attempt at breaking Mceliece’s cryptosystem,
Proceeding of Eurocode’94, Inria, pp. 163-167.
[15] N. Courtois, M. Finiasz, and N. Sendrier, "How to achievea McEliece-based digital signature scheme", In C. Boyd, editor,
Asiacrypt 2001, volume 2248 of LNCS, pages 157-174.
Springer-Verlag, 2001.

Hamdi Omessa$ad wasborn in 1978 in Gabès,Tunisia. She received thedegreeinelectricalengineering from National
School of Engineering ofTunis, Tunisia, in 2002, andthe postgraduate research
degreeintelecommunications, in 2003,
from National School ofEngineering of Tunis, Tunisia, in 2003.
She is preparing her PHD in National School ofEngineering of Tunis, Tunisia, and in South University of
Toulon and Var, France. Her actual research interests
involves cryptography and network security.