Posted By

weilawei on 03/28/12

Who likes this?

1 person have marked this snippet as a favorite

A Symmetric Somewhat Homomorphic Encryption Implementation

/ Published in: Python

This is an implementation of a symmetric SWHE from section 3.2 of "Computing Arbitrary Functions of Encrypted Data" by Craig Gentry. It contains a small modification (namely, the addition of a modulus parameter to allow a greater-than-2-element plaintext space). Examples provided illustrate the encryption/decryption of a value, addition and multiplication, the basic AND and XOR gates, and complex gates (circuits) for NOT, OR, NAND, NOR, IF, and RIGHT ROTATE. Note that I'm not a cryptographer, so I can't vouch for the correctness of this. If you find a bug, PLEASE post a comment below. Also, note that this is a toy, not production code: performing too many consecutive operations can easily cause values to exceed machine word size, and it's probably vulnerable to any number of attacks.

NOTE: Using a modulus other than 2 should be considered dangerous--and remember, this is only a TOY. Do not use in production.

`#!/usr/bin/env python import random def keygen(noise, modulus=2):    a_key = random.getrandbits((noise ** 2))     while ((a_key % 2) != 1) and (a_key < (modulus ** (noise ** 2) - 1)):        a_key = a_key + 1     return a_key def encrypt(noise, a_key, a_bit, modulus=2):    a_mask          = random.getrandbits(noise)    a_bit_remainder = a_bit % modulus     while ((a_mask % modulus) != a_bit_remainder):        a_mask = random.getrandbits(noise)     return a_mask + (a_key * random.getrandbits(noise ** 5)) def decrypt(a_key, a_bit, modulus=2):    return (a_bit % a_key) % modulus def simple_example():    modulus         = 32    noise           = 6    a_key           = keygen(noise, modulus=modulus)    a_random_bit    = random.getrandbits(5)    a_cipher_bit    = encrypt(noise, a_key, a_random_bit, modulus=modulus)    a_decrypted_bit = decrypt(a_key, a_cipher_bit, modulus=modulus)     print("simple_example()\n----------------")    print("key: %d\nplaintext: %d\nencrypted: %d\ndecrypted: %d\n\n" % (a_key, a_random_bit, a_cipher_bit, a_decrypted_bit)) def multiplication_example():    modulus = 16    noise   = 5    a_key   = keygen(noise, modulus=modulus)    a_p     = random.getrandbits(2)    b_p     = random.getrandbits(2)    a_c     = encrypt(noise, a_key, a_p, modulus=modulus)    b_c     = encrypt(noise, a_key, b_p, modulus=modulus)    c       = a_c * b_c    d       = decrypt(a_key, c, modulus=modulus)    print("multiplication_example()\n-------------------------")    print("a (p): %d\nb (p): %d\n" % (a_p, b_p))    print("a (c): %d\nb (c): %d\n" % (a_c, b_c))    print("c: %d\nd: %d\n\n" % (c, d)) def addition_example():    modulus = 8    noise   = 4    a_key   = keygen(noise, modulus=modulus)    a_p     = random.getrandbits(2)    b_p     = random.getrandbits(2)    a_c     = encrypt(noise, a_key, a_p, modulus=modulus)    b_c     = encrypt(noise, a_key, b_p, modulus=modulus)    c       = a_c + b_c    d       = decrypt(a_key, c, modulus=modulus)    print("addition_example()\n------------------")    print("a (p): %d\nb (p): %d\n" % (a_p, b_p))    print("a (c): %d\nb (c): %d\n" % (a_c, b_c))    print("c: %d\nd: %d\n\n" % (c, d)) def xor_gate():    noise   = 4    a_key   = keygen(noise)    a_p     = random.getrandbits(1)    b_p     = random.getrandbits(1)    a_c     = encrypt(noise, a_key, a_p)    b_c     = encrypt(noise, a_key, b_p)    c       = a_c + b_c    d       = decrypt(a_key, c)    print("xor_gate() (XOR)\n----------------")    print("a (p): %d\nb (p): %d\n" % (a_p, b_p))    print("a (c): %d\nb (c): %d\n" % (a_c, b_c))    print("c: %d\nd: %d\n\n" % (c, d)) def and_gate():    noise   = 4    a_key   = keygen(noise)    a_p     = random.getrandbits(1)    b_p     = random.getrandbits(1)    a_c     = encrypt(noise, a_key, a_p)    b_c     = encrypt(noise, a_key, b_p)    c       = a_c * b_c    d       = decrypt(a_key, c)    print("and_gate() (AND)\n----------------")    print("a (p): %d\nb (p): %d\n" % (a_p, b_p))    print("a (c): %d\nb (c): %d\n" % (a_c, b_c))    print("c: %d\nd: %d\n\n" % (c, d)) def or_gate():    noise   = 4    a_key   = keygen(noise)    a_p     = random.getrandbits(1)    b_p     = random.getrandbits(1)    a_c     = encrypt(noise, a_key, a_p)    b_c     = encrypt(noise, a_key, b_p)    c       = (a_c * b_c) + (a_c + b_c)    d       = decrypt(a_key, c)    print("or_gate() (OR)\n--------------")    print("a (p): %d\nb (p): %d\n" % (a_p, b_p))    print("a (c): %d\nb (c): %d\n" % (a_c, b_c))    print("c: %d\nd: %d\n\n" % (c, d)) def not_gate():    noise   = 4    a_key   = keygen(noise)    a_p     = random.getrandbits(1)    a_c     = encrypt(noise, a_key, a_p)    c       = 1 + a_c    d       = decrypt(a_key, c)    print("not_gate() (NOT)\n----------------")    print("a (p): %d\n" % (a_p,))    print("a (c): %d\n" % (a_c,))    print("c: %d\nd: %d\n\n" % (c, d)) def nand_gate():    noise   = 4    a_key   = keygen(noise)    a_p     = random.getrandbits(1)    b_p     = random.getrandbits(1)    a_c     = encrypt(noise, a_key, a_p)    b_c     = encrypt(noise, a_key, b_p)    c       = 1 + (a_c * b_c)    d       = decrypt(a_key, c)    print("nand_gate() (NAND)\n------------------")    print("a (p): %d\nb (p): %d\n" % (a_p, b_p))    print("a (c): %d\nb (c): %d\n" % (a_c, b_c))    print("c: %d\nd: %d\n\n" % (c, d)) def nor_gate():    noise   = 4    a_key   = keygen(noise)    a_p     = random.getrandbits(1)    b_p     = random.getrandbits(1)    a_c     = encrypt(noise, a_key, a_p)    b_c     = encrypt(noise, a_key, b_p)    c       = 1 + ((a_c * b_c) + (a_c + b_c))    d       = decrypt(a_key, c)    print("nor_gate() (NOR)\n----------------")    print("a (p): %d\nb (p): %d\n" % (a_p, b_p))    print("a (c): %d\nb (c): %d\n" % (a_c, b_c))    print("c: %d\nd: %d\n\n" % (c, d)) def if_gate():    noise   = 4    a_key   = keygen(noise)    a_p     = random.getrandbits(1)    a_c     = encrypt(noise, a_key, a_p)    c       = 1 * a_c    d       = decrypt(a_key, c)    print("if_gate() (IF)\n--------------")    print("a (p): %d\n" % (a_p,))    print("a (c): %d\n" % (a_c,))    print("c: %d\nd: %d\n\n" % (c, d)) def right_rotate():    noise   = 4    a_key   = keygen(noise)     a_p     = random.getrandbits(1)    b_p     = random.getrandbits(1)    c_p     = random.getrandbits(1)    d_p     = random.getrandbits(1)     a_c     = encrypt(noise, a_key, a_p)    b_c     = encrypt(noise, a_key, b_p)    c_c     = encrypt(noise, a_key, c_p)    d_c     = encrypt(noise, a_key, d_p)     a       = a_c + d_c + a_c    b       = b_c + a_c + b_c    c       = c_c + b_c + c_c    d       = d_c + c_c + d_c     de_a    = decrypt(a_key, a)    de_b    = decrypt(a_key, b)    de_c    = decrypt(a_key, c)    de_d    = decrypt(a_key, d)     print("right_rotate() (division mod 2)\n-------------------------------")    print("a (p): %d\nb (p): %d\nc (p): %d\nd (p): %d\n" % (a_p, b_p, c_p, d_p))    print("a (c): %d\nb (c): %d\nc (c): %d\nd (c): %d\n" % (a_c, b_c, c_c, d_c))    print("a' (c): %d\nb' (c): %d\nc' (c): %d\nd' (c): %d\n" % (a, b, c, d))    print("a: %d\nb: %d\nc: %d\nd: %d\n\n" % (de_a, de_b, de_c, de_d)) simple_example()multiplication_example()addition_example()xor_gate()and_gate()or_gate()not_gate()nand_gate()nor_gate()if_gate()right_rotate()`

Posted By: latot on April 5, 2012

First of all - please don't think that I am trying to be condescending or anything. I am being critical because I am also working on the same thing. Secondly, I am focusing only on "simple_example" and the associated methods. So on to the critiques:

1) It doesn't work. Whilst most of the time it will match the plaintext -> ciphertext - > decrypted text, this is a computing time issue and if you repeat it enough times eventually it will give the wrong decryption texts. Also, if you fiddle with the numbers of modulus and noise a bit more, they break even more often and will give even more wrong decrypted texts.

2) You HAVE to use modulo 2. There's a reason mod 2 is used in the paper (and other papers), and that is because you are working with binary digits, which can only take the values 0 or 1 - thus any number (mod 2) will be 0 or 1 (what we want).

3) Your keygen method is a little dangerous. The way you have it akey could be -1 (if akey is initially 0 then (mod 2 - 1) will subtract 1 from it). akey should also not be 0. I have altered this as shown in the code at the bottom of this comment. I also put in limiting values so that akey > 0 and that it does not exceed being a (noise^2)-bit number.

4) I changed arandombit so that it is only 0 or 1 (to be congruent with working with individual bits - its only for now to show).

Otherwise it's good code. I have a modified version of the main functions at the bottom of this comment. The problem with you adding in a modulus is that it breaks the homomorphism, it strays from the blueprint too much and it simply does not work. This new code does work every time and falls within the boundaries etc.

The problem I'm having is working with integers greater than 1. I've tried various methods and it just doesn't seem to work. Maybe you can see something though?

Anyway, here's the modified code I promised:

import random

def keygen(noise): a_key = random.getrandbits((noise**2))

``````while (((a_key % 2) != 1) and (a_key > 0) and (a_key < ((2**noise**2) - 1))):
a_key = a_key + 1

return a_key
``````

def encrypt(noise, akey, abit): a_mask = random.getrandbits(noise)

``````while ((a_mask % 2) != a_bit):

return a_mask + (a_key * random.getrandbits(noise**5))
``````

def decrypt(akey, abit): return (abit % akey) % 2

def simpleexample(): noise = 3 akey = keygen(noise) arandombit = random.getrandbits(1) acipherbit = encrypt(noise, akey, arandombit) adecryptedbit = decrypt(akey, acipherbit)

``````print("simple_example()\n----------------")
print("key: %d\nplaintext: %d\nencrypted: %d\ndecrypted: %d\n\n" % (a_key, a_random_bit, a_cipher_bit, a_decrypted_bit))
``````

simple_example()

Posted By: latot on April 5, 2012

Excuse the messed up formatting from the previous post - don't know what happened. Here's the non-messy code (I hope!)

`import random`

``` def keygen(noise): a_key = random.getrandbits((noise**2)) while (((a_key % 2) != 1) and (a_key > 0) and (a_key < ((2**noise**2) - 1))): a_key = a_key + 1 return a_key def encrypt(noise, akey, abit): a_mask = random.getrandbits(noise) while ((a_mask % 2) != a_bit): a_mask = random.getrandbits(noise) return a_mask + (a_key * random.getrandbits(noise**5)) def decrypt(akey, abit): return (abit % akey) % 2 def simpleexample(): noise = 3 akey = keygen(noise) arandombit = random.getrandbits(1) acipherbit = encrypt(noise, akey, arandombit) adecryptedbit = decrypt(akey, acipherbit) print("simple_example()\n----------------") print("key: %d\nplaintext: %d\nencrypted: %d\ndecrypted: %d\n\n" % (a_key, a_random_bit, a_cipher_bit, a_decrypted_bit)) ```

`simple_example()`

Posted By: latot on April 5, 2012

Sorry.... I give up..... I can't seem to edit/delete posts so you'll have to bear with it......

Posted By: weilawei on May 6, 2012

Hi latot, thank you for taking the time to look this over! I'm sorry it's been so long since you commented, but I didn't think anyone would be interested. So...

2: I understand the reason for the selection of the modulus of 2, but I'm looking for an explanation as to why any other modulus is particularly bad. Most of my examples use the modulus of 2, and I certainly wouldn't suggest anyone use this in production, and especially not with a different modulus. It's a wild idea that sorta seems to have worked. But I wouldn't trust it.

It does indeed break the homomorphic properties of the original, but it seems to work fine for a cipher otherwise. The real attraction of homomorphic encryption, as I understand it, is to perform computations on encrypted data (and perform encrypted operations), but it seemed interesting that other moduluses would decrypt correctly, so I kept the example.

The rest of the examples are more in line with what I expect homomorphic encryption to be used for. As for the code itself, I'm leaving in the option to specify the modulus, with a default value of 2, should it be unspecified. I've updated the examples and order of the parameters to reflect this.

4: I think I addressed this in #2.

As for integers greater than one, you can't encrypt an integer greater than 1 within a single bit. Expanding the modulus allows for us to use more bits per digit. That was the original motivation for altering the modulus. If you want to encrypt a multi-bit number in this scheme, with a modulus of 2, you need to perform the encryption operation for each bit.

Thank you for taking the time to try this out, and thank you for pointing out my mistakes with the keygen. I'm updating the code to reflect the changes. There's also a simple right-rotate example that's new.