Homomorphic Encryption using ElGamal Encryption

There are some encryption methods which allow us to process encrypted values. In this way we can process using certain mathematical…

Homomorphic Encryption using ElGamal Encryption

There are some encryption methods which allow us to process encrypted values. In this way we can process using certain mathematical operations on cipher values, and end up with the result when we decrypt. For example, if we encrypt a value of 4 and a value of 3 with a public key we get:

Epub(4), Epub(3)

If we now multiply these values we get:

Res=Epub(4)xEpub(3)

If we now decrypt the result (Res) with the private key, and the answer is 12, we have performed a multiplication on the encrypted values. RSA is one method that we can perform a multiplication and division — and is defined as a partial homomorphic encryption (PHE) method. Another method we can use to multiply and divide is ElGamal. If you are interested, here is the method [here]:

Basically, we compute the cipher values (a,b) for both integer values, and then multiply the a values and multiply the b values. The decryption process is then just the same as with a single value. The Go code for this is [here]:

A sample run is with 8 times 5 is [here]:

Input message: hello world
Prime number size: 512

====Values (val1=8 and val2=5)
====Private key (x):
X=42

====Public key (Y,G,P):
Y=13039885828249506231688772247299445547197938118451738724484040265283475187158436392032990161180212758509765634355858852500299761519902486581334607383485678
G=5421644057436475141609648488325705128047428394380474376834667300766108262613900542681289080713724597310673074119355136085795982097390670890367185141189796
P=13232376895198612407547930718267435757728527029623408872245156039757713029036368719146452186041204237350521785240337048752071462798273003935646236777459223

====Cipher (a=101450748543633522174469645756869277481997059615721605260517732295161484254186753595667197143559362478999627059745903717530648060148508480087843044438991489985245922897075242226581775396811442265722954147671675206915171870365011280719796878579281874455540079761975723979282128033485213310679449551478787853130)

(b=38465093973706508803811115294023066346398617497665684652549184603037756144740009180505883628941659699947810540755879724632188654396391356902249381297516702095771526230642720794962274607423513172185916994064267632612496431538114697962898849819813108584603959104072296805551570593318533018040963087684991999072): 

====Decrypted: [40]

We can see the result is 40, and which is 8 times 5.

Dividing cipher values

We then get:

M1÷M2=(b1 a2^x) ÷ (a1^x b2)(mod p)

For the divide operation, we use the inverse mod method for a2 and b2:

a2=a2.ModInverse(a2, priv.P)
b2=b2.ModInverse(b2, priv.P)

The coding is [from here]:

A sample run is:

Prime number size: 512

====Values (val1=200 and val2=50)
====Private key (x):
X=42

====Public key (Y,G,P):
Y=13039885828249506231688772247299445547197938118451738724484040265283475187158436392032990161180212758509765634355858852500299761519902486581334607383485678
G=5421644057436475141609648488325705128047428394380474376834667300766108262613900542681289080713724597310673074119355136085795982097390670890367185141189796
P=13232376895198612407547930718267435757728527029623408872245156039757713029036368719146452186041204237350521785240337048752071462798273003935646236777459223

====Cipher (a1=56622300668423702421204505076888700277109889614202597870615415642885468574085308179633816642461278778491054198793183029297162806137971453218179309398246867198051952699166737618831930710165066516382012966365402771509363128889521120627694217442331751783896086160382995754522665161748147780248600411374764700885)

(b1=16746055813747895144712687410363936094516489227800694234613010627350093612922746723662237701888955235690387255502577600737320849883017338367890546331696578645657858185133479914402559510533159623362118889718991181378028831855854711816406982976177849994630779661302757515632464931881719980604189468573064982212):

====Decrypted: 4

Conclusions

Our data world must change, and we must move into a world where all our data is encrypted, and where we can make decisions on it, without revealing the actual value.