22
votes
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ Requests for literature, software or similar recommendations are off-topic here. For details, see: Do we want “literature recommendations” and similar “list/subjective questions”?" $\endgroup$
    – e-sushi
    Feb 16, 2017 at 17:10
  • 2
    $\begingroup$ Any cryptography textbook will cover the relevant mathematical content, or give references thereto. $\endgroup$
    – fkraiem
    Aug 23, 2018 at 19:14
  • 3
    $\begingroup$ Process algebras are useful if you are interested in formal analysis of communication protocols: they are a nice, formal and compact way of describing communications protocols. They are also used to prove things like privacy properties of voting protocols or blockchains. $\endgroup$
    – Bakuriu
    Aug 23, 2018 at 21:10

7 Answers 7

25
votes
$\begingroup$

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 is, you can read the first 2-3 chapters of Rudolf Lidl' s Finite Fields book. You don't need to understand every little detail in the book, just read that part and get the general idea, and that would be enough for the beginning.

But the bible for the beginners in cryptography is definitely, "Introduction to Cryptography" by Washington and Trappe. It is the most basic book amongst all in addition to being very comprehensive. It has a solution manual and nice exercises that you will enjoy solving. I personally learned a lot from it. Trappe covers almost every basic thing that you need to know as a beginner.

$\endgroup$
1
  • 2
    $\begingroup$ I studied the first two chapter of cryptography is Introduction to Cryptography by Washington and Trappe and I got some clue. $\endgroup$
    – R1w
    Aug 29, 2018 at 5:00
7
votes
$\begingroup$

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?

$\endgroup$
4
  • 4
    $\begingroup$ Just to nitpick: It's elliptic curve cryptography, not 'elliptical'. Despite the name, elliptic curves are not ellipses. $\endgroup$
    – Jeff
    Jul 13, 2011 at 17:10
  • $\begingroup$ oops, sorry...Well, you know what I meant, but thanks for the correction! $\endgroup$ Jul 20, 2011 at 13:18
  • 1
    $\begingroup$ "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". $\endgroup$
    – D.W.
    Aug 4, 2011 at 6:09
  • $\begingroup$ 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. $\endgroup$ Aug 6, 2011 at 2:23
7
votes
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ what about finite field theory ? (used a bit in AES, and in LFSR based systems). Also coding theory is used in some crypto systems. $\endgroup$ Jan 7, 2017 at 7:27
5
votes
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – bzc
    Jul 17, 2011 at 18:46
5
votes
$\begingroup$

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 other subjects, especially probability and statistics are very important as well. Basically, if you love math then you could do worse than to study cryptography at an academic level.

If you just want to apply cryptography then a good understanding of high school math and different numerical systems, Boolean logic and the like could be enough. At least some idea about probability would be required if you want to create protocols yourself.

So there is not just one branch of mathematics involved in cryptography.


That said, there is precious little reason to be great at trigonometry or imaginary numbers. Not all of math is directly applicable, and sometimes we do get people here that try to shoe-horn specific math subjects into cryptography.

$\endgroup$
3
  • 2
    $\begingroup$ Any specific, explicit example for the last paragraph? $\endgroup$
    – Daniel
    Aug 29, 2018 at 13:58
  • 2
    $\begingroup$ Generally those kind of questions are not in my list of bookmarks :) And the problem is that if I point one out that it may attract downvotes. I can name a generic one though: any math that involves floating point calculations is generally not that useful because of bias introduced by rounding errors. Oh, and not every trapdoor etc. is directly practical to use for crypto. $\endgroup$
    – Maarten Bodewes
    Aug 29, 2018 at 14:05
  • 2
    $\begingroup$ Makes sense. There is also this categorical approach to cryptography: math.berkeley.edu/~izaak/assets/cryptocat.pdf $\endgroup$
    – Daniel
    Aug 29, 2018 at 14:10
4
votes
$\begingroup$

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]

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jalaj
    Jan 27, 2012 at 18:31
3
votes
$\begingroup$

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
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.