Tag Info

Accepted

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

In general, no. Let us say you have a data vector $x$ of $k$ bits and one bit is flipped by an error. There is no way of detecting, let alone correcting this, unless the errored data vector $x'$ is ...
• 23.1k

Current mathematics theory used in cryptography/coding theory

Finite fields - which is a branch of algebra - is a must. It is, in some way, used in almost all types of cryptographic algorithms. Also, you need some sort of basic programming ability since you ...
• 869
Accepted

What does this notation stand for when describing a code?

$Z_2^5$ means that you are working in $GF(2)^5$. $GF(2)$ is the Finite Field with two elements: 0 and 1 with the addition and multiplications defined: $0 + 0 = 0\\ 0 + 1 = 1\\ 1 + 0 = 1\\ 1 + 1 = 0$ ...
• 10k

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

No, because of the Pigeonhole Principle. Let's say you want to be able to send arbitrary $k$-bit messages. There are $2^k$ possible bit-patterns, and $2^k$ possible intended messages. Now let's say ...
• 191

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

For the general case kodlus answer explained it is not possible. For detecting or correcting errors you need to have redundancy. But many kind of information have included redundancy: Some file ...
• 161
Accepted

Hardness of LPN problem with small secret

There is a simple trick (known in the LWE literature as the Hermite normal form of the problem) that takes an existing LPN problem and transforms it into a problem in which the secret has the same ...
• 12.7k

Current mathematics theory used in cryptography/coding theory

Discrete mathematics, especially number theory and group theory is probably the most important part of mathematics related to cryptography. Number theory, group theory and logic are important subjects ...
Accepted

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

In this formulation you need to convert your function's output range to $\{-1,+1\}$ via $$f(x)=(-1)^{f(x)}$$ and apply the Walsh Hadamard to the new function $f(x)$. Using the zero one formulation ...
• 23.1k
Accepted

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

Suppose the 10 000-bit message is uniformly distributed and we split it with a $t$-of-$n$ scheme. With Shamir's secret-sharing where each share is 10 000 bits apiece, if you have only $t - 1$ shares, ...
Accepted

• 144k
Accepted

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

Some authors write $F_q$ for the finite field of order $q$. Some authors write $\mathbb F_q$. Some authors write $\mathbf F_q$. Unless there's a typo, or unless your pet author is particularly ...

Code families in McEliece cryptosytem

The modern approach is still to use binary Goppa codes. See, e.g., McBits from 2013: Daniel J. Bernstein, Tung Chou, Peter Schwabe. "McBits: fast constant-time code-based cryptography." Pages 250–...
Accepted

What does 2-flat mean when discussing APN permutations?

In the context of Boolean functions, "flat" is usually used as a synonym for "affine subspace of $\mathbb{F}_2^n$". More generally, an $n$-flat in a vector space $V$ (which may be considered as an ...
• 1,876

Hardness of LPN problem with small secret

It seems to me this argument works: According to Ryan O'Donnell's notes here here, $\tau$ is typically strictly smaller than $1/2$. Even in that case, if the secret $s$ is uniform this is enough to ...
• 23.1k
Accepted

Is McEliece secure with non-binary Goppa codes?

The problem is that you're only referring to plain information set decoding. Indeed, for plain ISD, the complexity of attacking a Goppa code over $\mathbb F_q$ would scale as one would expect with $q$...
• 192
Accepted

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

Reed-Solomon codes are Maximum-Distance-Separable codes and thus have the property that in a $[n,k]$ RS code ---- meaning than there are a total of $n$ blocks of which $k$ are data blocks and $n-k$ ...
• 2,751

Error-Correction capabilities of encryption?

There is no easy way of achieving what you want. Let ${\cal M}=\{0,1\}^n,$ and ${\cal K}=\{0,1\}^k.$ Let the set $\cal E,$ have cardinality $2^{f},$ for simplicity (no Hamming sphere would have this ...
• 23.1k

Decoding in Reed solomon codes

Use $5^6\pmod 7 =1,$ to re-express negative powers of $5$ with exponents in $\{0,1,\cdots,5\}.$ This works since $5$ is a generator of the multiplicative group of $GF(7).$
• 23.1k