Skip to main content
5 votes
Accepted

key size of public key in McEliece

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'$. ...
Christine's user avatar
  • 353
5 votes

Number of bit-operations required for information set decoding attacks on code-based cryptosystems?

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 ...
Elena Kirshanova's user avatar
3 votes
Accepted

Decrypting McEliece if security assumptions fail

If you know $G$ and $G'$ you can recover typically recover $P$ from the support splitting algorithm. Note that the support-splitting algorithm is independent of the bases used to represent the two ...
Daniel S's user avatar
  • 24.1k
3 votes
Accepted

"pc" variant of McEliece—what is it?

This is the so-called "Plaintext Confirmation" variant, and indeed it was submitted as "the" algorithm in rounds 1–3 of the competition, but was replaced in round 4 with a simpler ...
JamesTheAwesomeDude's user avatar
3 votes

McEliece variants that support signatures

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 ...
Luiz Carvalho's user avatar
3 votes

Why has the McEliece cryptosystem not gained much acceptance, but now is a candidate for post-quantum cryptography?

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 ...
Adrian Challinor's user avatar
3 votes
Accepted

Kyber and Classic McEliece as Public Key Encryption algorithms

Yes and no. Kyber and Classic McEliece refer to specific protocols which are KEMs, so in an obvious and boring sense neither one works as a PKE since a KEM does not take a message as an input. But, ...
Sam Jaques's user avatar
  • 1,202
2 votes
Accepted

How to choose rank(A) independant columns of matrix A efficiently

Compute the row echelon form of the matrix and select the pivot columns. Computing the row echelon form of a $m\times n$ matrix will take $O(m^2n)$ field operation, which is pretty straightforward. If ...
Daniel S's user avatar
  • 24.1k
2 votes

The cost of the additive homomorphic encryption of McEliece cryptosystem

You should decrypt and add. Let us take a simple McEliece set up where the public key is $k\times n$ matrix $\hat G$ and a $k$-long bit vector $\mathbf m$ is encrypted as $\mathbf m\hat G\oplus \...
Daniel S's user avatar
  • 24.1k
2 votes
Accepted

Can the McEliece cryptosystem be used as an additively homomorphic encryption scheme?

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 ...
poncho's user avatar
  • 148k
2 votes

Code families in McEliece cryptosytem

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–...
Squeamish Ossifrage's user avatar
2 votes
Accepted

Is McEliece secure with non-binary Goppa codes?

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$...
d125q's user avatar
  • 192
2 votes

Syndrome Computation Patterson's Algorithm

We treat $g(x)$ as a polynomial in $\mathbb F_{16}[x]$ and compute $\frac1{x+\gamma^3}\pmod{g(x)}$ using the extended Euclidean algorithm to find $u(x)$ such that $u(x)(x+\gamma^3)+v(x)g(x)=1$. The ...
Daniel S's user avatar
  • 24.1k
1 vote

Optimization of the McEliece crypto system

The Paterson decoding algorithm will work for cipher texts $\mathbf c=\mathbf m G'+\mathbf e$, because Paterson only needs you to know the correspondence between field elements and columns. This ...
Daniel S's user avatar
  • 24.1k
1 vote

What is $z$ in specification of Classic Mceliece?

Yes, $z$ is the root of the polynomial used to construct the field (in the case of mceliece 348864 this field is $\mathbb F_{2^{12}}$ and the polynomial is as quoted). I'm not sure to which pic you ...
Daniel S's user avatar
  • 24.1k
1 vote

RTL solutions to Post quantum candidates

To answer your second question: are there normally standards when it comes to implementation, or are they implemented how the user sees fit? Implementers are given a great deal of flexibility; we ...
poncho's user avatar
  • 148k
1 vote

What is the security strength of McEliece variants?

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-...
abhi-rao's user avatar
  • 123
1 vote

why Niederreiter cryptosystem is not a candidate in NIST PQC competition?

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 ...
ambiso's user avatar
  • 706
1 vote

How can the Stern's algorithm be used to attack McEliece?

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 ...
kodlu's user avatar
  • 22.7k
1 vote

Code used for McEliece cryptosystem

This is a (general, mathematical) perspective which may not be useful for all readers, but I still find particularly nice. It comes via analogy with the Lattice Isomorphism Problem. This is a ...
Mark Schultz-Wu's user avatar
  • 13.5k
1 vote

How is QKD (Quantum Key Distribution) advantageous over McEliece/AES?

QKD is "popular" as it doesn't rely on an algorithm that can possibly be broken. McEliece doesn't have a security proof. So although it is thought to be secure after many years of analysis, ...
Maarten Bodewes's user avatar
  • 93.2k
1 vote

Why doesn't “Classic McEliece” need scrambling?

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 ...
kodlu's user avatar
  • 22.7k
1 vote

McEliece cryptosystem

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 ...
kodlu's user avatar
  • 22.7k
1 vote

Efficient decoding of irreducible binary Goppa codes and the role of matrix P in McEliece cryptosystem

If one knows $\gamma_1,\cdots,\gamma_n$ and $g(x)$ then for any $n$-long binary vector $V$ one can form the polynomial $$v(x):=\prod_{i:V\cdot e_i} (x-\gamma_i)$$ and the syndrome polynomial $s(x)=v'(...
Daniel S's user avatar
  • 24.1k
1 vote

What are the properties of error vector used in symmetric McEliece cryptosystem?

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 ...
kodlu's user avatar
  • 22.7k

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