# Current mathematics theory used in cryptography/coding theory

What are the mainstream techniques borrowed from algebraic geometry (or some other branch of mathematics) which are currently used in cryptography/coding theory? I've only heard about a small subset of elliptic curves and hermitian curves. I've also heard about research of hyperelliptic curves but I don't know if some software has already implemented it.

Could you mention some other branches of mathematics being strongly used in cryptography/coding theory and its state? (mainstream/in research)

-

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 arithmetic, etc, etc...) If you can find a way to exploit some math property that makes it so there are more possibilities, then good on you!

I think a lot of modern research is going into elliptic curve cryptography. I know that the NSA is currently doing research on this and you can find out more via their website. Quantum cryptography also seems to be a hot topic.

I am not expert cryptographer, but I do enjoy reading articles on the subject when I get the chance. Hope some of these ideas lead you closer to where you want to go?

-
Just to nitpick: It's elliptic curve cryptography, not 'elliptical'. Despite the name, elliptic curves are not ellipses. – Jeff Jul 13 '11 at 17:10
oops, sorry...Well, you know what I meant, but thanks for the correction! – Mr_CryptoPrime Jul 20 '11 at 13:18
"Prime factorization" - Oops, looks like there is a misunderstanding here. Factoring primes is easy. RSA is based upon the difficulty of factoring composites (not factoring primes). "Prime theory" - I'm not sure what that is supposed to refer to; I've never heard a mathematician use this phrase. Sounds made-up to me. Perhaps you mean "number theory". – D.W. Aug 4 '11 at 6:09
I always just called it prime theory. Though, of course, if prime theory did exist it would most definitely be a subset of number theory. :) Thanks for clarification. – Mr_CryptoPrime Aug 6 '11 at 2:23

Abstract mathematics has played an important role in the development of cryptography.

1. From Analytical number theory, tools like factorization and computing logarithms in a finite field. Enough is said and known about these techniques!

2. Combinatorial problems, like knapsack and subset-sum has been used in cryptosystem. You can find a very nice connection between subset-sum and Lattice based cryptography. Try working it out yourself, if you can't do it, then look for a neat result in Public-key cryptographic primitives provably as secure as subset sum .

3. Game theory has been used in constructing protocols in rational setting, mainly for a weaker notion of fairness in Secure multiparty computation. Recall that fair computation is impossible because of Cleve's seminal work in STOC 1986.

4. Coding theory and many combinatorial designs (BIBDs, Orthogonal arrays) have been used in the constructing universal hash function families and thereby randomness extractor and pseudorandom number generators. They are mostly used in the unconditional setting.

5. Algebraic geometry have been used in elliptic curve cryptography. Enough has already been said by other people here.

6. Group theory and in general Algebraic number theory has been used (for example, hidden subgroup problem) to construct cryptographic primitives secure against quantum attack. Recall that quantum computers are not known to solve hidden subgroup problems. More so, Algebraic number theory gives rise to ideals and rings on which all the FHE are based and most of the lattice based cryptographic assumptions that have worst case to average case reduction are defined.

7. Analytical tools like exponential sums has been used in proving uniformity of certain distribution. Mostly, they use Weil's critereon and prove that the exponential sum corresponding to a particular distribution has a non-trivial bound and from discrete analog of Weil's critereon, it is uniformly distributed. This has been used to give an evidence that certain form of DH problems have uniform distribution over a group of prime order.

8. Discrete Fourier Analysis has been used to prove and construct hard-core predicates, something of great use in the theoretical cryptography.

9. Additive combinatorics has been used in few cryptosystems indirectly (they are used in complexity theory and from there find application in cryptography), especially the famous BKT03 result. You can find more about these results on Jean Bourgain's and Igor Shparlinski's webpage.

At the moment, I can't remember any more.

-

Surprised nobody has mentioned this. Abstract algebra is a big player in the design of AES, specifically AES uses finite field arithmetic over a specific field. This article introduces the field in question.

The field in question is also called a Galois Field, from Galois theory which neatly solves questions about higher order polynomials as well as linking fields to groups.

I should add that elliptic curve cryptography is actually the use of certain elliptic curves and rational points over a finite field.

Some of the theorems in group theory relate strongly to number theory on which RSA is based, for example $\mathbb{Z}_p$ is a group. You could also take a group $R = {x: x < n, gcd(x,n) = 1} \mod n$. This is also a group, since every element of the group is co-prime to the modulo. If you chose n as the product of two large primes, you'd construct a group from an RSA public key. The requirement that you pick e large and coprime to pq is precisely so that it ends up in this group and thus has an inverse, one of the defining axioms of a group, with the consequence that any t you pick as a target will also belong to this group and thus have an inverse.

-
The term Galois Field just means finite field and were discovered (and completely classified) before the study of Galois theory began. They share a name since they were discovered by the same person. – Brandon Carter Jul 17 '11 at 18:46

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]

-
Lattice based systems can be seen as a special form of coding theory scheme. For example, LWE can be seen as perturbation of a code word in a proper finite field. – Jalaj Jan 27 '12 at 18:31

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 parity with noise - in research
-