Exploring the Basics

The previous posts have discussed what this blog is about, and a general overview of Homomorphic Encryption. Now it’s time to start delving a little deeper and looking at the mathematics and basic ideas behind it.

This blog post by Craig Stuntz provides a good overview of what I’ve already talked about on the importance of HE and how it can help revolutionise distributed computing. He also delves a bit into ROT13 encryption method, which is a slightly homomorphic encryption technique as far as concatenation is concerned. The ROT13 technique basically shifts each letter for 13 places forward in the alphabet. It isn’t a very secure approach, but it’s a good introduction to encryption and getting your head around modular arithmetic.

To fully explain modular arithmetic would take to long (and would be too much of a digression) so check the Wikipedia link above – it gives a good explanation. Another link to look at is for the modulo operation, which goes a little more into detail for the programming side of things. In a nutshell, modulo is finding the remainder in division. Another way to look at things is like a clock: if it is 7 o’ clock and you add 10 hours, it isn’t 17 o’ clock, it’s 5 o’ clock. A clock uses (mod 12). So, 17 (mod 12) = 5.

The next post by Craig Stuntz gets a little deeper again. It explains more about the modulo operation, and more specifically, in a programming context. Check the link for more details, but the basics of it are below:

• First thing’s first – integer division. What is 10/6? Most would say 1 remainder 4. But the real answer is 1.6666 recurring. This is closer to 2 than 1, so how about an answer as 2 remainder -2? This gives a more accurate quotient, and a smaller remainder. So which is correct? Well, both are, as long as the following rule holds true:

dividend = divisor * quotient + remainder (the division rule)

• There are various types of finding the quotient and remainder, but the type used for Homomorphic encryption in the van Dijk, et al. paper as well as Gentry’s CACM paper use “R-Division”

1. Compute the real quotient Q_R (I.E. 10/6 = 1.6666).
2. Computer the integer quotient Q_Z by rounding the real quotient Q_R to the closest integer (I.E. 1.6666 is closest to 2).
3. Compute the remainder R = dividend – divisor * Q_Z (E.G. R = 10 – (6 * 2) = -2).

• The following segment of binary operations and modulo 2 arithmetic are of most importance due to the fact that they are used in the computation of homomorphic encryption:

• 0 + 0 = 0 mod 2
• 0 + 1 = 1 mod 2
• 1 + 0 = 1 mod 2
• 1 + 1 = 0 mod 2

• 0 – 0 = 0 mod 2
• 0 – 1 = 1 mod 2
• 1 – 0 = 1 mod 2
• 1 – 1 = 0 mod 2

• As can be seen from above: addition and subtraction yield the same results as XOR.

• 0 * 0 = 0 mod 2
• 0 * 1 = 0 mod 2
• 1 * 0 = 0 mod 2
• 1 * 1 = 1 mod 2

• And from above, it can be seen that multiplication yields the same results as AND.

That’s enough for one post, but this is continued in the next post.

- Ciaran

About these ads