Homomorphic encryption in Smart grids

Recently I read a paper “Secure Information Aggregation for Smart Grids using Homomorphic Encryption“, which was an interesting read. It introduced me to a new homomorphic encryption called Paillier cryptosystem. Here they have used this cryptosystem to encrypt data collected by smart grids. Smart grids are used for keeping track of the power consumption of an area, neighborhood or a wide range of area. The smart grids carry the information of the power consumption of the local area which is send to the collector unit which will calculate the total power consumption of a wider area. In smart grids the power usage is considered as privacy of the owner, and is not allowed to reveal to other meters. To protect user privacy homomorphic encryption is employed to ensure that the data is not revealed to the device en route. In this they have adopted Paillier cryptosystem since it require additive homomorphic property to use for the data aggregation.

In this method , they assume the smart grids to follow honest and curious model where they assume the smart grids does not falsify the data which causes inaccurate aggregation result, and thereby this model does not consider false data injection attack. Unlike the traditional method where each smart grid is connected to the collector unit, in this method an aggregation tree is generated by the collector unit in which some smart grids are connected directly to the collector unit and the others are connected as their child units. The data from the child and from itself is computed by the parent and is sent to the collector unit which is at the root hence reducing the network traffic at the collector unit. While generating the aggregation tree there are few things to be followed which is described in the paper. Anyway in all sense this is fully better than the traditional model that was employed before. The only mistake that I could find out was that they assume the smart grids to follow honest and curious model which can be exploited. But it is mentioned in the paper that their ongoing research is to improve this functionality.

If anyone gets time after their coding hours do find time to read this paper, it is suitable for novice readers. Maybe you can start reading paper from today onwards. And if it excites you, try implementing the Paillier cryptosystem 😉

 

Primitive Element of a number

A number g, is said to be a primitive element (root) of a number n, if every coprime c of n can be represented as the power of g modulo n, ie.

g^k mod n = k

Properties :

1) For any prime number p an element g ∈ Z such that gⁱ mod p takes all the values in Zp set has i value changes form 1 to p-1, then g is called a primitive element of p.

2) The number of primitive elements for p is given by φ(p-1).

3) Z*_p-1 can be used to find the primitive elements such that if one element in Zp is known then, other elements can be gⁱ mod p, i ∈ Z*_p-1.

4) For all values of a ∈ Zp, the sequence aⁱ mod p is cyclic for a non-primitive element.

5) The number of individual values in this sequence which is occuring uniquely is known as order of the set.

6) The order is specifically the smallest integer i such that aⁱ mod p ≡ 1.

7) Test for primitive element

Assume a is the primitive element of Zp if a^p-1/q_i ≠ 1 (mod p) where q_i are factors for p-1.

Eg: Checking if 2 is a primitive element of 11

2ⁱ mod 11

________________________________________________________________________________________________________________
|    i    |    1    |    2    |    3    |    4    |    5    |    6    |    7    |    8    |    9    |    10    |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|xi mod p |    2    |    4    |    8    |    5    |    10   |    9    |    7    |    3    |    6    |     1    |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 2ⁱ mod 11 has all elements from 1 to 10. Therefore, 2 is a primitive element of 11.

Eg: Check whether 2 and 3 are primitive elements in Z₃₇.

=> p = 37  ,   p-1  = 36

     36 = 2² * 3²     ∴  q_i = { 2, 3 }

     (37 -1) / 2 = 18 ;   (37-1) / 3  = 12

     2¹² mod 37 = 26                                        3¹² mod 37 = 10

     2¹⁸ mod 37 = 26                                        3¹⁸ mod 37 = 1

∴ 2 is a primitive element of 36                    ∴ 3 is not a primitive element of 36

ElGamal Cryptosystem

ElGamal encryption is an asymmetric key encryption algorithm and is used for public key cryptography. The sender and receiver shares a prime number p and any of its primitive element g.

Let’s say Bob is sending the message and Alice is the receiver. Then, the process going on will be as follows:

1) Alice selects a private key x, where x ∈ Zp

2) Public key is generated, K = g^x mod p

3) Bob generates two cipher text,

C₁ = g^y mod p

C₂ = M K^y (mod p),  where 1<= y <= p-2, is an ephemeral key, which is discarded after every message, M.

4) Alice computes the plain text,

Plain text = C₁^-x  C₂ (mod p)

Bob sends the message to Alice

Example :

Suppose, p = 17, g = 6, x = 5, y = 10, M = 13

Public key, K = 6⁵ mod 17 = 7

C₁ = 6¹⁰ mod 17 = 15

C₂ = 13  * 7¹⁰ mod 17 = 9

Then, plain text = 15^-5 * 9 (mod 17) = 13   (15^-5 mod 17 can be found out by Euler’s theorem)

 

AES – Advanced Encryption Standard

AES is based on the substitution-permutation network principle and is similar to Rijndael cipher. It’s block length is fixed to be 128 bits and key length can vary like 128, 192 or 256 bits where the encryption requires 10, 12 and 14 rounds respectively to get the cipher text. In this every input and output of an operation is termed as a state which is an array of 4X4 bytes.

Eg. Plain Text : AES USES A MATRIX ZZ

Hexadecimal : 00 04 12 14 12 04 12 00 0C 00 13 11 08 23 19 19

State representation

AES encryption involves four transformations which transforms the state given as the input to a different state. The four transformations are:

1. Sub Bytes
2. Shift Rows
3. Mix Columns
4. Add Round key

Sub Bytes Transformation

The values in the state is substituted by another values according to a lookup table called S-box.

S-Box

Shift Rows Transformation

ShiftRows method operates on the rows of the state, the nth row is shifted left circular by n-1 bytes.

Mix Columns Transformation

In this step four bytes of each column is replaced by doing multiplication with a fixed matrix shown below,

Matrix multiplication with hexadecimal is a combination of multiplication and addition similar to the normal matrix multiplication. The multiplication part follow the following mentioned rules:

Multiplication with 1: No change in the value

Multiplication with 2: Left shift with no carry. In addition to that XOR with 0X1B if the shifted bit is 1.

Multiplication with 3: Perform multiplication with 2 then XOR with the initial value.

While the addition part is simply XOR.

Add Round key Transformation

Here each byte of the input state is combined with corresponding byte of the subkey by doing bitwise XOR. The subkey for each round is generated by Rijndael’s key expansion method.

Key expansion in AES

Key expansion is done using three operations described below:

1. Rotate : A 32 bit word is rotated eight bits to the left.
   • 08 23 19 0C   =>   23 19 0C 08
2. S-box : 
   

   S-Box

   The value is replaced by using the lookup table given above as follows :

   •   C3   =>   2E
3. Rcon : The value is XORed with the round constant depending on the round number.

Rcon constants for different rounds

Key used for encryption is of 128 bits arranged as four words,

(i) If i is not a multiple of 4, w_i is formed as,

w_i = w_i-1 ⊕ w_i-4

(ii) If i is a multiple of 4, w_i is formed as,

w_i = temp ⊕ w_i-4

temp is a 32 bit word formed from w_i-1 in the following manner :

w_i-1  =>  Left shift 8 bits  =>  S-Box  =>  ⊕ Rcon_i/4  =>  temp_i

Key expansion in AES

Now, the AES encryption can be done in 11 rounds, where the initial round, Round 0 involves an Add Round Key transformation with the initial key comprising of w₀, w₁, w₂ and w₃. Following 9 rounds comprises of Sub Bytes, Shift Rows, Mix Columns followed by Add Round key with the subkey generated for that round. The final round involves all the above rounds except Mix Columns. After that the cipher text is ready.

AES encryption and decryption

 

DES – Data Encryption Standard

DES is a block cipher which is based on a Fiestel Cipher structure where encryption is carried out in multiple rounds, each of which uses a different subkey derived from the original key. The encryption/decryption is done on blocks of 64 bit with a 56 bit long key. The encryption/decryption completes in 16 rounds, where each round uses a 48 bit subkey.

Each round follows the following steps:

• Partition of the input block into two equal halves
• DES function of the right half and the subkey
• XOR of the left half with the output of the function

Now let me explain each steps in detail,

DES Encryption:

1. The bits of the plain text is permuted by the initial permutation table which is shown in the following figure.

Eg. Plain Text, M = 0123456789ABCDEF

M (in binary) = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

M (after permutation) = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010

IP Table

2. The permuted bits is then divided into two equal halves L₀ and R₀

L₀  = 1100 1100 0000 0000 1100 1100 1111 1111

R₀ = 1111 0000 1010 1010 1111 0000 1010 1010

Division of the bits

3. L_i = R_i-1

    R_i = L_i-1 ⊕ f(R_i-1, K_i)

Finding f(R_i-1, K_i)

DES function

Let the key given be K = 133457799BBCDFF1

K (in binary) = 0001 0011 0011 0100 0101 0111 0111 1001 1001 1011 1011 1100 1101 1111 1111 0001

The 64 bit key is permuted by the key permutation table which is given below, to obtain a 56 bit key after discarding the parity bits.

K (after permutation) = 1111 0000 1100 1100 1010 1010 1111 0101 0101 0110 0110 0111 1000 1111

Key permutation table

Now divide K into two equal parts, Co and Do containing 28 bits each

Co = 1111 0000 1100 1100 1010 1010 1111

Do = 0101 0101 0110 0110 0111 1000 1111

From this we have to obtain C_i and D_i for 16 rounds from which the subkeys are created. The C_i and D_i for the first round is obtained by left shifting Co and Do by 1,

C₁ = 1110 0001 1001 1001 0101 0101 1111

D₁ = 1010 1010 1100 1100 1111 0001 1110

By permuting C₁ and D₁ by the following table the subkey K₁ is obtained which is of 48 bit long.

K₁ = 0001 1011 0000 0010 1110 1111 1111 1100 0111 0000 0111 0010

Key – PC-2

Likewise C₂ and D₂ is obtained from C₁ and D₁ by doing left shift by 1 and K₂ is obtained by passing C₂ and D₂ to PC-2. Similarly C_i and D_i is obtained from C_i-1 and D_i-1 by doing left shift according to the following table,

____________________________________________________________________________________
|   Round   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|Left-Shifts| 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |  2 |  2 |  2 |  2 |  2 |  2 |  1 |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 Now, the R₀ has to be passed to an extension table which makes it 48 bits from 32 bits,

Expansion permutation table

Thus, E(R₀) = 0111 1010 0001 0101 0101 0101 0111 1010 0001 0101 0101 0111

E(R₀) ⊕ K₁ = 0110 0001 0001 0111 1011 1010 1000 0110 0110 0101 0010 0101

The result of E(R₀) ⊕ K₁ is written in form of 8 rows with 6 bits each as follows,

B₁ = 011000              B₂ = 010001              B₃ = 011110             B₄ = 111010

B₅ = 100001              B₆ = 100110              B₇ = 010100            B₈ = 100101

There are 8 S-boxes which gives a 4 bit output when a 6 bit input is given, each B_i is given as input to S-boxes of corresponding i value.

S-Box 1

S-Box 2

S-Box 3

S-Box 4

S-Box 5

S-Box 6

S-Box 7

S-Box 8

How to lookup in a S-Box?

It’s simple, the first and last bit determines the row and the other four determines the column and the value inside that box is the required 4 bit output.

Output from 8 S-boxes

The result from the S boxes => 0101 1100 1000 0010 1011 0101 1001 1110 is then permuted by the following permutation table,

After doing the permutation what we finally get is the value of f(R₀, K₁). It is then XOR with L₀ to get R₁. Similarly the process is repeated 16 times. After the 16th round L₁₆ and R₁₆ is reversed ie,

 L₁₆ = 0100 0011 0100 0010 0011 0010 0011 0100
R₁₆ = 0000 1010 0100 1100 1101 1001 1001 0101

becomes, R₁₆L₁₆ => 0000 1010 0100 1100 1101 1001 1001 0101 0100 0011 0100 0010 0011 0010 0011 0100 which is permuted with the final permutation table IP^-1 to get the cipher text.

DES Decryption:

Decryption is also done in the same manner in the reverse order.

Encryption and Decryption