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.
50 questions
0
votes
1
answer
249
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 ...
- 33
2
votes
1
answer
93
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 $\...
- 33
1
vote
0
answers
38
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 ...
4
votes
1
answer
120
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 &...
1
vote
0
answers
66
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 \...
- 111
0
votes
1
answer
152
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 ...
0
votes
1
answer
95
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 ...
- 35
0
votes
1
answer
37
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 ...
- 35
3
votes
2
answers
108
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 ...
- 35
2
votes
0
answers
103
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 ...
- 21
2
votes
1
answer
90
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 ...
- 21
1
vote
0
answers
34
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, \...
- 278
12
votes
1
answer
744
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 ...
- 341
12
votes
0
answers
539
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 ...
- 341
1
vote
1
answer
197
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 ...
- 51
2
votes
1
answer
121
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 ...
- 87
1
vote
1
answer
437
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 ...
- 123
1
vote
1
answer
323
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?
- 1,105
2
votes
1
answer
390
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 ...
- 280
2
votes
2
answers
414
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 ...
- 113
3
votes
2
answers
469
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 ...
- 124
4
votes
1
answer
379
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 $...
- 280
7
votes
1
answer
404
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 ...
- 201
1
vote
1
answer
244
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 ...
- 111
2
votes
1
answer
392
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 ...
- 2,337
1
vote
0
answers
54
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?
- 91
0
votes
1
answer
237
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 ...
- 91
2
votes
1
answer
381
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 ...
- 91
1
vote
1
answer
279
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 ...
- 111
1
vote
1
answer
162
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 ...
- 111
3
votes
1
answer
153
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 ...
- 31
1
vote
1
answer
192
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 ?
- 23
1
vote
1
answer
145
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 ...
- 3,705
6
votes
1
answer
502
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 ...
- 1,614
2
votes
1
answer
308
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. ("...
- 165
3
votes
0
answers
431
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 ...
- 46.4k
4
votes
1
answer
623
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 ...
- 78
5
votes
1
answer
374
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?
- 2,897
4
votes
2
answers
508
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 ...
- 328
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 ...
- 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?
- 277
11
votes
1
answer
257
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 ...
- 121
4
votes
1
answer
269
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 ...
- 41
2
votes
1
answer
462
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, ...
- 2,761
1
vote
1
answer
163
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 ...
- 2,761
0
votes
1
answer
178
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 "...
- 2,761
2
votes
0
answers
152
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$ ...
- 2,761
12
votes
1
answer
713
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 ...
- 121
3
votes
1
answer
233
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 ...
- 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 ...
user46