Advanced Search

A Symmetric Somewhat Homomorphic Encryption Implementation

/ Published in: Python
Save to your folder(s)
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.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. #!/usr/bin/env python
  2.  
  3. import random
  4.  
  5. def keygen(noise, modulus=2):
  6.     a_key = random.getrandbits((noise ** 2))
  7.  
  8.     while ((a_key % 2) != 1) and (a_key < (modulus ** (noise ** 2) - 1)):
  9.         a_key = a_key + 1
  10.  
  11.     return a_key
  12.  
  13. def encrypt(noise, a_key, a_bit, modulus=2):
  14.     a_mask          = random.getrandbits(noise)
  15.     a_bit_remainder = a_bit % modulus
  16.  
  17.     while ((a_mask % modulus) != a_bit_remainder):
  18.         a_mask = random.getrandbits(noise)
  19.  
  20.     return a_mask + (a_key * random.getrandbits(noise ** 5))
  21.  
  22. def decrypt(a_key, a_bit, modulus=2):
  23.     return (a_bit % a_key) % modulus
  24.  
  25. def simple_example():
  26.     modulus         = 32
  27.     noise           = 6
  28.     a_key           = keygen(noise, modulus=modulus)
  29.     a_random_bit    = random.getrandbits(5)
  30.     a_cipher_bit    = encrypt(noise, a_key, a_random_bit, modulus=modulus)
  31.     a_decrypted_bit = decrypt(a_key, a_cipher_bit, modulus=modulus)
  32.  
  33.     print("simple_example()\n----------------")
  34.     print("key: %d\nplaintext: %d\nencrypted: %d\ndecrypted: %d\n\n" % (a_key, a_random_bit, a_cipher_bit, a_decrypted_bit))
  35.  
  36. def multiplication_example():
  37.     modulus = 16
  38.     noise   = 5
  39.     a_key   = keygen(noise, modulus=modulus)
  40.     a_p     = random.getrandbits(2)
  41.     b_p     = random.getrandbits(2)
  42.     a_c     = encrypt(noise, a_key, a_p, modulus=modulus)
  43.     b_c     = encrypt(noise, a_key, b_p, modulus=modulus)
  44.     c       = a_c * b_c
  45.     d       = decrypt(a_key, c, modulus=modulus)
  46.     print("multiplication_example()\n-------------------------")
  47.     print("a (p): %d\nb (p): %d\n" % (a_p, b_p))
  48.     print("a (c): %d\nb (c): %d\n" % (a_c, b_c))
  49.     print("c: %d\nd: %d\n\n" % (c, d))
  50.  
  51. def addition_example():
  52.     modulus = 8
  53.     noise   = 4
  54.     a_key   = keygen(noise, modulus=modulus)
  55.     a_p     = random.getrandbits(2)
  56.     b_p     = random.getrandbits(2)
  57.     a_c     = encrypt(noise, a_key, a_p, modulus=modulus)
  58.     b_c     = encrypt(noise, a_key, b_p, modulus=modulus)
  59.     c       = a_c + b_c
  60.     d       = decrypt(a_key, c, modulus=modulus)
  61.     print("addition_example()\n------------------")
  62.     print("a (p): %d\nb (p): %d\n" % (a_p, b_p))
  63.     print("a (c): %d\nb (c): %d\n" % (a_c, b_c))
  64.     print("c: %d\nd: %d\n\n" % (c, d))
  65.  
  66. def xor_gate():
  67.     noise   = 4
  68.     a_key   = keygen(noise)
  69.     a_p     = random.getrandbits(1)
  70.     b_p     = random.getrandbits(1)
  71.     a_c     = encrypt(noise, a_key, a_p)
  72.     b_c     = encrypt(noise, a_key, b_p)
  73.     c       = a_c + b_c
  74.     d       = decrypt(a_key, c)
  75.     print("xor_gate() (XOR)\n----------------")
  76.     print("a (p): %d\nb (p): %d\n" % (a_p, b_p))
  77.     print("a (c): %d\nb (c): %d\n" % (a_c, b_c))
  78.     print("c: %d\nd: %d\n\n" % (c, d))
  79.  
  80. def and_gate():
  81.     noise   = 4
  82.     a_key   = keygen(noise)
  83.     a_p     = random.getrandbits(1)
  84.     b_p     = random.getrandbits(1)
  85.     a_c     = encrypt(noise, a_key, a_p)
  86.     b_c     = encrypt(noise, a_key, b_p)
  87.     c       = a_c * b_c
  88.     d       = decrypt(a_key, c)
  89.     print("and_gate() (AND)\n----------------")
  90.     print("a (p): %d\nb (p): %d\n" % (a_p, b_p))
  91.     print("a (c): %d\nb (c): %d\n" % (a_c, b_c))
  92.     print("c: %d\nd: %d\n\n" % (c, d))
  93.  
  94. def or_gate():
  95.     noise   = 4
  96.     a_key   = keygen(noise)
  97.     a_p     = random.getrandbits(1)
  98.     b_p     = random.getrandbits(1)
  99.     a_c     = encrypt(noise, a_key, a_p)
  100.     b_c     = encrypt(noise, a_key, b_p)
  101.     c       = (a_c * b_c) + (a_c + b_c)
  102.     d       = decrypt(a_key, c)
  103.     print("or_gate() (OR)\n--------------")
  104.     print("a (p): %d\nb (p): %d\n" % (a_p, b_p))
  105.     print("a (c): %d\nb (c): %d\n" % (a_c, b_c))
  106.     print("c: %d\nd: %d\n\n" % (c, d))
  107.  
  108. def not_gate():
  109.     noise   = 4
  110.     a_key   = keygen(noise)
  111.     a_p     = random.getrandbits(1)
  112.     a_c     = encrypt(noise, a_key, a_p)
  113.     c       = 1 + a_c
  114.     d       = decrypt(a_key, c)
  115.     print("not_gate() (NOT)\n----------------")
  116.     print("a (p): %d\n" % (a_p,))
  117.     print("a (c): %d\n" % (a_c,))
  118.     print("c: %d\nd: %d\n\n" % (c, d))
  119.  
  120. def nand_gate():
  121.     noise   = 4
  122.     a_key   = keygen(noise)
  123.     a_p     = random.getrandbits(1)
  124.     b_p     = random.getrandbits(1)
  125.     a_c     = encrypt(noise, a_key, a_p)
  126.     b_c     = encrypt(noise, a_key, b_p)
  127.     c       = 1 + (a_c * b_c)
  128.     d       = decrypt(a_key, c)
  129.     print("nand_gate() (NAND)\n------------------")
  130.     print("a (p): %d\nb (p): %d\n" % (a_p, b_p))
  131.     print("a (c): %d\nb (c): %d\n" % (a_c, b_c))
  132.     print("c: %d\nd: %d\n\n" % (c, d))
  133.  
  134. def nor_gate():
  135.     noise   = 4
  136.     a_key   = keygen(noise)
  137.     a_p     = random.getrandbits(1)
  138.     b_p     = random.getrandbits(1)
  139.     a_c     = encrypt(noise, a_key, a_p)
  140.     b_c     = encrypt(noise, a_key, b_p)
  141.     c       = 1 + ((a_c * b_c) + (a_c + b_c))
  142.     d       = decrypt(a_key, c)
  143.     print("nor_gate() (NOR)\n----------------")
  144.     print("a (p): %d\nb (p): %d\n" % (a_p, b_p))
  145.     print("a (c): %d\nb (c): %d\n" % (a_c, b_c))
  146.     print("c: %d\nd: %d\n\n" % (c, d))
  147.  
  148. def if_gate():
  149.     noise   = 4
  150.     a_key   = keygen(noise)
  151.     a_p     = random.getrandbits(1)
  152.     a_c     = encrypt(noise, a_key, a_p)
  153.     c       = 1 * a_c
  154.     d       = decrypt(a_key, c)
  155.     print("if_gate() (IF)\n--------------")
  156.     print("a (p): %d\n" % (a_p,))
  157.     print("a (c): %d\n" % (a_c,))
  158.     print("c: %d\nd: %d\n\n" % (c, d))
  159.  
  160. def right_rotate():
  161.     noise   = 4
  162.     a_key   = keygen(noise)
  163.  
  164.     a_p     = random.getrandbits(1)
  165.     b_p     = random.getrandbits(1)
  166.     c_p     = random.getrandbits(1)
  167.     d_p     = random.getrandbits(1)
  168.  
  169.     a_c     = encrypt(noise, a_key, a_p)
  170.     b_c     = encrypt(noise, a_key, b_p)
  171.     c_c     = encrypt(noise, a_key, c_p)
  172.     d_c     = encrypt(noise, a_key, d_p)
  173.  
  174.     a       = a_c + d_c + a_c
  175.     b       = b_c + a_c + b_c
  176.     c       = c_c + b_c + c_c
  177.     d       = d_c + c_c + d_c
  178.  
  179.     de_a    = decrypt(a_key, a)
  180.     de_b    = decrypt(a_key, b)
  181.     de_c    = decrypt(a_key, c)
  182.     de_d    = decrypt(a_key, d)
  183.  
  184.     print("right_rotate() (division mod 2)\n-------------------------------")
  185.     print("a (p): %d\nb (p): %d\nc (p): %d\nd (p): %d\n" % (a_p, b_p, c_p, d_p))
  186.     print("a (c): %d\nb (c): %d\nc (c): %d\nd (c): %d\n" % (a_c, b_c, c_c, d_c))
  187.     print("a' (c): %d\nb' (c): %d\nc' (c): %d\nd' (c): %d\n" % (a, b, c, d))
  188.     print("a: %d\nb: %d\nc: %d\nd: %d\n\n" % (de_a, de_b, de_c, de_d))
  189.  
  190. simple_example()
  191. multiplication_example()
  192. addition_example()
  193. xor_gate()
  194. and_gate()
  195. or_gate()
  196. not_gate()
  197. nand_gate()
  198. nor_gate()
  199. if_gate()
  200. right_rotate()

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.