Simple Homomorphic Cipher for password checking

Theory

The code uses the DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) scheme [paper] and which is a fully homomorphic encryption scheme [1].

First we get a random number (p) and two random numbers (q and r), and then encrypt a single bit (m) with:

\(c = p \times q + 2 \times r +m \)

In this case p will be our secret key.

If 2r is smaller than p/2, we cipher with mod p we get:

\(d = (c \mod p) \mod 2\)

We have basically added noise to the value with the q and r values.

With this function we can add (XOR) and multiply (AND).

The logic for checking the first two bits of the password for a match is:

\(cipherbit_7 = (\overline{c_1[7]} \cdot \overline{c_2[7]}) + ({c_1[7]} {c_2[7]}) \)

\(cipherbit_6 = (\overline{c_1[6]} \cdot \overline{c_2[6]}) + ({c_1[6]} {c_2[6]}) \)

etc

Code

The following is an outline:

import sys
from random import randint
import bitarray

def to_bin(string):
    res = ''
    for char in string:
        tmp = bin(ord(char))[2:]
        tmp = '%08d' %int(tmp)
        res += tmp
    return res

def inv(val):
	return(val ^ 1)

password1='A'
password2='B'

print "Password A: ",password1, "Password B: ",password2

bits1 = to_bin(password1)
bits2 = to_bin(password2)

print "Bits:\t",bits1
print "Bits:\t",bits2

c_bits1 = [0 for i in xrange(8)]
c_bits2 = [0 for i in xrange(8)]
	
p =randint(300000, 600000)*2+1

print "Cipher bits 1:"
print "Bit\tCipher\t\tq\t\tr"
for i in range(0,8):
	q=randint(50000000, 90000000)
	r=randint(1,200)
	c_bits1[i] =  q * p + 2*r +int(bits1[i])
	print bits1[i], "\t",c_bits1[i],"\t",q,"\t",r
	if (2*r > p/2): 
		print 'Error'

print
print "Cipher bits 2:"
print "Bit\tCipher\t\tq\t\tr"
for i in range(0,8):
	q=randint(50000000, 90000000)
	r=randint(1,200)
	c_bits2[i] =  q * p + 2*r +int(bits2[i])
	print bits2[i], "\t",c_bits2[i],"\t",q,"\t",r
	if (2*r > p/2): 
		print 'Error'

cipher_bit7 = (  (inv(c_bits1[7]) * inv(c_bits2[7]) ) + ( c_bits1[7] * c_bits2[7] ) ) 
cipher_bit6 = (  (inv(c_bits1[6]) * inv(c_bits2[6]) ) + ( c_bits1[6] * c_bits2[6] ) ) 
cipher_bit5 = (  (inv(c_bits1[5]) * inv(c_bits2[5]) ) + ( c_bits1[5] * c_bits2[5] ) ) 

print	
print "p value:\t",p


print "\nCipher result:"
print cipher_bit5, cipher_bit6, cipher_bit7

#decrypt
result7 = (cipher_bit7 % p) % 2
result6 = (cipher_bit6 % p) % 2
result5 = (cipher_bit5 % p) % 2

print "\nResults"

print result5,result6,result7

if ((result7==1) and (result6==1) and (result5==1)):
	print "Passwords are the same"
else:
	print "Passwords are not the same"

Example

In the following we create 16 cipher value bits and then make a calculation, and then decipher with the p value:

Password A:  A Password B:  A
Bits:	01000001
Bits:	01000001
Cipher bits 1:
Bit	Cipher		q		r
0 	87287788205444 	78622560 	82
1 	88750786929049 	79940324 	18
0 	61043423130676 	54983524 	32
0 	80491991247193 	72501395 	29
0 	86945995810958 	78314698 	142
0 	84631751261457 	76230193 	174
0 	84101674513206 	75752738 	6
1 	83851357008809 	75527270 	149

Cipher bits 2:
Bit	Cipher		q		r
0 	94222140856380 	84868526 	171
1 	95098406442408 	85657803 	184
0 	71366212470212 	64281550 	31
0 	58005073238079 	52246797 	159
0 	56107886863272 	50537948 	174
0 	94347189697499 	84981161 	103
0 	59943468498828 	53992764 	48
1 	82178328189517 	74020326 	39

p value:	1110213

Cipher result:
15969535781392288756035033131 10082692153762243110106057171 13781528670812359005495712181

Results
1 1 1
Passwords are the same

Presentation

Here is a presentation on the method used:

Reference

[1] M. van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan, "Fully
  Homomorphic Encryption over the Integers". Proceedings of Eurocrypt
  2010.