Explain with example numbers in more detail symmetric homomorphic encryption

Question

I am trying to understand the lowest level of homomorphic encryption proposed by this thesis : https://crypto.stanford.edu/craig/

and through this simple version: https://crypto.stanford.edu/craig/easy-fhe.pdf

I think this part it is in second link, section 3.2, a symmetric some-what homomorphic encryption.

If an example of encrypting data (1,2) and adding it. then decrypting the result (3), using this algorithm. I would appreciate understanding this basic part first then to get to the more underlying advanced algorithms.

Updated to be even simpler for an example... thank you!

Answer 1

I think I worked out a plausible example for future reference.

• $p$ = this is secret encryption key (random number)
• $c$ = cipher text
• $m$ = the bit to encrypt (1 or 0)
  

encrypt algorithm is (where $q$ and $r$ are random numbers in same space as $p$, the bit-ness)

$$c = p \cdot q + 2p \cdot r + m$$

decrypt algorithm is:

$$m = (c \bmod p) \bmod 2)$$

example: of enc and dec of a bit.
let P = $19$
$c = 19 \times 2 + 1 \quad(q = 2,r = 0)$ which equals "39",
$c = 39 \mid 39 \mod 17 = 5 \mid 5 \mod 2 = 1 $ (this is decrypted m)

now to show homomorphism (over integers)

Suppose $p = 17 , q_1 = 1 , r = 1 , q_2 = 2, r_2= 2$
bit 1 = $0$
bit 2 = $1$
$c_1 = p * 1 + 2 * 1 + 0 = 19$
$c_2 = p * 2 + 2 * 2 + 1 = 39$
$c_1 + c_2 = 58 \mid 58 \mod 17 \mod 2 = 1$ -> adding 1 and 0 = 1 (so that works)
$c_1 * c_2 = 741 \mid 741 \mod 17 \mod 2 = 0 $-> multiplication of 1 and 0 = 0, so that works.

Now to try 1 and 1, as a test, requires a carry-over

Suppose $p = 17 , q_1 = 1 , r = 1 , q_2 = 2, r_2= 2$
bit 1 = $0$
bit 2 = $1$
$c_1 = p * 1 + 2 * 1 + 1 = 20$
$c_2 = p * 2 + 2 * 2 + 1 = 39$
carry-out = AND(c1,c2) = 1 & 1 = 1.
$c_1 + c_2 = 59 \mid 59 \mod 17 \mod 2 = 0 $-> adding 1 and 1 (binary) 10 = 2.
$c_1 * c_2 = 780 \mid 780 \mod 17 \mod 2 = 1 $-> multiplication of 1 and 1= 1