2
$\begingroup$

I am currently working on a project that requires me to use the HElib library that implements the BGV homomorphic encryption scheme described in this paper. I need to be able to tune the parameters correctly so I am trying to understand the underlying concepts. However, I find the mathematical notation in the paper quite complicated. Perhaps someone can suggest a set of mathematical concepts that I should study before reading the paper.

Edit: I've just finished my third year in a computer science undergrad program. So my background includes basic courses on discrete math, linear algebra, probability and statistics, theory of computation..etc. I have self-studied some basics of cryptography such as AES, DES, RSA..etc.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Well... Authors use a lot of abstract algebra (rings, field extensions, maybe some algebraic number theory) to define BGV. I've already seem some papers using a bit of Galois theory to explain packing techniques and rotations of slots. To understand and set the parameters, you have to understand the (R)LWE problem and some lattice algorithms... And the noisy-growth analyses are usually complicated because the inequalities used are ugly, but no advanced math is required in this part... $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Jul 6, 2017 at 13:11
  • 1
    $\begingroup$ So, it means a lot of things to learn depending on your background... But maybe you can simplify things by using some parts as black-boxes. For instance, if you are more interested in tunning the parameters, than you could try to abstract (more or less ignore) the algebra used and focus on the security and nosy-growth analyses (there might be some PDFs on the web explaining those parts...) $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Jul 6, 2017 at 13:15

2 Answers 2

Reset to default
5
$\begingroup$

Knowing more about your background, you will definitely want to brush up on some abstract algebra. The book I link to below is pretty popular and introductory. I think it's just at your level. Also, understanding concepts like groups, rings (see below), homomorphisms, and fields are useful in understanding modern crypto. You won't be wasting your time at all.

Probably the most important skill is that vague term known as mathematical maturity, part of which includes

fearlessness in the face of symbols

Along with this is understanding how to read a mathematical proof.

You should know about provable security as well, in particular how a problem can be reduced to another, such as how the security of the lattice shortest vector problem (SVP) can be reduced to the security of RLWE.

You should be familiar with big-$O$ notation.

You should be familiar with probability distributions, in particular the uniform and Gaussian distributions, and what it means to sample from a distribution.

As mentioned in the comments, you need to learn some abstract algebra. Back in the day, I learned enough to start from Pinter's A Book of Abstract Algebra. It has some very gentle prerequisites. You'll definitely need to learn about rings and quotient rings (RLWE means "ring learning with errors").

You'll need some linear algebra (especially norms and inner products) and lattices.

You'll need some algebraic number theory (see section 5.1.1).

Now, this is a lot, and I don't know if you just want to "get the gist" of the paper or hopefully start contributing original research. But again, "mathematical maturity", or trying to cultivate it, is the most important thing regardless!

Improve this answer
$\endgroup$
1
  • $\begingroup$ This one is simple, has a lot of examples and covers from groups to field extension: Algebra: Pure and Applied, by Aigli Papantonopoulou. $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Jul 7, 2017 at 21:50
3
$\begingroup$

I strongly suggest "Fully Homomorphic Encryption over the Integers" as a starting point. This paper uses very simple mathematical primitives to get the point across. With an idea of how that works, you can choose a paper that respects your implementation needs more.

The paper addresses Gentry's homomorphic encryption scheme using integers instead of lattices, as from Gentry's original proposal. It requires some knowledge in number theory and modern algebra to read most of the material. It uses some unconventional notation for symmetric modulo rather than modulo. The hardness proofs use approximate greatest common divisor.

Once you have a grasp on that material you should be able to extend your knowledge by taking advantage of some modern algebras.

Improve this answer
$\endgroup$
0

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