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 ...
esra's user avatar
  • 869
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 ...
kodlu's user avatar
  • 22.2k
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$ ...
Biv's user avatar
  • 9,979
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 ...
Draconis's user avatar
  • 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 ...
H. Idden's user avatar
  • 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 ...
5 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 ...
Samuel Neves's user avatar
  • 12.4k
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, ...
Squeamish Ossifrage's user avatar
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 ...
kodlu's user avatar
  • 22.2k
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}\...
Daniel S's user avatar
  • 23k
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 ...
alex.forencich's user avatar
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 ...
kodlu's user avatar
  • 22.2k
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 ...
Daniel Lerch's user avatar
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 ...
Daniel S's user avatar
  • 23k
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{...
fgrieu's user avatar
  • 140k
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 ...
kodlu's user avatar
  • 22.2k
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 ...
Squeamish Ossifrage's user avatar
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–...
Squeamish Ossifrage's user avatar
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 ...
Aleph's user avatar
  • 1,856
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 ...
kodlu's user avatar
  • 22.2k
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$...
d125q's user avatar
  • 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$ ...
Dilip Sarwate's user avatar
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 ...
kodlu's user avatar
  • 22.2k
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).$
kodlu's user avatar
  • 22.2k
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 $\{...
E.Nole's user avatar
  • 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 ...
Daniel S's user avatar
  • 23k
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 ...
LeoDucas's user avatar
  • 1,203
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 ...
Daniel S's user avatar
  • 23k
1 vote

Error correcting codes that are indistinguishable from random

The actual message n is encrypted by a symmetric encryption scheme using some shared secret The symmetric encryption is keyed by what key? Is it something that the encryptor picks? If so, how does ...
poncho's user avatar
  • 146k
1 vote

Error-Correction capabilities of encryption?

There may be some specific use case where it would be desirable to combine the operations, but in general I don't see a benefit over encrypting and then encoding. The main drawback is that if this ...
bmm6o's user avatar
  • 1,067

Only top scored, non community-wiki answers of a minimum length are eligible