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

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

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

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

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

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

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

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

As pointed out by poncho, a hash function $H(.)$ that would consistently map two close strings $s_1$ and $s_2$ to the same value, would have to map all the strings to the same value. (Since you could ...
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 ...
Accepted

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

Your $F_2^n$ and $\mathbb F_2^n$ are exactly the same object, just typeset differently! They denote the vector space of dimension $n$ (the exponent) over the binary field $\mathbb F_2$ with two ...
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–...

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

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