# Tag Info

Accepted

### Why do Problems for Post-Quantum algorithms have to be NP-Hard?

I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why ...
• 12.5k

### Error-correcting Code VS Lattice-based Crypto

Broadly speaking, it's true that the main difference between "code-based cryptography" assumptions and "lattice-based" assumptions is the noise distribution. There are of course ...
• 721

### Why do Problems for Post-Quantum algorithms have to be NP-Hard?

They don't need to be: isogeny-based cryptography has no connection to any NP-complete problems, as far as I am aware. Generally you want the underlying mathematical problem to be hard, and you can't ...
• 1,135

### 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 ...
Accepted

### Error-correcting Code VS Lattice-based Crypto

Regarding your first paragraph, I would not say that the key difference is the type of noise, because lattice-based cryptography (LBC) uses a lot of different noises: Gaussian, binary, ternary, etc. (...
• 1,080
Accepted

• 21.9k
Accepted

### Use of irreducible Goppa codes in McEliece scheme

As you note, $g(X)$ cannot have any roots in $L$ and so we must perform at least one polynomial GCD to check this. For binary Goppa codes, we must also check that $g(X)$ has no repeated roots, else ...
• 22.8k

### dimension of Goppa codes

From a heuristic point of view (for parameters of cryptographic interest), it's pretty unlikely. Binary $n\times(n-r)$ matrices with random entries have a less than $2^{-n+r}$ chance of being rank ...
• 22.8k

• 22.8k
1 vote

### Cyclic codes as ideals of a quotient ring

Recall that an ideal of a ring is a set of elements from the ring, such that (this is not a complete list of properties, just those important for my answer): We can add any two elements in the ideal ...
• 1,573
1 vote

### How to map the message to the vector of weight t in Niederreiter cryptosystem?

Fun question! We can, in fact, efficiently realise the maximum message space of size $(q-1)^t({n\atop t})$. Let us begin with the case $q=2$. We want to generate a bit string of length $n$ and Hamming ...
• 22.8k
1 vote

### Error-correcting Code VS Lattice-based Crypto

Just to add another quick answer, but one can add "Mersenne Prime"-based crypto to this list, which was initially concieved as a variant of lattice-based crypto where one does "big-int&...
• 12.5k

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