5
votes
Accepted
How is McEliece chosen plaintext secure?
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 ...
- 45.7k
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'$. ...
- 333
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 ...
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 ...
- 21.9k
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 ...
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 ...
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–...
- 47.9k
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$...
- 192
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 ...
- 21.9k
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 ...
- 21.9k
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 ...
- 21.9k
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 ...
- 21.9k
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 ...
- 21.2k
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 ...
- 21.2k
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 ...
- 145k
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-...
- 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 ...
- 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 ...
- 21.2k
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 ...
- 11.6k
1
vote
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 ...
- 145k
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 ...
- 21.2k
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'(...
- 21.9k
Only top scored, non community-wiki answers of a minimum length are eligible