WO2014188336A1

WO2014188336A1 - Method and system for the digital signature

Info

Publication number: WO2014188336A1
Application number: PCT/IB2014/061557
Authority: WO
Inventors: Marco Baldi; Joachim Rosenthal; Davide Schipani; Franco CHIARALUCE; Marco Bianchi
Original assignee: Zurich Universitaet Institut fuer Medizinische Virologie; Universita Politechnica delle Marche
Current assignee: Zurich Universitaet Institut fuer Medizinische Virologie; Universita Politechnica delle Marche
Priority date: 2013-05-20
Filing date: 2014-05-20
Publication date: 2014-11-27
Anticipated expiration: 2015-11-20
Also published as: ITMO20130140A1

Abstract

The method for the digital signature comprises the following steps: - defining a public calculation function (7) suitable for calculating a syndrome vector (s) starting from a digital file (D) to sign; - selecting a private error corrector code (C(n, k)); - calculating the syndrome vector (s) by means of the calculation function (7) and starting from the digital file (D) to sign; - determining an error vector (e) starting from the syndrome vector (s) and by means of the error corrector code (C(n, k)); - determining a digital signature (e') starting from the error vector (e); - associating the digital signature (e') with the digital file (D) to obtain a signed digital file (D'); - wherein the syndrome vector (s) calculated by means of the calculation function (7) is made up of a sparse vector.

Description

METHOD AND SYSTEM FOR THE DIGITAL SIGNATURE

Technical Field

The present invention relates to a method and a system for the digital signature. Background Art

Two main systems are known for digital signature based on codes: the Kabatianskii-Krouk-Smeets (KKS) system and the Courtois-Finiasz-Sendrier (CFS) system.

In particular, the KKS system uses two codes of different dimensions to make a so-called "trapdoor" function.

Nevertheless, the KKS system has a major weak point.

In fact, it has been shown that many system parameter choices are weak with respect to the use of algorithms for finding low-weight words in linear block codes.

This is due to the fact that the information made public in the KKS system permits defining a linear block code containing many low- weight words which have bits set only in a small sub-set of possible positions. This considerably increases the efficiency of probabilistic algorithms, such as Stern's algorithm, aimed at finding such low- weight words.

The CFS digital signature system uses a "hash-and-sign" paradigm based on the fact that only the authorized signer is able to use the error correction capacity of a secret code.

In particular, the main components of the CFS system are a private corrector code C able to correct t errors and a public hash algorithm Jf.

The private corrector code C can be described by means of a generating matrix G or, in an equivalent way, by means of a parity matrix H.

In particular, if described by means of the matrix H, then the matrix H' = S x H is made public, where S is a private random matrix.

Furthermore, the CFS system of known type comprises a function F suitable for transforming, within a reasonable time, any hash value obtained by means of the algorithm Ji into a correctable syndrome s for the private corrector code C.

In detail, the method for the signature of a digital file D by means of the CFS system comprises the following steps: - the signer calculates the hash vector h = H(D);

- the signer calculates s = F(h) in such a way that s ' = S^{'1 ■} s corresponds to a correctable syndrome for the code C; such calculation can be made by means of an empiric procedure, by trial and error;

- the signer applies a syndrome decoding algorithm to s' by means of C and obtains an error vector e, with weight w < t, so that s ' = H^■ e;

- the signer applies the digital signature to the file D, obtaining the signed file D ', where such digital signature is made up of the error vector e and of the parameters used inside the function F to obtain the s ' value, which are made public;

- following the receipt of a copy of the signed file D ' the verifier calculates H' - e = S^■ H^■ e = S^■ s ' = s;

- the verifier also calculates h = H(D ') and s = F(h) using the parameters of the function F associated with the signed file D ';

- if 5 = s, then the file D ' is accepted; otherwise, the file D ' is deemed invalid and rejected.

The CFS system is not however without its drawbacks.

In particular, the main limits of the CFS system relate to the function F. In fact, it is very hard to determine a function able to quickly transform an arbitrary hash vector into a correctable syndrome.

To overcome this drawback, the CFS system presents two possible alternative solutions:

- add a counter to the message;

- make a complete decoding.

Nevertheless, both solutions require a very careful choice of the code parameters to obtain, in a reasonable time, a correctable syndrome starting from any hash vector.

For this reason, high rate codes are generally used with limited error correction capacity.

Consequently, such choice involves the exposure of the cryptography system to attacks based on the so-called "generalized birthday attack", as well as to the common attacks normally affecting cryptography systems based on codes.

Such limit is due mainly to the need to ensure that many vectors produced by the hash function .T are correctable.

In addition, particularly in the case of a complete decoding being performed, the complexity of decoding can be considerably high.

Description of the Invention

The main aim of the present invention is to devise a method and a system for the digital signature which permits avoiding the attacks commonly suffered by a conventional CFS type system.

Another object of the present invention is to devise a method and a system for the digital signature able to allow a faster processing speed, together with the use of less computational power, compared to a CFS system of known type. Another object of the present invention is to devise a method and a system for the digital signature able to allow a reduction in the decoding complexity compared to a CFS system of known type.

Another object of the present invention is to devise a method and a system for the digital signature able to allow the use of a public key of smaller size compared to a CFS system of known type.

Another object of the present invention is to devise a method and a system for the digital signature which allow to overcome the mentioned drawbacks of the prior art in the ambit of a simple, rational, easy and effective to use as well as low cost solution.

The above objects are achieved by the present method for the digital signature, comprising the following steps:

- defining a public calculation function suitable for calculating a syndrome vector starting from a digital file to sign;

- selecting a private error corrector code;

- calculating said syndrome vector by means of said calculation function and starting from said digital file to sign;

- determining an error vector starting from said syndrome vector and by means of said error corrector code;

- determining a digital signature starting from said error vector; - associating said digital signature with said digital file to obtain a signed digital file;

characterized in that said syndrome vector calculated by means of said calculation function is made up of a sparse vector.

Brief Description of the Drawings

Other characteristics and advantages of the present invention will become evident from the description of a preferred but not exclusive embodiment of a method and a system for the digital signature, illustrated by way of an indicative, but not limitative, example in the accompanying drawings in which: Figure 1 is a flow chart that schematically illustrates a phase of signature of a digital file by means of the method according to the invention;

Figure 2 is a flow chart that schematically illustrates a phase of verification of a digital file signed by means of the method according to the invention;

Figure 3 shows an illustrative table that shows parameters related to the possible implementations of the method and system according to the invention;

Figure 4 shows an illustrative table that shows the size values of the public key in the case of Quasi-Cyclic Low-Density Generator-Matrix (QC-LDGM) codes being used having the parameters shown in Figure 4, for different security levels.

Embodiments of the Invention

With particular reference to figures 1 and 2, globally indicated by M is a method for the digital signature based on codes, able to use a sub-set of the possible syndromes, selecting only those having a determinate density of no null elements.

A first phase of signature of a digital file D using the method according to the invention is schematically shown in the flow chart in figure 1.

The method M for the digital signature comprises defining a public calculation function Y suitable for calculating a syndrome vector s starting from a digital file D to sign.

Preferably, the calculation function Y comprises:

- a public hash function .T (step 1);

- a public conversion function Fg suitable for converting a hash vector (h) obtained by means of the hash function .T into a syndrome vector s (step 2)·

The method M for the digital signature also comprises selecting a private error corrector code C(n, k) (step 3).

In particular, the error corrector code C(n, k) can be defined by means of its own generating matrix G with dimensions k*n and/or by means of its own parity matrix H with dimensions rxn.

The method M envisages calculating the syndrome vector s by means of the calculation function Y and starting from the digital file D to sign (step 4).

In particular, the method M comprises the calculation of the hash vector h by means of the hash function H and starting from a digital file D to sign, according to the formula h = H(D) (step 5) and, subsequently, the calculation of the syndrome vector s by means of the conversion function Fg and starting from the hash vector h, according to the formula s = Fe(h) (step 6).

Advantageously, the conversion function Fg converts the hash vector h into a corresponding syndrome vector s made up of a sparse vector (with low density of no null elements).

In particular, the sparse vector s has a predefined value of density of no null elements and has a predefined length r and a weight w smaller than r.

The conversion function Fg is suitable for converting the hash vector h into the sparse vector s according to a group of determined parameters Θ starting from the digital file D. Such parameters Θ are public and included in the digital signature of the file D itself.

In a possible embodiment of the method M according to the invention, the conversion function Fg is suitable for expanding a hash vector h of reduced dimensions so as to obtain a respective sparse vector s of bigger dimensions. Such expansion can be obtained in various ways.

One example consists in converting the binary hash vector h into the corresponding decimal whole number and then representing such whole number according to a positional code which uses w bits set inside a vector with a r bit length.

One possible solution for achieving the function Fg in such a way that its output depends on the parameter Θ is the following.

Given the hash vector h obtained from the file D, and having a x bit length, the value is added of a y bit binary counter m, thus obtaining the binary vector [h\m]. Such vector is then converted into one of the possible vectors of length r and weight w, as expounded above.

By changing the value of the counter m, a different vector is obtained with length r and weight w, consequently Θ coincides with m. Different methodologies and different implementations of the conversion function Fg cannot however be ruled out suitable for obtaining sparse vectors s starting from corresponding hash vectors h.

The use of the sparse vector s allows a more practical choice of the coding parameters compared to the solutions of known type, such as the Courtois- Finiasz-Sendrier (CFS) digital signature scheme, and permits the use of simplified decoding procedures.

Consequently, the main advantages deriving from the use of the method M are the following:

- to prevent potentially damaging attacks normally suffered by the conventional CFS system;

- to considerably reduce decoding complexity;

- to considerably reduce the dimensions of the key with respect to a conventional CFS system.

The method M also comprises the step of determining an error vector e starting from the sparse vector s (step 7).

In particular, the determination of the error vector e envisages the selection of a first matrix Q with dimensions r*r and of a second matrix S with dimensions «x« (step 8).

In particular, the first matrix Q and the sparse vector s are such that the private sparse vector s' is defined by the formula:

s ' = Q - s

and has weight w .

Preferably, the first matrix Q can be obtained as the sum of a low rank dense matrix R, z < r, with dimensions r*r and of a matrix T selected so that Q = R + T is a full rank matrix.

The second matrix S is selected in the form of a non singular sparse matrix. Subsequently, the method M envisages the determination of a public parity matrix H' (step 9) by means of the formula:

H^ Q-^! - H - S^'1

where H' is the public parity matrix, Q¹ is the inverse of the first matrix Q, S^'1 is the inverse of the second matrix S and H is the parity matrix of the error corrector code i.

The error vector e is calculated by means of a syndrome decoding algorithm, in such a way that s ' = H^■ e (step 10).

In particular, the fact is underlined that the error corrector code C(n, k) is in systematic form.

In fact, if a code is systematic, then it can have a parity matrix H_s = [P\I\, where P is a matrix r*k and I is the identity matrix r*r.

Consequently, each syndrome s can be obtained from the vector e_s = [O^s⁷], where 0_lxk is the vector with dimensions l *k with all values equal to zero. In fact, checking that Hs · e_s ^T = s is immediate.

Subsequently, the method M envisages the application of the digital signature to the digital file D, wherein the digital signature is determined according to the error vector e (step 11).

In particular, the determination of the digital signature envisages the selection of a code word c belonging to the error corrector code C(n, k) (step 12).

Usefully, c has a low weight w_c.

Consequently, considering that the number of vectors e corresponding to each vector s ' is very reduced, randomly generated error corrector codes C(n, k) can be used.

In this respect, with reference to a preferred but not exclusive embodiment of the method M, the use of randomly generated codes of the LDGM (Low- Density Generator-Matrix) type represents an effective solution.

In particular, supposing that the generating matrix G with dimensions k*n of the secret error corrector code C(n, k) is obtained by choosing its k lines as random binary vectors with dimensions i*« with weight w_g « n, then such generating matrix G defines an LDGM type code the minimum distance of which is very likely equal to w_g.

Consequently, such code contains words of weight w_c≥ w_g.

A parity matrix H can be easily obtained starting from the generating matrix G. With reference instead to the selection of the code word c with weight w_c, it can be observed that such code word can be easily obtained by adding together Wc/wg lines of the generating matrix G selected randomly. In this respect, it is pointed out that w_c must be a multiple of w_g. In other cases, a code word can in any case be obtained with a weight close to w_c by linearly combining lines of G. Consequently, using LDGM type codes, the signer can easily generate a high enough number of random code words with a moderately reduced weight w_c. Such codes have both the parity matrix and the generating matrix in the form of sparse matrices consisting of cyclic sub-matrices with dimensions p*p. It follows that the length and the dimension of the code are both multiples of the whole p, i.e., n = nop, k = hop.

As shown by way of example in the table of figure 4, the use of the codes QC- LDGM permits reducing the dimensions of the public key by a factor equal to p compared to the case of non nearly cyclic LDGM codes.

Subsequently, the method M comprises the determination of the digital signature e ' (step 13) by means of the formula:

e ' = (e + c) - S^T

where e indicates the error vector, c indicates the code word and S^T indicates the transposed matrix of the second matrix S.

In particular, the density of e' must be determined so that it is:

- high enough to prevent attacks aimed at recovering the bond between the public syndrome and the contents of e ';

- low enough to prevent attacks aimed at falsifying valid signatures without however knowing the secret key.

Usefully, the use of the code word c allows avoiding the possibility of falsifying valid signatures by linearly combining previously intercepted signatures.

In particular, it can be observed that in the case of such code word c not being used, then the digital signature e ' can be rewritten as e ' = N(s), where N is a bijective and linear map from the group of public syndromes to the group of the valid signatures.

Consequently, anyone wanting to falsify a signature for a public syndrome s_x could express s_x as a linear combination of previously intercepted public syndromes, i.e., as s_x = su + + ... + s , and falsify a valid signature by combining together in a linear way the corresponding signatures, i.e., as e '_x = e 'ii + e ',2 + ... + e ' .

To avoid such risk, the signer therefore adds the random code word c with weight Wc « n to the error vector e, before multiplication by the matrix S^T. This way, the map N becomes a similar map dependent on the code word c and no longer has as its image a group of valid signatures.

Nevertheless, if the choice of the word is completely random and independent from the file D, the signature obtained for a given file can change every time the file is signed, and this leaves the system open to attacks which exploit many different signatures of the same file.

In order to avoid this vulnerability, the selection of the code word c can be tied to the file to sign, so as to always select the same word c for the same file D. This can be obtained, e.g., using the syndrome vector s as initial seed of the pseudo-random generator used to select the lines of the matrix G to be combined linearly to obtain the word c.

Once the digital signature e' has been determined, the method M envisages the application of the digital signature e ' to the digital file D, to obtain a signed digital file D ' (step 14) and the subsequent sending of the signed digital file D ' (step 15).

The signed digital file D ' can be sent using conventional and typically unsecure transmission means such as, for example, the Internet.

A phase of verification of the signature of a signed digital file D ' using the method according to the invention is schematically shown in the flow chart in figure 2.

In particular, following the receipt of a copy of the signed digital file D ' (step 16) a check is made of the correspondence between a comparison syndrome vector 5 and the syndrome vector s, determined starting from the received digital signature e '.

Preferably, such verification comprises the following steps:

- calculating the hash vector h by means of the public hash function H and starting from the copy of the digital file D (step 17);

- calculating the comparison syndrome vector s by means of the public conversion function Fg and starting from the hash vector h (step 18);

- checking whether the weight wg of the comparison syndrome vector s is equal to the weight w of the sparse vector s (step 19);

- if the comparison syndrome vector s has weight wg different to weight w of the sparse vector s, then the signed digital file D ' is considered not reliable and is therefore rejected (step 22).

Different embodiments cannot however be ruled out wherein, for example, the comparison syndrome vector s is calculated starting from the copy of the digital file D, by means of the public calculation function Y.

Such check also comprises the calculation of the syndrome vector s starting from the received digital signature e ' (step 20).

In particular, the digital signature e ' and the public matrix H' being known, the syndrome vector s is calculated by means of the following formula:

H'^■ e '^T = Q^{A ■} H^■ S^{'1 ■} S^■ (e^T + c^T) = Q^{A ■} H^■ (e^T + c^T) = Q^{~l ■} H^■ e^T = Q^A■ s ' = s.

Subsequently, the method M envisages a control step suitable for checking whether the digital signature e' has weight we' less or the same as a predefined value v, where v = {mrw + w_c)-ms (step 21), where mi is the weight of line and of column of the matrix T while ms is the weight of line and of column of the matrix S.

If the digital signature e ' has weight w_e greater than the value v, then the signed digital file D ' is considered not to be reliable and is therefore rejected (step 22). Afterwards, the comparison is also made between the comparison syndrome vector 5 and the syndrome vector s (step 23).

If the comparison syndrome vector s is different from the syndrome vector s, then the signed digital file D ' is considered not reliable and is therefore rejected (step 22). If the comparison syndrome vector s corresponds to the syndrome vector s, then the signed digital file D ' is considered to be reliable and is accepted (step 24). By way of example only, the figure 3 shows representative parameters of application examples of the method M according to the invention.

In particular, such examples refer to the use of LFGM type error corrector codes.

In particular, by way of example the table in figure 4 shows the dimension values of the public key in the event of QC-LDGM codes being used having parameters with security levels shown in figure 4, where the dimension of the public key is expressed in kibibytes (1 KiB = 1024x8 bits).

It is also pointed out that the method according to the invention is implemented by means of one or more computer programs running on one or more electronic processors.

In particular, the method according to the invention can be implemented by means of a system for the digital signature, composed of one or more hardware devices and/or one or more computer programs, comprising:

- calculation means of the sparse vector s by means of the calculation function Y and starting from the digital file D to sign;

- means of determination of the error vector e starting from the syndrome vector s and by means of the error corrector code C(n, k);

- means of determination of the digital signature e ' starting from the error vector e;

- means of association of the digital signature e ' with the digital file D to obtain the signed digital file D '.

Preferably, the calculation means of the syndrome vector s comprise:

- first calculation means of the hash vector h by means of the hash function ^ and starting from the digital file D to sign;

- second calculation means of the sparse vector s, by means of the conversion function Fg and starting from the hash vector h.

Different embodiments cannot however be ruled out whereby, for example, the calculation means of the syndrome vector s consist of the calculation function Y. Furthermore, the means for determining the error vector e comprise: - selection means of the first matrix Q and of a second matrix S, wherein the first matrix Q and the sparse vector s are such that the private sparse vector s ' defined by the formula

s ' = Q s

has weight w, where Q indicates the first matrix and s indicates the sparse vector;

- means for determining the public matrix H' by means of the formula

H' = Q-^1■ H^■ S^~l

where H' is the public matrix, Q is the first matrix, S is the second matrix and H is the parity matrix of the error corrector code C(n, k);

- calculation means of the error vector e by means of a syndrome decoding algorithm, in such a way that s ' = H ^■ e, where e indicates the error vector.

The means of association of the digital signature with the digital file D comprise:

- selection means of a code word c belonging to the error corrector code C(n, k) where, preferably, the code word c is always the same for a given

- means for determining the digital signature by means of the formula

e ' = (e + c)^■ S^T

where e ' indicates the digital signature vector, e indicates the error vector, c indicates the code word and S^T indicates the transposed matrix of the second matrix S.

The system also comprises means for verifying the correspondence between:

- the comparison syndrome vector s, calculated by means of the public calculation function Y and starting from the received digital file D;

- the sparse vector s, determined starting from the received digital signature e '.

Preferably, the verification means comprise:

- calculation means of a hash vector h by means of the public hash function H and starting from the copy of the signed digital file D ';

- calculation means of the comparison syndrome vector s by means of the public conversion function (Fe) and starting from the hash vector h;

- calculation means of the sparse vector (s) by means of the following formula:

H'^■ e '^T = Q^{A ■} H^■ S^{'1 ■} S^■ (e^T + c^T) = Q^{A ■} H^■ (e^T + c^T) = Q^{A ■} H^■ e^T = Q^A■ s ' = s.

Furthermore, the verification means comprise control means suitable for controlling that the weight of the vector s is equal to the preset value w and that the weight w_e of the digital signature vector e ' is less than or the same as v =

It has in fact been ascertained how the described invention achieves the proposed objects.

In particular, the fact is underlined that the method and the system for the digital signature according to the invention permit avoiding the attacks commonly suffered by a conventional CFS type system.

Furthermore, the method and the system according to the invention permit reducing the decoding complexity and the dimensions of the key and therefore permit a higher processing speed and make possible the use of less computational power, with consequent economic and energy savings.

Claims

1) Method (M) for the digital signature, comprising the following steps:

- defining a public calculation function (7) suitable for calculating a syndrome vector (s) starting from a digital file (D) to sign;

- selecting a private error corrector code (C(n, k));

- calculating said syndrome vector (s) by means of said calculation function (7) and starting from said digital file (D) to sign;

- determining an error vector (e) starting from said syndrome vector (s) and by means of said error corrector code (C(n, k));

- determining a digital signature (e ') starting from said error vector (e);

- associating said digital signature (e ') with said digital file (D) to obtain a signed digital file (D ');

characterized in that said syndrome vector (s) calculated by means of said calculation function (7) is made up of a sparse vector.

2) Method (M) according to claim 1, characterized in that, following the receipt of a copy of said signed digital file (D it comprises the step of verifying the correspondence between:

- a comparison syndrome vector (s), calculated by means of said calculation function (7) starting from the received digital file (D);

- said sparse vector (s), determined starting from the received digital signature (e ').

3) Method (M) according to one or more of the preceding claims, characterized in that said calculation function (7) comprises:

- a public hash function ( );

- a public conversion function (Fe) suitable for converting a hash vector (h) obtained by means of said hash function (.¾) into said sparse vector (s); and in that said step of calculating the syndrome vector (s) comprises the steps of:

- calculating said hash vector (h) by means of said hash function (ti) and starting from said digital file (D) to sign;

- calculating said sparse vector (s), by means of said conversion function (Fe) and starting from said hash vector (h). 4) Method (M) according to one or more of the preceding claims, characterized in that said sparse vector (s) has a predefined value of density of no null elements, a predefined length (r) and a predefined weight w.

5) Method (M) according to one or more of the preceding claims, characterized in that said conversion function (Fe) is suitable for converting said hash vector (h) into said sparse vector (s) according to a group of determined public parameters (Θ) starting from said digital file (D).

6) Method (M) according to one or more of the preceding claims, characterized in that said step of calculating the sparse vector (s) by means of said conversion function (Fe) and starting from said hash vector (h) comprises the step of expanding said hash vector (h) into a sparse vector (s) of bigger dimensions.

7) Method (M) according to one or more of the preceding claims, characterized in that said step of calculating the sparse vector (s) by means of said conversion function (Fe) and starting from said hash vector (h) comprises the step of adding the value of a binary counter (m), thus obtaining a binary vector and the step of converting said binary vector into a predefined length (r) and predefined weight (w) vector.

8) Method (M) according to one or more of the preceding claims, characterized in that said error corrector code (C(n, k)) is defined by means of its own generating matrix (G) and/or by means of its own parity matrix (H in systematic form.

9) Method (M) according to one or more of the preceding claims, characterized in that said step of determining an error vector (e) comprises: - selecting a first matrix (Q) and a second matrix (S), wherein said first matrix (Q) and said sparse vector (s) are such that a private sparse vector (V) defined by the formula

s ' = Q s

has a predefined weight w, where Q indicates said first matrix and s indicates said sparse vector;

- determining a public matrix (H ') by means of the formula

H' = Q ^l H Sr¹ where Η' is said public matrix, Q is said first matrix, S is said second matrix and H is a parity control matrix of said error corrector code (C(n, k));

calculating said error vector (e) by means of a syndrome decoding algorithm, so that s ' = H^■ e, where e indicates said error vector.

10) Method (M) according to one or more of the preceding claims, characterized in that said step of associating the digital signature with the digital file (D) comprises:

selecting a code word (c) belonging to said error corrector code (C(n, k)); determining said digital signature by means of the formula

e ' = (e + c) - S^T

where e ' indicates a digital signature vector, e indicates said error vector, c indicates said code word and S^T indicates a transposed matrix of said second matrix S.

11) Method (M) according to one or more of the preceding claims, characterized in that said step of verifying comprises:

calculating a hash vector (h) by means of said public hash function (ti) and starting from said copy of the signed digital file (D ').

calculating said comparison syndrome vector (s) by means of said public conversion function (Fe) and starting from said hash vector (h);

- calculating said sparse vector (s) by means of the following formula:

H' ^■ e '^T = Q ^{1 ■} H^■ S^{~l ■} S^■ (e^T + c^T) = Q ^{1 ■} H^■ (e^T + c^T) = Q ^{1 ■} H^■ e^T = Q-' s ' = s.

12) Method (M) according to one or more of the preceding claims, characterized in that said step of verifying comprises checking that the weight (wj) of the comparison syndrome vector {§) is equal to the weight (w) of the syndrome vector (s), and/or that the weight (w_e ) of said vector of digital signature (e ') is less than or equal to v = {mrw + w_c)ms.

13) System for the digital signature, comprising:

- calculation means of syndrome vector (s) by means of a calculation function (7) and starting from a digital file (D) to sign;

- means of determination of an error vector (e) starting from said syndrome vector (s) and by means of an error corrector code (C(n, k)); - means of determination of a digital signature (e ') starting from said error vector (e);

- means of association of said digital signature (e ') with said digital file (D) to obtain a signed digital file (D ');

14) System according to claim 13, characterized in that it comprises verification means of the correspondence between:

15) System according to one or more of the claims 13 and 14, characterized in that said calculation function (7) comprises:

- a public hash function ( );

- a public conversion function (Fe) suitable for converting a hash vector (h) obtained by means of said hash function (.¾) into said sparse vector (s); and in that said calculation means of the syndrome vector (s) comprise:

- first calculation means of said hash vector (h) by means of said hash function (ti) and starting from said digital file (D) to sign;

- second calculation means of said sparse vector (s), by means of said conversion function (Fe) and starting from said hash vector (h).