Questions tagged [code-based-cryptography]
For questions about cryptosystems based on error-correcting codes. e.g. the Classic McEliece.
15
questions
1
vote
1
answer
90
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.
- 21
6
votes
2
answers
100
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 ...
- 21.2k
0
votes
1
answer
78
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{...
- 103
2
votes
1
answer
484
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, ...
1
vote
0
answers
74
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 ...
- 11
2
votes
2
answers
151
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 $...
2
votes
1
answer
140
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 ...
- 367
1
vote
1
answer
128
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 ...
- 327
3
votes
1
answer
170
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 ...
- 327
12
votes
1
answer
692
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
521
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
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 ...
- 297
1
vote
1
answer
65
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 ...
- 8,648
11
votes
3
answers
887
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....
- 2,554
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 ...
- 71