Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
22 views

Minimal secure index of quasi-cyclic codes for code-based cryptography

It is well-known that keys (generator matrices) of code-based cryptography are very large for its practical usage. To reduce them scientists propose to use families of quasi-cyclic codes. I remind ...
6
votes
1answer
81 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 ...
1
vote
1answer
75 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 ...
0
votes
0answers
57 views

Breaking soft McEliece with soft Stern

I am nearly new in Code-based cryptography and I am trying to understand the soft Stern attack in [GJMS17] which the authors used to break the soft McEliece cryptosystem [BSC16]. The description of ...
2
votes
1answer
160 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 ...
1
vote
0answers
29 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?
0
votes
1answer
109 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 ...
1
vote
1answer
173 views

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

Since McElice 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 advantages ...
1
vote
1answer
161 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 ...
1
vote
1answer
102 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 ...
3
votes
1answer
65 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 ...
0
votes
1answer
111 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 ?
1
vote
1answer
98 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 ...
4
votes
1answer
188 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 ...
2
votes
1answer
167 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. ("...
2
votes
0answers
224 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 ...
4
votes
1answer
302 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 ...
5
votes
1answer
238 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?
4
votes
2answers
279 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 ...
4
votes
1answer
921 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 ...
2
votes
2answers
663 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?
10
votes
1answer
203 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 ...
4
votes
1answer
187 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 ...
2
votes
1answer
400 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, ...
1
vote
1answer
133 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 ...
0
votes
1answer
136 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
votes
0answers
128 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$ ...
11
votes
0answers
452 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 ...
3
votes
1answer
184 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 ...
10
votes
4answers
1k 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 ...