# Tag Info

## Hot answers tagged coding-theory

7

Prime theory is of great interest to me! It is currently used in many cryptosystems to protect data (in making public keys, for example). There are always a few obscure researchers studying how to make prime factorization easier (or stronger I suppose). There are so many branches of math that we use in cryptography (matrices, primes, ellipses, modular ...

6

Shamir's (m,n) secret sharing scheme has a secret $s_0$ which is represented as an element of a finite field $\mathbb F_q$ of $q$ elements. There are also $m-1$ other "randomly chosen" elements $s_1, s_2, \ldots, s_{m-1}$ that the designer uses. The scheme creates a polynomial $$S(x) = s_0 + s_1x + \cdots + s_{m-1}x^{m-1}$$ and evaluates $S(x)$ at $n$ ...

5

Abstract mathematics has played an important role in the development of cryptography. From Analytical number theory, tools like factorization and computing logarithms in a finite field. Enough is said and known about these techniques! Combinatorial problems, like knapsack and subset-sum has been used in cryptosystem. You can find a very nice connection ...

4

I would like to add my two cents (mostly related to asymmetric cryptography): Number theoretic primitives (RSA/DH/EC/Pairing based crypto) [Mainstream] Coding theory based crypto systems (McEliece) [research] Lattice based systems [research] Other models of information theory, e.g. wiretap model [research] Combinatorics (knapsack problems) [research]

4

"Algebraic Geometry Codes: Basic Notions" by Tsfasman, Vladut, and Nogin is a textbook that is available as a PDF. Discussion of Hermitian curves begins on page 167. I haven't read it and no very little about coding theory. It was the reference a friend provided in his dissertation, which included constructing universal hash functions from Hermitian curves. ...

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

Generating prime integers and computing things modulo integers is easy with a programming language which features support for big integers. I usually use Java: it includes java.math.BigInteger, with which one can: generate prime integers of any length; do all basic operations, including modular reduction (mod() method); compute modular inverses ...

3

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

3

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

3

In general, an $(n,k,k')$ erasure code must have the property that any $k'$ out of $n$ symbols must be sufficient to recover the original $k$-symbol message. An $(n,k')$ threshold secret sharing scheme, however, requires an additional property: knowing less than $k'$ shares out of $n$ must not be sufficient to recover any information about ...

2

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

2

I am not sure on the implementation status of hyperelliptic curves. Two other significant uses of mathematical techniques: Bilinear pairings on appropriate elliptic curves - mainstream (Voltage) Ideal lattices - mainstream (NTRU) and in research (Gentry's fully homomorphic encryption) Another area of interest is based on coding theory: Learning ...

2

If you use a high-level mathematical language (Mathematica, Maple, etc.), generating this data is very easy. I use Mathematica personally, but some are free and apparently very good. In a pinch, you can use Wolfram Alpha to do a lot: Generate random prime: RandomPrime[{2^1023,2^1024}] Random integer: RandomInteger[{2^1023,2^1024}] Inverse mod p: ...

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

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

1

Ok, I found the answer. The answer is yes, singular submatrices may happen in a Vandermonde matrix. Look at this paper for an approach to avoid singular submatrices while creating a generator matrix: http://oatao.univ-toulouse.fr/2176/1/Lacan_2176.pdf

1

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

1

First of all, the choice of word "Erasure code" is not appropriate. RS code can be used as an erasure code, but when you are talking about erasure code, you implicitly work in the area where some bits of the data has been deleted (note the difference from ECC where you know that the data has been corrupted). An erasure code is more efficient in terms of ...

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