9 votes
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 ...
Mark's user avatar
  • 12.5k
7 votes

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 ...
pscholl's user avatar
  • 721
6 votes

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 ...
Sam Jaques's user avatar
  • 1,135
5 votes

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 ...
Elena Kirshanova's user avatar
5 votes
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. (...
Thomas Prest's user avatar
  • 1,080
4 votes
Accepted

Patterson's decoding algorithm for Goppa codes

First note that $$\frac{\sigma'(x)}{\sigma(x)}=\sum_{i\in B}\frac 1{x-L_i}$$ and that if we write $C$ for the bit positions of a codeword, the Goppa code is defined by $$\sum_{i\in C}\frac 1{x-L_i}\...
Daniel S's user avatar
  • 22.8k
3 votes
Accepted

Cyclic codes as ideals of a quotient ring

The ideal property gives an equivalence of polynomials upon division modulo $(x^n-1).$ $$p(x) \equiv q(x) \text{ iff } p(x) - q(x) = 0 \pmod{(x^n-1)}$$ Thinking of multiplication by $x$ as the shift ...
kodlu's user avatar
  • 21.9k
2 votes
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 ...
Daniel S's user avatar
  • 22.8k
2 votes

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 ...
Daniel S's user avatar
  • 22.8k
2 votes

The mathematical similarity and difference between code-based PKE and multivariate DSS

Multivariate schemes tipically work with a central polynomial map $\mathcal{F}(X) : F_2^n \mapsto F_2^m$ which is a quadratic map that defines $m$ quadratic equations on $n$ variables. Then select $T,...
kub0x's user avatar
  • 898
2 votes
Accepted

Covering codes for digital signatures

This makes perfect sense in principle. However you will need some extra properties from your covering code. My understanding is that no one ever came up with a family of covering codes having all ...
LeoDucas's user avatar
  • 1,203
2 votes
Accepted

Truncating ciphertext as encryption and to decrease bandwidth in code-based PKEs

I'm not aware of a scheme that does this, but I'm not an expert so there may well be such a scheme and I just don't know it. As I see it, the main issue is that most code-based crypto uses linear ...
Mike Hamburg's user avatar
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
  • 22.8k
1 vote

Post-quantum secure trapdoor function

Lattice-based problems are the most common examples for this. In general, we need to generate a “hard” public basis $B'$ (chosen at random from some appropriate distribution) of some lattice $L$ ...
NB_1907's user avatar
  • 610
1 vote

Covering codes for digital signatures

Sort of --- but likely not in the way that you imagine. By this, I mean that what you want exists in the lattice-crypto world. I imagine it means it exists (or you could make it work) in the code-...
Mark's user avatar
  • 12.5k
1 vote
Accepted

What are the parity bits in a (7,3)-linear code

In general, let $G$ be a basis matrix for a linear code with the basis codewords as the rows of the matrix. The matrix $G$ can be transformed using column swaps and row additions into systematic form $...
Daniel S's user avatar
  • 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 ...
meshcollider's user avatar
  • 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 ...
Daniel S's user avatar
  • 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&...
Mark's user avatar
  • 12.5k

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