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
  • 23k
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
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
  • 23k
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
  • 23k
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
  • 23k
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
  • 23k
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
  • 92.4k

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