Skip to main content

Questions tagged [mceliece]

McEliece cryptosystem is an asymmetric encryption algorithm and is a candidate for "post-quantum cryptography", as it is immune to attacks using Shor's algorithm and — more generally — measuring coset states using Fourier sampling.

Filter by
Sorted by
Tagged with
0 votes
1 answer
109 views

Kyber and Classic McEliece as Public Key Encryption algorithms

Can Crystal Kyber and Classic McEliece be used as public key encryption (PKE) algorithms?. Is there any problem with using these KEM algorithms as PKE for some reason, e.g., doing some holomorphic ...
Anas Ahmad's user avatar
2 votes
1 answer
84 views

The cost of the additive homomorphic encryption of McEliece cryptosystem

Let's have two integer-vectors $v_1$ and $v_2$ that are encrypted by McEliece public key. An intermediate node between the sender and receiver receives the two encrypted vectors $\text{E}(v_1)$ and $\...
Anas Ahmad's user avatar
1 vote
0 answers
36 views

Safety of multiple public keys per McEliece private key?

I noticed that, when deriving a Classic McEliece public key from a private key, randomness is required, and also that this randomness is normally provided at once, during key pair generation. I'm ...
JamesTheAwesomeDude's user avatar
4 votes
1 answer
110 views

"pc" variant of McEliece—what is it?

It looks like the IETF draft specification of Classic McEliece has penciled in separate variants of the algorithm for so-called "pc" and "non-pc" variants (as well as the familiar &...
JamesTheAwesomeDude's user avatar
1 vote
0 answers
45 views

Efficient decoding a code dual to a Goppa code?

Consider a matrix $H \in GF(2)^{a \times b}$ where $b > a$. This defines two linear codes. First, we have the code for which $H$ is the parity check matrix: $$ C = \{ \mathbf{x} \in GF(2)^b | H \...
StephenJ's user avatar
  • 111
0 votes
1 answer
141 views

Syndrome Computation Patterson's Algorithm

Suppose in Patterson's algorithm for the correction of binary Goppa codes, we wish to compute the syndrome polynomial when the defining polynomial is $g(x) = x^{4} + x + 1$, and the error polynomial ...
mathgoonie's user avatar
0 votes
1 answer
78 views

Optimization of the McEliece crypto system

In the normal McEliece proposal, the public key G' = SGP is used, with S beeing non-singular, G Generator Matrix and P permutation Matrix In the White Paper on McEliece with Binary Goppa Codes by ...
fepaul's user avatar
  • 35
0 votes
1 answer
34 views

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

Is there a better way than brute forcing (choose $k=\mathrm{rank}(A)$ first columns - test the determinant, if determinant = 0 choose new column set - there are $\binom nk$ many possibilities which is ...
fepaul's user avatar
  • 35
3 votes
2 answers
99 views

Decrypting McEliece if security assumptions fail

1. G known - how to decrypt Referring to this question: Basic attacks on McEliece; finding S and P (nobody answered) Take a McEliece cryptosystem with public generator matrix $G′=SGP$ where $G$ is a ...
fepaul's user avatar
  • 35
2 votes
0 answers
72 views

McEliece cryptosystem based on Goppa codes and Sidelnikov-Shestakov attack

Hello I am trying to understand why the Sidelnikov-Shestakov attack doesn't work for McEliece cryptosystem based on Goppa codes whereas it works when based of GRS codes. I understood how the attack ...
Paul's user avatar
  • 21
2 votes
1 answer
80 views

What is $z$ in specification of Classic Mceliece?

I have a question about $z$ in Classic Mceliece Algorithm specification. I have no idea about this $z$! In parameter set kem/mceliece348864, Field polynomial $f(z) = z^{12} + z^3 + 1$. is this $z$ in ...
Min's user avatar
  • 21
1 vote
0 answers
30 views

What is the security implication of non-full-rank systematic matrix in McEliece cryptosystem?

The Classic McEliece cryptosystem has the following key generation procedure: Choose a field $\mathbb{F}_{2^m}$, an irreducible polynomial $g(x)$ of degree $t$, and $n$ field elements $\alpha_1, \...
user2249675's user avatar
12 votes
1 answer
720 views

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

This question is potentially relevant to NIST post-quantum cryptography standards, involving code-based cryptosystems such as McEliece, BIKE and HQC. This paper estimates the concrete number of bit ...
Ray Perlner's user avatar
12 votes
0 answers
535 views

Requirements for security against multi-target attacks, for McEliece and other code-based cryptosystems?

This question is potentially relevant to NIST post-quantum cryptography standards, involving code-based cryptosystems such as McEliece, BIKE and HQC. For these cryptosystems, it seems that an attacker ...
Ray Perlner's user avatar
1 vote
1 answer
163 views

RTL solutions to Post quantum candidates

I am looking for RTL implementations of the PQC finalists for KEM (McEliece, Kyber, Saber and NTRU) Saber provides the following repository McEliece provides some code from their website, but as far ...
Daftyler's user avatar
2 votes
1 answer
115 views

What is the extra defense that McEliece 6960119 and 6688128 have that 8192128 does not?

From https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/official-comments/Classic-McEliece-round3-official-comment.pdf The 8192128 parameter set is bigger, but the ...
augustus's user avatar
1 vote
1 answer
367 views

What is the security strength of McEliece variants?

Please help me understand the security strength of McEliece variants prepared for Round 3. I looked at the specifications - https://classic.mceliece.org/nist/mceliece-20201010.pdf - it doesn't have ...
abhi-rao's user avatar
  • 123
1 vote
1 answer
295 views

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

Seemingly, Niederreiter cryptosystem is faster than McEliece, and it can also be used to implement digital signature. Why isn't this scheme appear in NIST post quantum competition?
Evgeni Vaknin's user avatar
2 votes
1 answer
326 views

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

I'm reading about the attacks of the McEliece cryptosystem. I needed to work out a lot of things because most descriptions I have found so far on the internet seems to be quite hand-wavy about the ...
Calmarius's user avatar
  • 280
2 votes
2 answers
378 views

Code used for McEliece cryptosystem

In the McEliece cryptosystem, is choice of the code known to the attacker? And if a structural attack succeeded and the attacker found the generator matrix of the code, how did the attacker decode the ...
Mathsa's user avatar
  • 113
3 votes
2 answers
423 views

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

I don't understand the popularity of the idea of QKD (often coupled with OTP). From what I can tell, a quantum-safe key exchange algorithm like McEliece has just as much security while operating over ...
Evariste's user avatar
  • 124
4 votes
1 answer
353 views

Is McEliece secure with non-binary Goppa codes?

A binary Goppa code with codewords of length $n$ bits that can fix $t$ errors with a polynomial over $GF(2^m)$ can encode $k = n - mt$ bits long data. That is one needs to add $mt$ check bits to fix $...
Calmarius's user avatar
  • 280
7 votes
1 answer
375 views

Why doesn't “Classic McEliece” need scrambling?

The original McEliece scheme uses two random matrices S and P to scramble the generator matrix and uses $\mathsf S·\mathsf G·\mathsf P$ as the public key. The Niederreiter variant also does about the ...
Marian's user avatar
  • 201
1 vote
1 answer
226 views

McEliece cryptosystem

There is something intriguing me about this cryptosystem. That is : Let $(S, G, P)$ be the secret key: $S$ : invertible matrix $G$ : generator matrix for some linear code $C$ $P$ : permutation ...
Younes's user avatar
  • 111
2 votes
1 answer
364 views

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

I understand that the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece, almost around the same time RSA came about. Why has the McEliece cryptosystem ...
Nathan Aw's user avatar
  • 2,277
1 vote
0 answers
52 views

Why in the Rao-Nam private key version of McEliece scheme, P matrix is multiplied after adding error vector?

The private key version of McEliece known as Rao-Nam scheme, the encryption is done as c = (mSG + e)P. What is the need for applying permutation matrix on the error vector?
Surya's user avatar
  • 91
0 votes
1 answer
222 views

How can we prove that the scrambled G matrix in McEliece cryptosystem preserves the minimum distance properties of G matrix?

In McEliece cryptosystem, G matrix is scrambled using S and P so that scrambled G matrix is G' = SGP. Here G is the generator matrix of a linear code and after scrambling it is converted into another ...
Surya's user avatar
  • 91
2 votes
1 answer
370 views

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

Since the McEliece cryptosystem is linear, if matrix G is kept constant for different plaintexts, it can be used for linearly combining the corresponding ciphertexts. In that case, what are the ...
Surya's user avatar
  • 91
1 vote
1 answer
265 views

Code families in McEliece cryptosytem

What are the families of codes frequently used in McEliece cryptosystem or its variants? I know that binary Goppa codes were used in the original system but many codes with efficient decoding ...
Root's user avatar
  • 111
1 vote
1 answer
159 views

McEliece parameter tuple (n, k, t) through BouncyCastles (m, t, poly) [closed]

I am using BouncyCastles Java API and want to use McEliece encryption. After browsing through various paper for finding good parameters (e.g. How to choose McEliece's parameters?) I am now having the ...
Ph3n1x's user avatar
  • 111
3 votes
1 answer
139 views

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

In the symmetric version of McEliece cryptosystem, we are adding intentional error vector during encryption. During decryption, first, we cancel the effect of error vector and then multiply the ...
user44122's user avatar
1 vote
1 answer
185 views

key size of public key in McEliece

The length of public-key matrix in McEliece cryptosystem is $n \times k$. Then the key size is $\frac{n \times k}{8}$ bytes. But I find that the key size is $\frac{(n-k) \times k}{8}$ bytes. why ?
Nour28's user avatar
  • 23
1 vote
1 answer
142 views

McEliece variants that support signatures

Besides the Niederreiter cryptosystem, are there any other variants that support digital signatures? Can any of them sign arbitrary signatures unlike the Niederreiter cryptosystem? What are the key ...
Melab's user avatar
  • 3,655
6 votes
1 answer
456 views

How is McEliece chosen plaintext secure?

Suppose a challenger creates a McEliece encryption system where there is a public key consisting of a matrix $G$ representing some linear code, and a number $t$ for the number of errors. Then the ...
Sam Jaques's user avatar
  • 1,202
2 votes
1 answer
283 views

Efficiency of McEliece cryptography (ciphertext expansion)

Most of the sources say McEliece has never gained acceptance because of its large size of private and public keys. However I have never heard about the size (or length) of its ciphertext. ("...
faith's user avatar
  • 165
3 votes
0 answers
413 views

How to choose McEliece's parameters?

At the time of this writing, there are 3 sources for parameters for the McEliece public-key cryptosystem out there. The first paper is the original McEliece paper ("A Public-Key Cryptosystem based on ...
SEJPM's user avatar
  • 46.1k
4 votes
1 answer
578 views

Implementing the Mceliece Encryption - making the Generator Matrix

I am working on an implementation of the Mceliece Encryption system (MCE) and the Niederreiter encryption system. I have been through the basics of finite fields, polynomial arithmetic and some coding ...
gautam's user avatar
  • 78
5 votes
1 answer
359 views

McEliece and cryptanalysis

What is the computational time to break McEliece on a quantum computer? I've seen that polynomial time algorithms exist, but for special conditions. What about the general case?
Dingo13's user avatar
  • 2,867
4 votes
2 answers
481 views

Basic attacks on McEliece; finding S and P

Take a McEliece cryptosystem with public generator matrix $G' = S G P$ where $G$ is a generator of a secret code with known fast decoding (not necessarily a Goppa code over $\mathbb{F}_2$), $S$ is ...
QuadrExAtt's user avatar
7 votes
1 answer
2k views

McEliece information set decoding attack vulnerability

Wikipedia states that McEliece is open to "information set decoding attack". What is an "information set decoding attack" and how serious is the vulnerability? (is it just a matter of choosing proper ...
bbozo's user avatar
  • 277
3 votes
2 answers
2k views

McEliece key size

There's a lot of references about McEliece key size being the barrier for proper usage of the algorithm, exactly (or roughly) how large are the keys?
bbozo's user avatar
  • 277
11 votes
1 answer
251 views

Is the Couvreur et al. polynomial time attack on McEliece practical?

There's a new e-print out on arXiv titled "A Polynomial Time Attack against Algebraic Geometry Code Based Public Key Cryptosystems" by Alain Couvreur, Irene Márquez-Corbella and Ruud Pellikaan: "We ...
fractal's user avatar
  • 121
4 votes
1 answer
254 views

What is the impact of the Goppa code distinguisher on the CFS and McEliece?

What is the impact of the distinguisher for the high-rate Goppa codes (as published in "A Distinguisher for High Rate McEliece Cryptosystems") on the CFS signature scheme and the McEliece/Niederreiter ...
lumun's user avatar
  • 41
2 votes
1 answer
455 views

McEliece Public Key Encryption

The definition of Public Key Encryption(PKE) say that: A PKE scheme is a triple of probabilistic polynomial time algorithm (PPT) (Gen,Enc,Dec). The definition of PPT say: In complexity theory, ...
juaninf's user avatar
  • 2,711
1 vote
1 answer
157 views

Is there any restriction in using lossless compression algorithms for huge key sizes?

I'm studying McEliece and Multivariate Public Key cryptographic systems. The main problem here is the huge key size. Is there any restriction in using lossless compression algorithms to fix this ...
juaninf's user avatar
  • 2,711
0 votes
1 answer
176 views

Sematically Secure McEliece

I am read the Lemma 2 (pp13) in the paper "Kazukuni Kobara and Hideki Imai: Semantically Secure McEliece Public-Key Cryptosystems –Conversions for McEliece PKC– (PKC 2001)". Related to the question "...
juaninf's user avatar
  • 2,711
2 votes
0 answers
151 views

PKC McEliece + $S$ + $P$ [closed]

I am trying implement the McEliece crytosystem in SAGE. My question is How I will be able to choose the appropriate matrix $S$ and $P$?. I ask this because when I trying obtain the vector $\hat{m}=mS$ ...
juaninf's user avatar
  • 2,711
12 votes
1 answer
697 views

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

If we assume that the support for an irreducible binary Goppa code $\gamma_1, ..., \gamma_n$ is publicly known, when is it possible to efficiently decode the code? I know it's possible if one knows ...
Zuzana's user avatar
  • 121
3 votes
1 answer
230 views

McEliece for streaming data

Under the assumption that there exists a real-world implementation of the McEliece scheme, could it be applied to streaming data as is? By that I mean in 'block cipher mode'? I've read that McEliece ...
publixo's user avatar
  • 31
12 votes
4 answers
2k views

Is key size the only barrier to the adoption of the McEliece cryptosystem, or is it considered broken/potentially vulnerable?

A recent paper showed that the McEliece cryptosystem is not, unlike RSA and other cryptosystems, weakened as drastically by quantum computing because strong Fourier sampling cannot solve the hidden ...
user avatar