Questions tagged [code-based-cryptography]

For questions about cryptosystems based on error-correcting codes. e.g. the Classic McEliece.

Filter by
Sorted by
Tagged with
1 vote
1 answer
203 views

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

Since code-based PKEs work by correcting error introduced into the ciphertext, and since truncating ciphertext constitutes both saving in bandwidth and introducing "errors", my question ...
DannyNiu's user avatar
  • 9,080
0 votes
1 answer
114 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
1 vote
1 answer
113 views

Post-quantum secure trapdoor function

I am looking for examples post-quantum secure trapdoor functions. Ideally, the inversion knowing the trapdoor should be "simple" in the sense that it can be computed by a circuit in NC^1.
Mjf T's user avatar
  • 21
6 votes
2 answers
112 views

Covering codes for digital signatures

An encryption scheme should be injective in the sense that each ciphertext should only be associated with at most one message, in order that decryption is unambiguous. An efficient signature ...
Daniel S's user avatar
  • 22.8k
0 votes
1 answer
117 views

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

If I have a linear (7,4)-Hamming Code I know that the last 3 bits are the parity bits but I just have seen that there are multiple linear codes like (7,3) for example the code with basis: $$\begin{...
B0BBY's user avatar
  • 103
2 votes
1 answer
797 views

Patterson's decoding algorithm for Goppa codes

From this Wiki page: given a Goppa code $\Gamma(g, L)$ and a binary word $v=(v_0,...,v_{n-1})$, its syndrome is defined as $$s(x)=\sum_{i=0}^{n-1}\frac{v_i}{x-L_i} \mod g(x).$$ To do error correction, ...
Creeptographer's user avatar
1 vote
0 answers
86 views

On the effectiveness of Sidelnikov-Shestakov attack under a bad guess

I have been studying Wieschebrink paper "Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Codes". In the paper a cryptosystem using GRS codes is exhibited with an attack ...
Partizanki's user avatar
2 votes
2 answers
178 views

Cyclic codes as ideals of a quotient ring

I'm finding the algebra behind cyclic codes somewhat tricky. The starting point is easy enough: $C\subseteq \mathbb F_q^n$ is cyclic if any cyclic shift of a codeword $c\in \mathbb F_q^n$ is still in $...
Creeptographer's user avatar
2 votes
1 answer
173 views

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

In Niederreiter cryptosystem, we require the message to be a vector of weight $t$ in $F_q^n$ in encryption, assume $t$ is the error-correction ability of the code. But what is the mapping? One ...
Laura's user avatar
  • 377
1 vote
1 answer
161 views

Use of irreducible Goppa codes in McEliece scheme

Is there a cryptographic reason for using an irreducible Goppa polynomial $g$ in the McEliece scheme? One doesn't need irreducibility to define a usable code, so I assume there is some structural ...
yoyo's user avatar
  • 391
3 votes
1 answer
204 views

dimension of Goppa codes

For the McEliece/Niederreiter cryptosystems, an efficient seemingly secure choice of code is an irreducible binary Goppa code, defined by an irreducible $g(x)\in GF(2^m)[x]$ of degree $t$ and a ...
yoyo's user avatar
  • 391
12 votes
1 answer
707 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
528 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
5 votes
3 answers
1k views

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

The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g. Solving quadratic equations over finite fields short lattice vectors and close lattice ...
Marc's user avatar
  • 297
1 vote
1 answer
74 views

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

In code-based public key encryption schemes, a public key is formed by matrix-multiplying 2 linear matrices to the left and right side of a easily decodeable error-correcting code, so that it'll be ...
DannyNiu's user avatar
  • 9,080
12 votes
3 answers
1k views

Error-correcting Code VS Lattice-based Crypto

I'm not an expert in PQ-crypto, but as I understand error-correcting code and lattice-based crypto, the cryptographic assumptions are very similar. The key difference for me is the nature of the noise....
Ievgeni's user avatar
  • 2,585
2 votes
0 answers
121 views

A proposal for randomization of Niederreiter cryptosystem

The Niederreiter cryptosystem is a public key cryptosystem using Goppa code. Unfortunately it it is insecure unless it is a binary code. So I thought I could insert random linear codes into randomly ...
cryptomania's user avatar