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

44 questions
Filter by
Sorted by
Tagged with
7answers
9k views

### Current mathematics theory used in cryptography/coding theory

What are the mainstream techniques borrowed from algebraic geometry (or some other branch of mathematics) which are currently used in cryptography/coding theory? I've only heard about a small subset ...
3answers
3k views

### RS Erasure Coding and Shamir's Secret Sharing

So I was trying to understand the basic difference between erasure coding and secret sharing, and I found this paper (that you can find here or here). For what I understand, it states that Shamir's ...
2answers
2k views

### Does there exist a proof-of-retrievability scheme that is publicly-verifiable, limited-use, and does not use homomorphic encryption?

I find myself wanting to test out a practical implementation of a proof-of-retrievability scheme, simply out of curiosity. These schemes seem to be divided into two variations, publicly-verified and ...
5answers
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 ...
2answers
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)$?
1answer
217 views

### Why doesn't “Classic McEliece” need scrambling?

The original McEliece scheme uses two random matrices S and P to scramble the generator matrix and uses $\mathsf S·\mathsf G·\mathsf P$ as the public key. The Niederreiter variant also does about the ...
1answer
713 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)$ ...
1answer
348 views

### Hermitian curves introductory references

Could you give me some reference to start on Hermitian Curves. Some papers or textbooks would be perfect, and please mention if it's math inclined or comp.sci. inclined. I've only seen hermitian ...
2answers
156 views

1answer
379 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 ...
3answers
409 views

### Where can I find useful data for cryptography/coding theory?

When implementing cryptographic/coding theory algorithms one need to use data like big prime numbers, numbers in $Z_n$ and their inverses, irreducible polynomials in $Z_n[x]$ and so on... While ...
2answers
104 views

### Why is the nonlinearity of this Boolean function evaluating to $\frac12$?

I am using the method presented in this paper to find the nonlinearity of the function $$f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \\ f(x) = x$$ The truth table is $f = [0 \space \space 1]$. Now, I read ...
2answers
125 views

0answers
129 views

0answers
337 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 ...
2answers
278 views

### Reed Solomon secret sharing and as a one-time symmetric key?

Shamir's Secret Sharing is just a special case of Reed-Solomon where only one coefficient is used to store the secret instead of the entire polynomial. Sarwate however, suggests that the latter can ...
1answer
204 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 ...
1answer
128 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 ...
1answer
96 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?
2answers
199 views

### Can Reed Solomon parity blocks be used as an all-or-nothing transform?

Consider the following scheme: Perform an (N,N) Reed-Solomon encoding (i.e. N data blocks, N parity blocks) Drop the N data blocks and keep only the N parity blocks. Are these N parity blocks an all-...
1answer
61 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}$...
1answer
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 ...
0answers
51 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)$. ...
0answers
39 views

### Number of words in binary linear code starting with zero and unit

Is it true that in a binary linear code number of words, which start with zero, is always at least as much as words, which start with 1? I have no idea how to prove or disprove it. Can you give me a ...
0answers
170 views

### Ciphertext indistinguishability under a noisy channel w/ error correction

The objective is to broadcast information over a noisy digital channel (corruption rate of say, 10-20 %, where bits flip). Assume the broadcasting software is public and there is no possibility of ...
0answers
76 views

### Suggestion for proof of retrievability (via coding theory)

I want to build a fully open-source open-everything protocol/service for massively-distributed shared storage (P2P). I came up with a suggestion for a proof-of-retrievability scheme, but I would like ...
2answers
235 views

### Difference between $F_2^n$ and $\Bbb F_2^n$ for a field

I am confused between the notation $F_2^n$ and $\Bbb F_2^n$ for a field in regards to codes. I thought that $F_2^n$ and $\Bbb F_2^n$ were both fields composed by codes of length n and entries in mod ...
1answer
32 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 ...
1answer
59 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. ...
0answers
41 views