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

34 questions
Filter by
Sorted by
Tagged with
8k 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 ...
1k 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 ...
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 ...
2k 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)$?
100 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 ...
707 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)$ ...
342 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 ...
87 views

310 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 ...
393 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 ...
96 views

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 ...
241 views

### About using mistakes as part of a code

Could a code be developed where one uses intentional errors say in english, as a text to encode? For example someone might have a message 'Agent X must report to station 5'. This could be distorted ...
121 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 ...
84 views

I am given that $S_1=(S_1,P_1)$ and $S_2=(S_2,P_2)$ are sources, where $S_1=\{s_1,...,s_n\}$, $P_1(x_i)=p_i$ and $S_2=\{y_1,...,s_m\}$, $P_2(y_j)=q_j$. I have to find the entropy of $S_{\lambda}=(S_i ... 0answers 265 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 122 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 166 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 ... 2answers 141 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 41 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 86 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 ... 1answer 74 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 43 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 73 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 66 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 98 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 ... 0answers 21 views ### Is it possibe to extend DGK method of comparion two integers to$d$-ary settings? In , a method for comparing two integers is described by using polynomial operations related to the binary representations of the given two integers. The method is re-phrased as follows: Given the ... 0answers 23 views ### What are dual codes and the codewords denoted by these dual codes in terms of trace? I am currently reading a research paper (linked below) that mentions "Consider only maps that vanish at 0, their short codes$C_f$and their duals$C_f^\perp$. The duals can be written as$C_f^\perp = ...
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 ...
### 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 ...