# Questions tagged [coding-theory]

Coding theory studies the properties of codes and their fitness for specific applications, and typically involves the removal of redundancy and the detection and/or correction of errors in transmitted data.

42 questions
Filter by
Sorted by
Tagged with
63 views

### ROLLO: ideal codes

In ROLLO - Rank-Ouroboros, LAKE & LOCKER, Ideal codes are definited in Definition 2.1.4. Thanks the Lemma 1, It is proved that every block of ideal matrix is non- singular. Now, why do they say &...
35 views

114 views

### Error correcting codes that are indistinguishable from random

Suppose you have a public program P(n) which takes message n and generates an encrypted output (utilizing asymmetric cryptography) for some entity which has the private key to decrypt it. Using a ...
82 views

### Error-Correction capabilities of encryption?

This is motivated by this question about the recovery of (corrupted) encrypted files, and in particular the statement (in the answer): But If I know the algorithm and the key and I make a custom ...
28 views

### Decoding in Reed solomon codes

I have code encoded in GF(7) with primitive 5 Сf(4,1,0,4,5,5). (last four symbols is redundancy) While decoding using DFT we use formula $$С_k=N^{-1}*c(z^{-kj})$$ example:  C_1 = c(5^{-1*j})/6 ...
75 views

### Proof that Niederreiter Cryptosystem is correct

I read about Niederreiter Cryptosystem. I understood the Key Generator, encryption and decryption of the cryptosystem, but if I want to prove that is a correct cryptosystem, what should I do?
40 views

### Choosing the Bernoulli distribution for LPN encryption scheme

The symmetric-key encryption scheme from  is based on the LPN (learning parity with noise) problem. The definition of the problem is, informally, that the adversary cannot recover $\mathbf{s}$ from ...
55 views

### How to solve the system of linear equations to recover original file using “Erasure Coding”?

Following article explains a simplified version of Erasure Coding: Link to the article here is the recipe: Take a file of size M. Split the file into k chunks, each of the same size M/k. ...
2k views

### Can error correction and detection be done without adding extra bits?

I have gone through error detection and correction techniques like Hamming codes, and BCH codes require extra parity bits for detection and correction. While sending data, we always seem to introduce ...
50 views

### Constructing Low-Density Parity-Check Codes of length $n$ and minimum distance = $\delta n$ over $GF(q)$? [closed]

I am looking for a way to construct an LDPC (Low-Density Parity-Check) Code $C$ of length $n$ and minimum distance $d_C$ that scales linearly to $n$, meaning $d_C = \delta n$ for $\delta \in (0,1)$. ...
142 views

54 views

### What is the link between the parity check matrix, double-error-correcting codes and APN permutations?

I am currently reading a research paper (linked below) which mentions that a map $f:V:=GF(2^{m}) \rightarrow V$ which vanishes at 0 is APN if it satisfies the condition that it is a binary code $C_{f}$...
63 views

### What does 2-flat mean when discussing APN permutations?

I am currently reading a research paper that uses the term 2-flat. However, I don't understand what this term means. For example, the paper mentions in its definition of APN that for all distinct $a$,...
138 views

### Unique decoding Radius in Reed Solomon Codes

In one of the coding theory books I read the unique decoding radius for Reed Solomon codes is $\frac{1-\rho}{2}$. Precisely, if the relative distance be less than these amount so the receiver is able ...
113 views

195 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 ...
62 views

### Value of $t$ in Fuzzy Exractor

Is there a defined method to choose value of $t$ when using fuzzy extractor to reconcile two close secrets? I did try with multiple values ranging from 5 to close to half of the sequence. I ...
124 views

### Traitor tracing - codeword properties

Let $c ≥ 2$. A code $C ⊂ Q^n$ is a $c$-frameproof code if for any set $X ⊂ C$ with $|X| ≤ c$ we have desc$(X) ∩ C = X$. Thus the only codewords that a coalition of up to $c$ pirates is capable of ...
78 views

### Traitor tracing - determining a set of codewords

I am reading some notes and having trouble understanding the following example: Let $F$ be a finite set of size $q$, where $q ≥ 2$. Let $n$ be an integer, where $n ≥ 2$. For a subset $X ⊆ F^n$ of ...
285 views

### Need an example to write permutation in cycle notation [closed]

Actually, I don't quite understand the question. What does $a_{i,j}$ means? Is it the element in the matrix from row i and column j? Can anyone give me an example? Better use another matrix because I ...
711 views

### What does this notation stand for when describing a code?

This code has appeared in some online course material. I understand the $(5, 4, 3)$ refers to (length, num codewords, distance) but no explanation of the $Z_2^5$ notation is given: One $(5,4,3)$ ...
3k views

### How to hash similar strings to the same hash value?

Suppose that $s_1$ and $s_2$ are two stings that have a small hamming distance. Is there a preimage resistant "hash" function ($H$) that can map them to the same value i.e., $H(s_1) = H(s_2)$?
77 views

### Words having weight near to minimum distance

I am studying the NP-Problem of the codes Syndrome Decoding. The formulation is show below. Input: a binary matrix $H$ of dimension $r \times n$ and a bit string $S$ of length $r$. Property: there ...
330 views

### Convolution and catastrophic codes

i'm reading the article of Massey and Sain (here) and i cannot unserstand - what is "foreforward inversion"? I mean There is a description of circles in convolutional codes and a little bit ...
352 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 ...
81 views