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.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
0answers
129 views

Solving LPN using algorithm for syndrome decoding

Given an algorithm $A_D$ which solves an instance of the decoding problem $e \in \mathbb{F}_2^n$ in time $T_D$ given a parity check matrix $H \in \mathbb{F}_2^{(n-k)\times n}$ and a syndrome $s \in \...
3
votes
1answer
122 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 ...
3
votes
0answers
46 views

Choosing the Bernoulli distribution for LPN encryption scheme

The symmetric-key encryption scheme from [1] 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 ...
3
votes
0answers
80 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 ...
2
votes
0answers
36 views

Merkle tree-based PoR

As you may already know, proofs of retrievability (PoR) can be constructed using MACs, Signatures (as stated here) or Merkle tree (like this). The PoRs that are based on MACs or signatures usually use ...
2
votes
0answers
97 views

ROLLO: ideal codes

In ROLLO - Rank-Ouroboros, LAKE & LOCKER, Ideal codes are defined in Definition 2.1.4. Thanks to the Lemma 1, it is proved that every block of ideal matrix is non-singular. Now, why do they say &...
2
votes
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
0answers
41 views

What is the code when looking at the LPN problem?

We are given the problem in this question. We know that we have to use the algorithm $A_D$ in order to get $e_i$. Our idea is that we construct a vector $l$ of $l_i$'s by getting $n$ samples from the $...