Abstract

McEliece is one of the oldest public-key cryptosystems and is believed to be able to withstand quantum computing attacks. It is widely believed, that code-based cryptosystems like McEliece are not suitable for digital signatures. In this paper, the difficulties of code-based signatures are pointed out and with the CFS signature scheme, a possible approach is proposed. For this scheme, an overview of the algorithm and secure parameters, as well as the statistics like signature length, public key size, signature generation cost and time, and verification costs are given.

1         Introduction

Quantum computing is a field in research, that has gained much attention in recent years. An establishment of quantum computers might be a big constraint to the confidentiality and security of digital communications as these devices will be able to crack many public-key cryptosystems. On the way to a fully connected world, public-key cryptosystems have become essential, of which many would become useless with the existence of quantum computing.

Almost all asymmetric cryptosystems base on one of the following three mathematical concepts. Firstly, integer factorization is used for the RSA cryptosystem, on which for example web browsers, e-mail encryption and VPNs rely. Discrete logarithms are exploited for the ElGamal and Di e-Hellman cryptosystems and the third concept is the elliptic-curve discrete logarithm, like in Curve25519, applied in e.g. WhatsApp, the Tor browser or iOS. All three concepts can be solved by Peter Shor’s Algorithm [1], if a quantum computer with sufficient computational power is available. This would create the need for new cryptosystems.

In the course of this paper, it will be shown how the Niederreiter scheme [4], which is a dual form of the McEliece cryptosystem [2], needs to be transformed to be made suitable for a digital signature. This will lead to the CFS signature scheme.

2         Preliminaries

2.1         Public Key Cryptosystems

Let bold letters denote vectors and bold upper case letters denote matrices. A public key cryptosystem is de ned by its private key and the inherent public key. A ciphertext y is the encrypted message, which is generated by applying the public key to the plaintext x. The only way to recover the plaintext is applying the private key to the ciphertext.

2.2         Digital signatures

A digital signature is a bit pattern, that is created by applying a private function or key to a message, which needs to be very di cult to do without knowing the private information, but must be easy to verify with a public key. This public key has to be a one-way function, where a one-way function F denotes a function that is easy to compute but di cult to invert [5]. A signature is created by a combination of the document D and the public key. Such a signature s is what would be the plaintext x in public key encryption and is created by applying the private key to the ciphertext y. Such a signature can then be verified by comparing the resulting hash value from the received document D’ and the result from applying the public key to the signature like done for encryption. If both values are equal, the signature is valid.

2.3         McEliece’s and Niederreiter’s schemes

The binary eld F2 is de ned as the eld with the elements {0,1}. The set of all m × n matrices over F2 is denoted by and  is de ned as . A binary linear [n, k, d] code C is a k-dimensional linear subspace of the vector space with minimum Hamming distance d, where the minimum Hamming distance d of a code C is de ned as the minimum number of differing symbols in any two different codewords c_i. A generator matrix G of linear code C is a k × n matrix over F2, where its row space generates the code. The codeword c is achieved by encoding the plaintext x with the generator matrix c = x · G. For a code C, the set of vectors

is called dual code. An (n − k) × n matrix H over F2 is called a parity-check matrix of a binary [n, k, d] code C if it is a generator matrix of the [n, n - k, d^⊥] dual code C^⊥. Furthermore, the parity-check matrix has the property that for any c ∈ C: c · H^T = 0, which implies that G · H^T = 0. For a vector a and a parity-check matrix H of a code C, the vector s := a · H^T  is called the syndrome s of a.

The McEliece [2] system is a public key cryptographic system, where a message is encrypted by adding a random error vector to a codeword. The ciphertext y is calculated by y = xG+e = c+e, with w_H(e) = t. The decryption is done by using Goppa decoding as a trapdoor function to correct the added errors.

The Niederreiter [4] cryptosystem is a dual version of the McEliece cryptosystem, where the public key is a parity-chack matrix H’ of code C’ equivalent to the secret code. This results in a syndrome of weight t as ciphertext. The decryption is done with a syndrome decoder, which has the same security as the decoding in the McEliece scheme. A comparison of both systems is given in Table 1.

Table 1: Overview on McEliece and Niederreiter cryptosystems

McElieceNiederreiter

public keyGH

plaintext x ∈ F₂^kx ∈ F₂ⁿ,w_H(x) = t

ciphertext y = xG + e, w_H(e) = ty = Hx^T

ciphertext spaceF₂ⁿF₂^n−k

For both schemes, the security relies on the hardness of decoding an error-correcting code, which is known to be NP-hard [6] and also no sub-exponential attacks are known [7].

2.4         Complete Decoding

Complete decoding is a concept, where every ciphertext y is decoded by finding the nearest codeword c. While for in bounded minimum distance decoding with minimum distance d, d/2 - 1 errors can be corrected by finding a codeword with at most d/2 - 1 different bits, in complete decoding, every is decrypted to a codeword. This is done by finding the lowest distance of a codeword c to the given ciphertext y.

3         Obstacles for straight-forward implementation of a digital signature based on McEliece

Code-based cryptosystems, in general, have some issues for implementing them as a digital signature. For the McEliece code in particular, there are two problems to solve. First of all, as in the signature generation a random bit word needs to be decoded like an instance of ciphertext, this bit word needs to be decryptable. For a t-error correcting code, this is feasible, if the error vector, which is also random has a maximum Hamming weight of t. Therefore, it is very unlikely to get a decodable bit word by hashing a document. In order to achieve decryption, the CFS signature scheme uses complete decoding and adopts the code parameters, which will be explained in more detail in IV.

Another big disadvantage for code-based cryptosystems, in general, is, that they have very large public keys. For McEliece, the public key is the generator matrix G, which is a binary matrix of size k × n, while for the Niederreiter scheme, the public key is the parity check matrix, which has the size (n−k)×n. With classical McEliece parameters (n = 1024,k = 524,t = 50) the resulting sizes are at least 500 kbits. However, it is possible to transform the parity and generator matrices H and G into systematic form with G = [I|A] and H = [ I | B ], for which only A or B respectively need to be published and stored. The new public keys then are both of size (n−k)×k and can therefore be represented with 262 kbits for the afore-mentioned classical McEliece parameters.

4         CFS Signature scheme

4.1         Key generation

The CFS signature scheme [3] builds on the Niederreiter scheme [4]. In the following let r, n, k and t be integers and r = n-k. For a Goppa code of length n and dimension k, let H₀ be a r × n parity-check matrix like defined in 2.C, for which there exists an efficient syndrome decoder Dec_C that can decode syndromes of maximal weight t. The public key is generated by H = S · H₀ · P, where S is an r × r uniformly at random non-singular matrix and P is a uniformly at random permutation matrix of size n×n. Decryption is then done by P⁻¹ · Dec_C(S⁻¹ · s). A permutation matrix has one entry per line and column and thus only permutes the columns of H₀ here. Furthermore, the inverse of a permutation matrix is its transpose.

Therefore, the public key is:

1. The scrambled r × n parity-check matrix H
2. The error correction capability t

The private key is:

1. The original parity-check matrix H₀
2. The random non-singular r × r matrix S
3. The n × n permutation matrix P

4.2         Signature Algorithm

The CFS signature scheme [3], named after its authors Nicolas Courtois, Matthieu Finiasz, and Nicolas Sendrier, is a digital signature scheme based on the Niederreiter scheme. Let a Hash function h(·) denote a function that maps data of arbitrary size to a binary vector of size r. In the CFS signature, the hash value of the document s  to sign is treated as a syndrome in the Niederreiter’s scheme. For a noisy codeword y = c + e a syndrome is the same as s = y · H^T = (c + e) · H^T = e · H^T since G · H^T = 0. Decoding thereby means finding the error vector e. Let ˜e = e · P^T, then ˜s, which can be decoded if wt(e) = wt(e˜) ≤ t. The signature z is then the error vector e that is achieved by undoing the permutation of ˜e with P^T by multiplying it with P^T−1 = P.

Such a syndrome s with random a errors is very unlikely to be decodable. For generating a decodable syndrome an approach to convert an incomplete decoder to a complete decoder is used. One way, therefore, is to flip δ random bits and then try to decode the new codeword. If these δ bits appear to be errors, the bit flips reduce the number of errors from a to a − δ. This is done until the syndrome after the bit flips has a−δ ≤ t errors, which can be decoded by the trapdoor function. In [3] it was proposed to concatenate the counter i to s and hash to try to decode the syndrome s_i = h([ s | i ]). Starting at i = 0, the counter is increased by 1 if s_i is not decodable. Increasing the counter always results in an s_i with new bits are flipped compared to the first syndrome s₀. For the first decryptable s_i, the index i is denoted i₀ and the trapdoor function is applied to calculate the word z, such that Hz^T = s_i0, where H denotes the public key. The signature is formed by a concatenation of z and i₀ because i₀ is needed in the verification algorithm. The steps of the signature creation can be followed in Figure 1, which shows a flowchart of the generation algorithm.

Figure 1: Flow chart of the signature generation in the CFS scheme

4.3         Veri cation Algorithm

In order to verify the signature, the value s₁ = Hz^T is computed with the signature z and the public key H. Furthermore, the hash of the document D and counter index i₀ is computed to s₂ = h([ h(D) | i₀ ]. If s₁ and s₂ are equal, the signature is valid.

4.4         Establishment of appropriate parameters

Appropriate parameters should create a good security level together with adequate costs and runtimes. The signature creation depends on the probability P of a random syndrome s_i to be decodable since the decoding algorithm will have to be repeated 1/P times on average. This probability can be calculated as_! as there exist N_tot = 2^n−k = 2^mt = n^t different syndromes in total with decodable syndromes. This time dependency on t! shows that a secure set of parameters with small t would give a good trade-off.

5         Possible Attacks on the CFS signature

For signature schemes there exist two kinds of attacks in general, key recovery attacks and signature forgeries without knowledge about the private key. Known key recovery attacks against McEliece type cryptosystems have been less efficient than decoding attacks [9]. Therefore, the focus of this section will lie on signature forgeries, where the goal is to nd a valid signature without knowing the private key.

5.1         Information Set Decoding

Information Set Decoding (ISD) is an algorithm that is efficient for Syndrome Decoding (SD) problem with few solutions [9]. ISD builds on the CanteautChabaud algorithm [11], which is an algorithm for finding minimum-weight words in large linear codes. The work factor for finding a minimum-weight word in a [n,nR] binary-code with the Canteaut-Chabaud algorithm can be approximated by W_Opt ≈ 2^ncH2(R+R0)+d where c = 0.12, d = 10 and R₀ =

3.125 · 10⁻² [11].

5.2         Generalized Birthday Algorithm

The Generalized Birthday Algorithm (GBA) builds on the classic birthday problem, where the task basically is to nd matches from different lists [10]. the goal for applying GBA to the CFS signature is then to just nd any pair of syndrome s_i and z that match together. This is done by comparing lists with target syndromes. The work factor of GBA against a CFS signature is given by

W = L*log(L) with

5.3         Example Parameters and their Securities

In order to find a set of secure parameters, the workfactors of the Canteaut and Chabaud attack and GBA are compared for different parameter sets (n,t).

Table 2: Workfactors for Canteaut and Chabaud attack and GBA

Values for Canteaut and Chabaud attack are taken from [3] and ² values for GBA from [9]; ³ Last row is for three parallel signatures

From Table II, it can be observed that all shown parameter sets fulfill an 80 bit security level for the Canteaut and Chabaud attack but are far away from fulfilling it for GBA. In [9], it is proposed to use two or three signatures in parallel by concatenating to one big signature, which improves the security against GBA as the last row in Table II shows. For the set (2¹⁷,10), 2 parallel signatures are enough for an 80 bit security level [9].

6         Practicality of the CFS signature

6.1         Costs and Sizes

This calculation of costs and sizes will be shown for the parameter set (2¹⁶,9) as it provides the smallest costs and sizes and applying the three signatures in parallel it also o ers an acceptable security level. When three signatures in parallel are used, the signature length is tripled and the signature cost is increased by approximately 2^1.5 [9].

6.1.1         Signature length

After the choice of parameters, the signature length can also be determined. Similar to the plaintext in the Niederreiter scheme, the word z for the signature scheme has a maximum Hamming weight of t in a t-error correcting code.

Therefore,  different words z with Hamming weight t = 9 and length n = 2¹⁶ are possible. This means that z can be compressed from 2¹⁶ bits to a 126 bit counter that contains the positions of non-zero bits. With the counter i₀, which has an irreducible length of on average log₂ 9! ≈ 18.4 bits. The expected signature length would then be 126 + 18.4 = 144.4bits. Together with the data compression of the word z, it has to be mentioned that this is only possible using the Niederreiter scheme as there z has Hamming weight t, which is not the case in the original McEliece scheme. With the McEliece scheme, the signature length would be k bits plus the length of the counter.

For the length of the counter i₀, it has to be mentioned, that the 18.4bits are the average and it is not possible to nd an upper bound for the number of decoding attempts. However, adding ve extra bits for the counter reduces the probability of failing to sign a message to less than 2⁻⁴⁶.

6.1.2         Signature cost

As already mentioned in IV.D, it takes t! decoding attempts on average. The decoding algorithm is Goppa Decoding, of which in [8] the complexity can be reduced to O(nlgn) when Goppa codes are constructed in dyadic form instead of the generic complexity of O(n²). In the CFS signature scheme, this leads to a complexity of O(t! · nlgn) instead of O(t! · n²) for generic Goppa codes.

6.1.3          Veri cation cost

For a hash value s of the message and the error pattern z, s = Hz^T. Thus, adding the t corresponding columns of H is enough to compute y = Hz^T and if y equals s, the signature is accepted. The cost of such a verification sums up to t column operations, where a column operation typically is one access to a table together with an operation like an addition or a comparison. Since this is very easy to compute, in [3] and [9] the signatures are shortened on the cost of a more complex verification, which can still be completed in the range < 1ms.

6.1.4         Public key size

The only storage consuming part of the public information is the parity check matrix, which the systematic form of a parity-check is the most e cient way to store it. Then it has (n − k) × k binary entries and therefore needs (n − k) × k bits of storage as described in II.

6.2         Overview of practical values of the CFS signature

Table 3: Overview of practical values of the CFS signature

¹ The signature generation time is to give an order of magnitude and bases on the assumption, that the decoding algorithm from [3] can perform one million decodings in one minute with recent advances of computational power instead of a few minutes, where one minute again is an estimate

² approximate calculated values for the number of entries of the parity check matrix in systematic form

³ values for 3 parallel signatures for the sets (2¹⁶,9) and (2¹⁵,10), and two parallel signatures for (2¹⁷,10); Values are taken from [9] ⁴ Size in bits with all reductions applied [9]

⁴ The estimated signature generation times from Table III show, that in order to achieve a reasonable signature scheme (good security and convenient signature generation time), public key sizes of a few Mbits (a few hundred kbytes) need to be accepted. In particular, a trade-o between signature generation time, signature length and public key size needs to be found. For finding such trade-off, the parallel signature scheme proposed in [9] is very helpful, since it increases the security without changing the key size and the generation time is much less affected compared to increasing the error capability t of the decoder.

7         Conclusion

After the description of the issues of code-based digital signatures, namely large public keys and low probabilities of decoding success, it is shown how these can be approached with the CFS signature scheme, a digital signature scheme based on the McEliece cryptosystem. On one hand, the proposed signature scheme has a large public key and high signature generation cost, where a trade-o needs to be selected with the choice of parameters as shown in Table III. On the other hand, the signature length and verification costs can be kept very small.

References

[1] P. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review, 1999, Vol. 41, No. 2:pp 303-332. 1999

[2] J. McEliece. A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep., Jet Prop. Lab., California Inst. Technol., Pasadena, CA, pp. 114-116, January 1978.

[2] Courtois, M. Finiasz, and N. Sendrier. How to achieve a McEliecebased digital signature scheme. Cryptology ePrint Archive, Report 2001/010, February 2001. http://eprint.iacr.org/ et RR-INRIA 4118.

[2] Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Prob.Contr. Inform. Theory, 15(2):157-166, 1986.

[2] Merkle. A Digital Signature Based on a Conventional Encryption Function. Advances in Cryptology CRYPTO ’87. Springer Berlin Heidelberg. Berlin, Heidelberg. pp. 369-378. 1988

[2] R. Berlekamp, R. J. McEliece, and H. C van Tilborg. On the inherent intractability of certain coding problems. IEEE Transaction on Information Theory, 24(3), May 1978.

[2] Canteaut and F. Chabaud. A new algorithm for finding minimum-weight words in a linear code: Application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511. IEEE Transaction on Information Theory, 44(1):367-378, January 1998

[2] Misoczki,P. Barreto. Compact McEliece Keys from Goppa Codes. In: Jacobson M.J., Rijmen V., Safavi-Naini R. (eds) Selected Areas in Cryptography. SAC 2009. Lecture Notes in Computer Science, vol 5867. Springer, Berlin, Heidelberg. (2009)

[2]  Finiasz. Parallel-CFS Strengthening the CFS McEliece-Based Signature Scheme. In: SAC 2010 [18], pp. 159 170 (2011)

[2]  D.Wagner. A Generalized Birthday Problem. In: Yung M. (eds) Advances in Cryptology CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. (2002)

[2]  A. Canteaut and F. Chabaud. A new algorithm for finding minimumweight words in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511. IEEE Transactions on Information Theory, vol. 44, no. 1, pp. 367-378, Jan. 1998. doi: 10.1109/18.651067