# Tag Info

## Hot answers tagged coding-theory

26

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 will need to calculate time and space complexity of cryptographic algorithms. An "Algorithms" course taken from a CS department would be very useful. My advice ...

25

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 not another valid data vector. If the errored vector $x'$ is not a valid data vector and you can do detection, then all $k$ bits cannot be used as arbitrary ...

12

$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$ It is equivalent to XOR. $0 \times 0 = 0\\ 0 \times 1 = 0\\ 1 \times 0 = 0\\ 1 \times 1 = 1$ It is equivalent to AND. the $^5$ is the dimension of the space ...

9

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 you want to add error correction. This means that, on top of the $2^k$ correct messages that you want to be able to send, you also want to be able to send some ...

7

Not sure if hash trees miss some of your requirements, but many of requirements you have could be satisfied with hash trees. Note: The scheme described below is essentially "Merkle Hash Tree-based Storage Enforcing Scheme (MHT-SE)[Golle et al. 2002]". So my question is, if we relax the requirement of being able to perform an unbounded number of ...

7

I do not know of any approaches in context of proofs or retrievability (PoRs)/provable data possession (PDP) that use homomorphic encryption. However, many of those schemes employ homomorphic (linear) authenticators/tags for the metadata such that the proofs delivered by the server can be of constant size, i.e., by aggregating single tags. Now to some ...

6

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 formats have a fixed header Some file formats/protocols only use part of the available symbol space Some information only allow certain information in certain ...

5

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 within discrete mathematics. Within logic proof theory is very important, otherwise, you could not prove the correctness of cryptographic algorithms. Many ...

5

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 Bernoulli distribution as the error. This trick is proved in Lemma 2 of Applebaum et al. for a more general case, or on the (Ring-)LPN attacks of Kirchner (Section ...

4

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, the $t^{\mathit{th}}$ share has $2^{10~000}$ possible values with uniform distribution, and so the conditional distribution on the secret given $t - 1$ shares ...

4

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 go from one string to the next and it would always have to map to the same value.) So this does not make any sense. I think, like you also suggest, that an ...

4

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 means you are off by a constant depending on the number of variables since $$(-1)^u=1-2u$$ for $u\in \{0,1\}.$ See my answer below on Boolean functions and ...

3

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 locality condition map to the same value. Compared to the coding approach, it has the advantage that it works for any domain element. However, locality here is ...

3

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 with the FEC implementations for Ethernet. Let's take 10GBASE-R Ethernet as an example. 10GBASE-R Ethernet without FEC is transferred using the 64b/66b line ...

2

The question has been answered but let me add some historical examples. Enigma operators often made spelling mistakes; it didn't help their cause. Navajo code talkers on the other hand were a good measure even if the cipher was broken. What you are describing is very close to a secret language. A certain terrorist organization operating in Greece in the '...

2

I think the concept you are describing is steganography, with deliberate typos/mistakes in a text document hiding the fact that there is any data to be found. This technically does not encrypt anything (it's a form of encoding), but could be used to store/send an encrypted message in a way that might avoid rousing suspicion. See http://en.wikipedia.org/...

2

The short answer is that such an encoding would not help with encrypting the content. A good, modern encryption scheme should at least be secure if the attacker can choose the plaintext, let alone know what the plaintext is. Moreover, most of them are secure if the attacker can even ask for the decryption of ciphertexts of his choice (other than the actual ...

2

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{cases}$$ where subscripts denote bit index. Is that "succinct"? I can't tell for lack of a definition. We sure can make an $O(n)$ representation of $y$; in ...

2

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 elements. Sometimes $GF(2)$ is also used. Compare with vector space of dimension 2 over the reals, the $xy$plane, which is denoted $\mathbb R^2.$ Now, since the ...

2

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 confusing and as a personal peculiarity makes a nonstandard semantic distinction between them, which one you use is a matter of taste. And as we all know—de ...

2

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–272 in Cryptographic hardware and embedded systems—CHES 2013—15th international workshop, Santa Barbara, CA, USA, August 20–23, 2013, proceedings, edited by ...

2

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 affine space) is an $n$-dimensional affine subspace of $V$. Note that a 2-flat of a vector space $V$ over $\mathbb{F}_2$ is then any set of the form $$A = \{a, a ... 2 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. However, Stern's algorithm for ISD does not scale purely with the code size. Following a geometric distribution, we can express the expected cost of an ISD ... 2 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 make a\cdot s uniform, assuming the components of a are independently chosen with a biased Bernoulli distribution. Even though each term a_i \cdot s_i in ... 2 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). 2 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 \{0,1\} then the formula for nonlinearity is ... half the number of bits in the function, less the absolute value of the unexpected distance. That is$$ Nl(f) =...

2

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 the minimum distance proof may break down. This will require another GCD check. Irreducibility precludes both of these situations as well as irritating issues ...

1

This quite technical connection was ultimately proved in the paper C. Carlet, P. Charpin and V. Zinoviev. Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography 15(2), pp. 125–156, 1998. See also the paper by the same authors plus Dobbertin in the IEEE Transactions on Information Theory, around the ...

1

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$ are parity block ($n=2N$ and $k=N$ in the OP's notation) ---- any $k$ blocks are sufficient to reconstruct the entire codeword, that is, all the blocks can be ...

1

It seems to me that the answer is highly likely to be as follows. I only had a quick look, so buyer beware: So, instead of the recovered permuted error vector $\sigma(e)$ ( $e$ is the plaintext, in Niederreiter and Classic McEliece) needing to be scrambled by the opponent to get the unpermuted error vector $e$, the recovery of the correct error vector (for ...

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