What math will I need in order to learn Microsoft's UProve?

Question

I'm studying Microsoft's UProve (independent studies at 35 years old) and forget most of the Math I learned in college.

I intend to proceed and learn the contents of this chapter of this book but can barely get past 2.1.1.

To get a sense of where I'm at, today I discovered that the "e" symbol is an epsilon, is a small number, and is impossible to find beginner information on math.stackexchange.com because searching for the word epsilon results in a text search of every equation in the site. (not helpful to me).

Can anyone recommend a course, keywords websites, etc. in order to fully appreciate Chapter 2 of this book?

Answer 1

MIT-OCW has a cryptanalysis course in the Computer Science department: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-875-cryptography-and-cryptanalysis-spring-2005/

Prerequisites listed there include "General ease with algorithms, elementary number theory and discrete probability." Maybe those would be good keywords to begin with?

Answer 2

I would start with a gentle overview of the subject, like Good Old Mathematics The Basis of Cryptography. Things like this will help to get you a good footing and overview.

The mathematics you need to learn is quite broad and includes:

• Information theory
• Computational complexity
• Statistics
• Combinatorics
• Abstract algebra
• Number theory
• Finite mathematics

There are quite a few math books specifically related to the math side, however, there are also many cryptographic protocols and standards.

I have written a list of those in another post.

A very nice algorithmic book is:

• Handbook of Applied Cryptography
• See NIST for protocols and special publications on cryptographic anything

I would also look into the Open Courseware at schools like MIT and certainly check out your local university library and look for books that float your boat.

Lastly, security is a process and deals with a lot more than algorithms, protocols and math. It also deals with the human element and that is as unpredictable as can be!

Answer 3

The first epsilon, $\in$, that appears is not actually for a small number, but is the "element of" symbol, as in Ford is an element of the set of car brands. So apparently they mean a random car brand by $b \in_{\scr{R}} \text{Brands}$. Epsilon in the sense you mentioned appears later on as a probability $\varepsilon$.

You can use the Wikipedia article Set (mathematics) to familiarize yourself with the basics of set theory. They're dropping a lot of abstract algebra notation like $\Bbb{Z}_n$, which is the cyclic group of order $n$. This is just addition on a clock with $n$ hours on it instead of $12$. Likewise you can do multiplication on a clock, but $3*4=12$ and going 12 hours around the clock from anything is 12, so $12*x=12$, so 12 is really 0. So, in order to be able to divide - to get a subgroup of multiplication - you want to take only the numbers that can't produce 0 through multiplication of any pair. This is the group of units of a ring. $\Bbb{R}, \Bbb{N}, \Bbb{Z}$ are the real numbers, natural numbers, and integers.

To be honest this is somewhat dense, and while it might be a good bellwether for learning new material and putting it into context, you would have a lot more fun reading an introduction to abstract algebra, playing with modular arithmetic to do tricks with large numbers, or learning about probability theory, Turing machines, and cellular automata (which are related). Or, as the other posters suggested, picking up a self-contained book on cryptography.