# Tag Info

10

Yes there are. The first publicly accessible McEliece implementation was this one from The Error Correcting Codes (ECC) Page, but it isn't particularly useful for reading, being quite obfuscated. There's INRIA's SECRET group implementation called HyMES that implements something quite similar. FlexiProvider (java library) contains quite a good amount of ...

9

The huge key is definitely an issue. Another is the lack of standardization or recommendations. Should you use OAEP with McEliece, or some other padding? What parameters are actually secure? And so on. Part of the problem is that, while it has been around since the 70s, it was not considered particularly interesting until quite recently—so it probably hasn'...

8

Wide adoption of an asymmetric encryption algorithm, or a digital signature algorithm, requires at least the following: There must exist a reasonably clear standard which unambiguously says where each byte goes. It must cover endianness and similar issues. PKCS#1 is such a standard, for RSA. The algorithm must provide reasonably good performance, in ...

5

An old thread, but I thought it deserved an answer. Information-set decoding In short, the idea behind information-set decoding is to pick a sufficiently large set of error-free coordinates in a sent codeword such that the corresponding columns in the generator matrix form an invertible submatrix. Then, the information sequence can easily be obtained by ...

4

The problem is that the key is essentially random data and thus cannot be meaningfully compressed. Several variations of the McEliece cryptosystem have tried modifying it to produce public keys with special structure which are compressable. However, all such systems have been broken (as far as I know), and it seems that in most cases, adding special ...

4

We looked into post-quantum digital signature schemes for the Tahoe-LAFS "100 Year Cryptography" project but I stopped looking at all but one of them when David-Sarah Hopwood observed that they all rely on a secure hash function to generate a message representative for the digital signature scheme to sign. Therefore, all of them (except for that one) are ...

4

That means a plaintext of length 524 will be encrypted to a ciphertext of length 1024 and then will be sent. Isn't is also an inefficiency? Not really; or at least, that's not an inefficiency we care about. A length of 1024 means, in this context, 1024 bits (or 128 bytes). This compares favorably to RSA (for which a key with a 1024 bit ciphertext has ...

4

Dinh, Moore, Russell have shown that the quantum algorithm (Quantum Fourier sampling) used to attack RSA and ElGamal does not work on McEliece-like crypto systems. (I think) this means, that there are no known algorithms on quantum computers that decrease the complexity of attacks on McEliece, and thus McEliece is just as safe post-quantum computers as it is ...

4

Why the CFS signature is affected Let us review the structure of the CFS signature, which is strongly related to the Niederreiter PKE scheme. In the Niederreiter PKE scheme, a public key is $H \in \mathbb{F}^{n \times k}$, which is a scrambled parity-check matrix of the Goppa codes. A plaintext is a decodable error; for example, we set $S = \{\vec{e} \in \... 3 My understanding is that the attack only works against McEliece with algebraic geometry codes. The paper by Bernstein, Lange and Peters recommends parameters for McEliece with binary Goppa codes, so the attack does not apply against those parameters. 3 As you probably know the public key in McEliece is an$k \times n $binary matrix, encoding a generator matrix for a randomly permuted Goppa code (i.e.$G_{\mathsf{pub}} = SGP$, where$S$is any$k \times k$invertible binary matrix,$G$a$k \times n$generator matrix for an$(n, k, t)$binary Goppa code, and$P$a$n \times n$permutation matrix). ... 3 There is a variant of the Neiderreiter system by Courtois, Finiasz, and Sendrier found in their paper: "How to achieve a McEliece-based Digital Signature Scheme" from Asiacrypt 2001. The Wikipedia article on the Neiderreiter Cryptosystem provides a brief introduction to this signature. There is an element of trial and error in the signing process that is ... 3 I make another online implementation in SAGE. See my entry blog http://juaninf.blogspot.com.br/2013/04/function-make-div-with-id-mycell-sage.html 3 It seems that it is easy to implement it in SAGE -- check this paper. 2 While McEliece could be used like a block cipher, in practice it would much must slower than the standard hybrid approach. McEliece might be relatively fast compared to other public key primitives, it is still quite slow compared to a symmetric cipher. On the Ecrypt performance page, they list the performance of McEliece on various hardware platforms; the ... 2 Does this attack work? Yes, it works. However, "textbook" McEliece was never claimed to be IND-CPA. In fact, it was already published in 2008 by Nojima et. al. in "Semantic Security for the McEliece Cryptosystem without Random Oracles" (PDF). They also propose a mitigation in the paper, which is to simply front-pad the message with sufficiently many ... 1 McEliece public keys need about 100 kByte to 1 MByte depending on the desired security level. 65 kB for 80 bits of security (too low, corresponds to 1024 bit RSA) 150 kB for 112 bits of security 220 kB for 128 bits of security 1000 kB for 256 bits of security The McBits paper contains the following table: 1 A decision problem is to decide if something is true or not (typically phrased in terms of membership of a language). In complexity theory, decision problems are useful for understanding, and most problems can be reduced to a decision problem of some form. However, in everyday life we are usually not trying to solve decision problems. The algorithms in a ... 1 I assume that the paper you have read is the paper by Kobara and Imai in PKC 2001 (or its journal version), which proposed a padding scheme for the McEliece PKE scheme. In Lemma2, the authors showed CPA security of the padded scheme. The first answer is NO. They are not. Let$C(n,t) = \{z \mid z \in \{0,1\}^n, Hw(z) = t\}$, where$Hw(z)$denotes$z\$'s ...

Only top voted, non community-wiki answers of a minimum length are eligible