11

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 ...


5

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 ...


5

I could not reproduce the exact bit complexities from the mentioned paper [1], the authors did not provide the source code. I'm posting my estimators for MMT and BJMM attacks here. The conclusion that BJMM algorithm is worse than MMT is incorrect because MMT is a special case of BJMM. Briefly, BJMM is MMT with no representations of type $1 = 0+0 \bmod 2 $ ...


5

Let $G$ be the public key matrix. With Gaussian elimination, you can find a Matrix $G'$ with $G = (E_k | G')$, where $E_k$ is the identity matrix with dimension $k$. Then, you only have to store $G'$. And $G'$ has the dimension $(n-k) \times k$. Source: German Wikipedia (https://de.wikipedia.org/wiki/McEliece-Kryptosystem)


5

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 random ...


5

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

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.


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 \...


4

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). ...


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 ...


3

The simple answer is that there are two reasons: The lack of a standard implementation. RSA has an acknowledged standard while McEliece doesn't. The size of the key. It's huge! In the multi-megabit range. In terms of today's communication networks, that is bad, but - in my opinion - not too bad. It means it takes time to exchange, but once you have built ...


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 ...


2

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:


2

The modern approach is still to use binary Goppa codes. See, e.g., McBits from 2013: Daniel J. Bernstein, Tung Chou, Peter Schwabe. "McBits: fast constant-time code-based cryptography." Pages 250–272 in Cryptographic hardware and embedded systems—CHES 2013—15th international workshop, Santa Barbara, CA, USA, August 20–23, 2013, proceedings, edited by ...


2

The problem is that you're only referring to plain information set decoding. Indeed, for plain ISD, the complexity of attacking a Goppa code over $\mathbb F_q$ would scale as one would expect with $q$. However, Stern's algorithm for ISD does not scale purely with the code size. Following a geometric distribution, we can express the expected cost of an ISD ...


1

It seems to me that the answer is highly likely to be as follows. I only had a quick look, so buyer beware: So, instead of the recovered permuted error vector $\sigma(e)$ ( $e$ is the plaintext, in Niederreiter and Classic McEliece) needing to be scrambled by the opponent to get the unpermuted error vector $e$, the recovery of the correct error vector (for ...


1

But the matrix is permuted, which is the operation enabling the trapdoor to operate. Thus, the permuted matrix 'hides' the actual matrix $G$. So your extra hiding is unnecessary. The attacker knows the set of permuted generator matrices, but not the actual matrix. The dimensions are huge, as a comparison, say you know that an RSA asymmetric key of 4096 ...


1

Further search at this Round 3 Official Comment Newsgroup - found here https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/official-comments/Classic-McEliece-round3-official-comment.pdf https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/EiwxGnfQgec?pli=1 OP (Kirk Fleming) sets up these estimates mceliece-3488-064 143 ...


1

Classic McEliece is using the Niederreiter T-OWF: The KEM is built conservatively from a PKE designed for OW-CPA security, namely Niederreiter’s dual version of McEliece’s PKE using binary Goppa codes. https://classic.mceliece.org/nist/mceliece-20201010.pdf


1

Forgive me if I missed something. Is $K$ a generator matrix? I believe yes, which means the original code is linear. The translate of the original code by subtracting $y$ is a coset, sometimes called affine subspace. It has almost all the nice properties of a subspace. In particular sums of elements of the translated code are codewords in the original code (...


1

In that case, what are the advantages of McEliece over Paillier encryption? It's not that easy to think of any specific advantages; the public key will be huge (because you would need to expand the code to allow the relatively small initial error vectors to be secure), and those keys are already large enough to begin with. About the only thing that springs ...


1

The weight of the synthetic error vector is $n/2$ where $n$ is the block length, this corresponds to maximum entropy error patterns, with independent probability of error $1/2$ for each bit. The error correcting capability of the code should be much lower for good security. In the original proposal, $n=1024$ and $t=50$ so this should give you some idea. ...


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 ...


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