25
votes
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 ...
- 21k
25
votes
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
12
votes
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$
...
- 9,959
9
votes
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
6
votes
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
5
votes
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 ...
4
votes
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, ...
- 47.5k
4
votes
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.3k
4
votes
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 ...
- 989
4
votes
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 ...
- 21k
4
votes
Accepted
Patterson's decoding algorithm for Goppa codes
First note that
$$\frac{\sigma'(x)}{\sigma(x)}=\sum_{i\in B}\frac 1{x-L_i}$$
and that if we write $C$ for the bit positions of a codeword, the Goppa code is defined by
$$\sum_{i\in C}\frac 1{x-L_i}\...
- 21.2k
3
votes
Can error correction and detection be done without adding extra bits?
It is not possible to implement error correction without adding parity bits. However, in some cases it may be possible to 'steal' some bits from some other part of the protocol. This is what is done ...
- 131
3
votes
How to hash similar strings to the same hash value?
You could combine locality sensitive hashing ($LSH$) with a one-way function $H$. E.g. you could do $H(LSH(x))$ for data $x$. This is one-way and has the feature that two values that fulfill some ...
- 2,888
3
votes
Accepted
Can Reed-Solomon codes work on infinite fields like $\mathbb{Q}$?
Yes they can work, and under some channel noise conditions be useful for error correction coding in a continuous channel. This idea was originally due to Prof. Welch (of Welch-Berlekamp algorithm and ...
- 21k
3
votes
Accepted
Too many wet positions in Wet-Paper Codes steganography with random H
It is not possible to hide a message, without modifying the wet pixels, if there are too many wet pixels. Think for example, of an image with all pixels wet: you can't modify the image without ...
- 686
3
votes
Accepted
Decrypting McEliece if security assumptions fail
If you know $G$ and $G'$ you can recover typically recover $P$ from the support splitting algorithm. Note that the support-splitting algorithm is independent of the bases used to represent the two ...
- 21.2k
2
votes
Finding Nonlinear boolean functions
One trivial possibility is to sets $m=2^n$, and defines $f(x)$ as the $m$-bit vector $y$ with
$$y_j=\begin{cases}
1&\text{if }j=\displaystyle\sum_{i=0}^{n-1}x_i\,2^i\\
0&\text{otherwise}
\end{...
- 137k
2
votes
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 ...
- 21k
2
votes
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 ...
- 47.5k
2
votes
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–...
- 47.5k
2
votes
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 ...
- 21k
2
votes
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
2
votes
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,721
2
votes
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,826
2
votes
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 ...
- 21k
2
votes
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).$
- 21k
2
votes
Why is the nonlinearity of this Boolean function evaluating to $\frac12$?
In addition to the answer by kodlu, after carefully re-reading the papers, I was able to figure it out. Key things to note:
1. If we use the Fast Walsh Transform on Boolean functions consisting of $\{...
- 175
2
votes
Accepted
Use of irreducible Goppa codes in McEliece scheme
As you note, $g(X)$ cannot have any roots in $L$ and so we must perform at least one polynomial GCD to check this.
For binary Goppa codes, we must also check that $g(X)$ has no repeated roots, else ...
- 21.2k
2
votes
Accepted
Covering codes for digital signatures
This makes perfect sense in principle. However you will need some extra properties from your covering code. My understanding is that no one ever came up with a family of covering codes having all ...
- 1,193
2
votes
Accepted
How to choose rank(A) independant columns of matrix A efficiently
Compute the row echelon form of the matrix and select the pivot columns. Computing the row echelon form of a $m\times n$ matrix will take $O(m^2n)$ field operation, which is pretty straightforward. If ...
- 21.2k
Only top scored, non community-wiki answers of a minimum length are eligible