CRYPTOGRAPHIC APPLICATIONS OF HOMOMORPHIC
ENCRYPTION
1 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where a company wants to outsource the computation of the
sum of two encrypted numbers xand yto a cloud server using homomorphic encryption. The
company encrypts x= 7 and y= 3 using a fully homomorphic encryption scheme and sends the
ciphertexts to the cloud server. The cloud server computes E(x+y)and sends the result back to
the company.
a) If the company decrypts E(x+y), what value will they obtain?
b) If the company wants to know the result of 3x+ 2ywithout revealing xand yindividually, can
this be achieved using homomorphic encryption?
Solution 1.
a) The cloud server computes E(x+y)where x= 7 and y= 3. Using fully homomorphic
encryption, the encryption scheme allows for addition of ciphertexts without decrypting them. Thus,
E(7 + 3) = E(10). When the company decrypts this ciphertext, they will obtain the result of 10.
b) To compute 3x+2ywithout revealing xand yindividually, thecompanycanutilizethepropertiesof thehomomorphicencryptionscheme.Sincehomomorphicencryptionsupportsbothadditionandmultiplicationoperations, itispossibletocompute3x
+ 2ywithoutrevealingthevaluesof xandy separately.
Let E(3x)be the encryption of 3xand E(2y)be the encryption of 2y. The company can compute
E(3x+ 2y)using the homomorphic properties of the encryption scheme. Therefore, the company
can indeed compute 3x+ 2ywithout revealing xand yindividually.
2 2. PERFORMANCE ISSUES IN HOMOMORPHIC ENCRYPTION
Problem 2. Consider a fully homomorphic encryption scheme where the public key size is
512 bits, the secret key size is 128 bits, and the security level is set to 80 bits. If a homomorphic
operation in this scheme takes 10 milliseconds to compute on average, and we want to perform
100 homomorphic operations in a sequence, calculate the total time it would take to complete all
these operations.
Solution 2. Let’s first calculate the time it takes to perform one homomorphic operation: Given
that the homomorphic operation takes 10 milliseconds to compute on average.
Therefore, time taken for one homomorphic operation = 10 milliseconds.
Now, we want to perform 100 homomorphic operations in sequence. Let’s calculate the total
time it would take to complete all these operations.
Total time for 100 operations = time taken for one operation ×number of operations Total time
for 100 operations = 10 milliseconds ×100
Total time for 100 operations = 1000 milliseconds
Therefore, the total time it would take to complete 100 homomorphic operations in sequence is
1000 milliseconds or 1 second.
I. Difficulty: Easy
3 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to perform a homomorphic encryption on a message m= 7 using a fully
homomorphic encryption scheme. The public key for this scheme is n= 13 and the encryption
function is defined as E(x) = x2mod n. Calculate the encrypted message.
Solution 1. To encrypt the message using the homomorphic encryption scheme, we need to
compute E(m):
E(m) = E(7) = 72mod 13 = 49 mod 13 = 10
Therefore, the encrypted message is 10.
4 Cryptographic Applications of Homomorphic Encryption
Problem 2. Bob wants to perform a homomorphic addition on two encrypted messages. The
encrypted messages are c1= 8 and c2= 12, and the public key for the homomorphic encryption
scheme is n= 17. If the encryption function is defined as E(x) = x2mod n, calculate the result
of adding the two encrypted messages together.
Solution 2. To perform homomorphic addition on the encrypted messages, we first need to
decrypt the messages, add them together, and then re-encrypt the sum:
Step 1: Decrypt the messages
C1=c
n+1
4
1mod n= 85mod 17 = 8
C2=c
n+1
4
2mod n= 125mod 17 = 12
Step 2: Add the decrypted messages
D=C1+C2= 8 + 12 = 20
Step 3: Re-encrypt the sum
E(D) = D2mod 17 = 202mod 17 = 400 mod 17 = 11
Therefore, the result of adding the two encrypted messages together is 11.
5 4. LIMITATIONS OF HOMOMORPHIC ENCRYPTION
Problem 4. Consider a fully homomorphic encryption scheme where the ciphertext space is
integers modulo N= 29. Alice wants to perform the following computations:
a) Encrypt the integer 9 using the encryption function.
b) Add two encrypted integers, the encryption of 5 and 12.
c) Multiply an encrypted integer, the encryption of 3, by an encrypted integer, the encryption of
7.
Solution 4.
a) To encrypt the integer 9, we first need to choose a public key (N, q, h)for the encryption
scheme. Let q= 31 and h= 6. Then the encryption function is defined as follows:
Encrypt(m) = mh + 2rmod N
where m= 9, and ris a random integer modulo N. Let’s choose r= 7. Thus, the encryption
of 9 is:
Encrypt(9) = 9∗6+2∗7 mod 29 = 54 + 14 mod 29 = 68 mod 29 = 10
Therefore, the encryption of 9 is 10.
b) To add two encrypted integers, we simply add them modulo N. Let’s consider the encryption
of 5 and 12:
Encrypt(5) = 5∗6+2∗7 mod 29 = 32 mod 29 = 3
Encrypt(12) = 12 ∗6+2∗7 mod 29 = 74 mod 29 = 16
Adding the two encrypted integers:
Encrypt(5) +Encrypt(12) = 3 + 16 mod 29 = 19
Therefore, the sum of the encrypted integers 5 and 12 is 19.
c) For multiplication of two encrypted integers, we multiply the two ciphertexts modulo N. Let’s
multiply the encryption of 3 and 7:
Encrypt(3) = 3∗6+2∗7 mod 29 = 20
Encrypt(7) = 7∗6+2∗7 mod 29 = 49 mod 29 = 20
Multiplying the two encrypted integers:
Encrypt(3) ·Encrypt(7) = 20 ∗20 mod 29 = 400 mod 29 = 16
Therefore, the product of the encrypted integers 3 and 7 is 16.
6 Cryptographic Applications of Homomorphic Encryption
Problem: Suppose we have two ciphertexts c1and c2encrypted under the same homomorphic
encryption scheme, and we want to compute the product of the plaintexts they represent. Let the
decryption function be Dec(·).
Given that Dec(c1) = 7 and Dec(c2) = 4, and we know that the homomorphic encryption
scheme supports homomorphic multiplication, calculate the decryption of the product of the plain-
texts represented by c1and c2, i.e., find Dec(c1×c2).
Solution: Since the homomorphic encryption scheme supports homomorphic multiplication,
we can calculate the product of the plaintexts without decrypting c1and c2individually.
Let’s assume that the product of the plaintexts represented by c1and c2is denoted as m1×m2.
Since Dec(c1) = 7 and Dec(c2)=4, we have m1= 7 and m2= 4.
Now, to find Dec(c1×c2), we calculate the product of the plaintexts represented by c1and c2,
which is m1×m2= 7 ×4 = 28.
Therefore, Dec(c1×c2) = 28.
7 6. SCALABILITY PROBLEMS IN HOMOMORPHIC ENCRYPTION
Problem 6. Consider a homomorphic encryption scheme where the ciphertext size grows
linearly with the plaintext size. Suppose we have a plaintext vector p= [3,1,4,1,5] encrypted
using this scheme and a homomorphic operation that requires adding two ciphertexts together. If
the size of each ciphertext is 4 bytes, what is the total ciphertext size required for this operation?
Solution 6. a) Given that the plaintext vector p= [3,1,4,1,5] is encrypted using a homomorphic
encryption scheme with a ciphertext size of 4 bytes each, the total ciphertext size required for a
homomorphic addition operation can be calculated as follows:
b) Since the ciphertext size grows linearly with the plaintext size, the total ciphertext size re-
quired for encrypting the plaintext vector pis determined by multiplying the number of plaintext
elements by the size of each ciphertext. For a plaintext vector of length n, the total ciphertext size
is given by:
Total ciphertext size =n×Size of each ciphertext
In this case, n= 5 (as there are 5 elements in the plaintext vector) and the size of each ciphertext
is 4 bytes. Substituting these values into the formula:
Total ciphertext size = 5 ×4 = 20 bytes
Thus, the total ciphertext size required for a homomorphic addition operation on the given plain-
text vector using a 4-byte ciphertext scheme would be 20 bytes.
8 Cryptographic Applications of Homomorphic Encryption
Problem: Consider a fully homomorphic encryption scheme where the public key is (n= 5, q =
7) and the secret key is (a= 3).
a) Encrypt the plaintext message m= 4.
b) Perform a homomorphic addition on the ciphertexts corresponding to m1= 4 and m2= 3.
c) Perform a homomorphic multiplication on the ciphertext corresponding to m3= 2.
Solution:
a) To encrypt the plaintext message m= 4, we use the encryption function:
c= (a·r+ 2m) mod q
where ris a random integer. Plugging in m= 4,a= 3,q= 7, and choosing r= 2 for
demonstration purposes:
c= (3 ·2+2·4) mod 7 = (6 + 8) mod 7 = 14 mod 7 = 0
Therefore, the encrypted ciphertext for m= 4 is c= 0.
b) For homomorphic addition on two ciphertexts c1and c2corresponding to m1= 4 and m2= 3,
we can simply add the ciphertexts together modulo q:
cadd = (c1+c2) mod q
Given c1= 0 and c2= (3 ·2+2·3) mod 7 = 12 mod 7 = 5, we have:
cadd = (0 + 5) mod 7 = 5
Therefore, the resulting ciphertext after homomorphic addition is cadd = 5.
c) For homomorphic multiplication on the ciphertext corresponding to m3= 2, we perform the
multiplication modulo q:
cmul = (c·ma
3) mod q
Given c= 0 and m3= 2, we have:
cmul = (0 ·23) mod 7 = 0
Therefore, the resulting ciphertext after homomorphic multiplication is cmul = 0.
9 8. ERROR RATES IN HOMOMORPHIC ENCRYPTION
Problem 8. In a homomorphic encryption scheme, the probability of an error occurring during
the encryption process is 0.05. If a computation involves 20 homomorphic operations, what is the
probability that at least one error occurs during the computation?
Solution 8. Let’s denote the probability of an error occurring during a single homomorphic
operation as p= 0.05. The probability of no error occurring during a single operation is 1−p= 0.95.
The probability that at least one error occurs during the 20 computations can be calculated
using the complement rule (the probability of the event happening is 1 minus the probability of the
event not happening).
The probability of no error occurring during all 20 computations is (0.95)20.
Therefore, the probability of at least one error occurring is:
P(at least one error) = 1 −P(no error in 20 computations)
= 1 −(0.95)20
≈1−0.358485
≈0.641515 (approximately)
So, the probability that at least one error occurs during the computation involving 20 homomor-
phic operations is approximately 0.641515, or 64.15
10 9. KEY MANAGEMENT CHALLENGES IN HOMOMORPHIC ENCRYPTION
Problem 9. Consider a homomorphic encryption scheme where the public key is (n, e)and the
private key is (n, d), where n= 187,e= 7, and d= 23. Given a plaintext message m= 42, encrypt
the message using the public key and then decrypt the ciphertext using the private key.
Solution 9. a) To encrypt the message m= 42 using the public key (n, e), we compute the
ciphertext cusing the encryption function: c≡me(mod n).
Substitute m= 42,e= 7, and n= 187 into the encryption function:
c≡427(mod 187)
Calculating 427(mod 187):
427= 1406408618242
1406408618242 ≡29 (mod 187)
Therefore, the ciphertext cis 29.
b) To decrypt the ciphertext c= 29 using the private key (n, d), we compute the decrypted
message musing the decryption function: m≡cd(mod n).
Substitute c= 29,d= 23, and n= 187 into the decryption function:
m≡2923 (mod 187)
Calculating 2923 (mod 187):
2923 = 49298393010889
49298393010889 ≡42 (mod 187)
Therefore, the decrypted message mis 42, which matches the original plaintext message.
11 10. RELIABILITY CONCERNS IN HOMOMORPHIC ENCRYPTION
Problem 10. Consider a homomorphic encryption scheme where the key generation process
has a 5% chance of generating an incorrect key. Suppose a ciphertext is encrypted using such an
incorrect key.
a) What is the effect on the decryption process if the key is incorrect?
b) Calculate the probability that at least one out of five ciphertexts is decrypted incorrectly due
to a wrong key.
Solution 10.
a) If a ciphertext is encrypted using an incorrect key in a homomorphic encryption scheme,
the decryption process will result in an incorrect plaintext. This is because the decryption process
relies on the correctness of the key to properly recover the original plaintext from the ciphertext.
b) In this case, the probability of a key being incorrect is 5%, so the probability of a key being
correct is 95%, or 0.95. Since there are five ciphertexts, the probability of at least one being
decrypted incorrectly is equal to 1 minus the probability that all five are decrypted correctly.
Let pbe the probability that a ciphertext is decrypted correctly using the correct key. Therefore,
the probability that a ciphertext is decrypted incorrectly using the incorrect key is 1−p.
The probability that all five ciphertexts are decrypted correctly is p5, and the probability that at
least one is decrypted incorrectly is 1−p5.
Substitute p= 0.95 into the formula:
Probability of at least one incorrect decryption = 1 −(0.95)5
= 1 −0.77378
= 0.22622
Therefore, the probability that at least one out of five ciphertexts is decrypted incorrectly due to
a wrong key is approximately 0.22622 (or 22.622%).
12 11. TRUSTWORTHINESS OF HOMOMORPHIC ENCRYPTION
Problem 11. Consider a homomorphic encryption scheme where the encryption function E
and the decryption function Dare defined as follows:
E(x) = x2mod 17
D(y) = √ymod 17
Suppose we want to perform homomorphic addition and multiplication on two plaintext values.
Specifically, given the plaintext values m1= 4 and m2= 11, find the encryption of the sum m1+m2
and the encryption of the product m1×m2using the above encryption scheme. Also, decrypt the
results to obtain the plaintext values.
Solution 11.
a) To find the encryption of the sum m1+m2, we first calculate the sum modulo 17:
m1+m2= 4 + 11 = 15
Next, we calculate the encryption using the encryption function E:
E(15) = 152mod 17 = 225 mod 17 = 4
Therefore, the encryption of the sum m1+m2is 4.
b) To find the encryption of the product m1×m2, we first calculate the product modulo 17:
m1×m2= 4 ×11 = 44
Next, we calculate the encryption using the encryption function E:
E(44) = 442mod 17 = 1936 mod 17 = 16
Therefore, the encryption of the product m1×m2is 16.
c) To decrypt the results, we use the decryption function D:
For the encrypted sum 4:
D(4) = √4 mod 17 = 2
Thus, the decrypted plaintext value for the sum is 2.
For the encrypted product 16:
D(16) = √16 mod 17 = 4
Therefore, the decrypted plaintext value for the product is 4.
13 12. COMPLEXITY IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 12. Consider a homomorphic encryption scheme where the encryption function is
defined as E(m) = m2mod 13.
a) Encrypt the message m= 5.
b) Perform the homomorphic addition of two ciphertexts encrypted with the values m1= 3 and
m2= 4.
c) Decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13.
Solution 12.
a) We are given the encryption function E(m) = m2mod 13. To encrypt the message m= 5,
we substitute m= 5 into the encryption function:
E(5) = 52mod 13 = 25 mod 13 = 12.
Therefore, the encrypted ciphertext for the message m= 5 is 12.
b) To perform homomorphic addition, we calculate the sum of the ciphertexts created by en-
crypting m1= 3 and m2= 4:
E(3) = 32mod 13 = 9 mod 13 = 9
E(4) = 42mod 13 = 16 mod 13 = 3
Now, we add the ciphertexts: 9 + 3 = 12.
Therefore, the homomorphically added ciphertext is 12.
c) To decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13, we substitute c= 12 into the decryption function:
D(12) = √12 mod 13 ≈3.4641 mod 13 ≈3
Therefore, the decrypted message corresponding to the ciphertext 12 is 3.
14 13. PRIVACY RISKS OF HOMOMORPHIC ENCRYPTION
Problem 13. Consider a scenario where a company wants to use homomorphic encryption to
compute the sum of salaries of its employees without decrypting the individual salaries to ensure
privacy. The encryption scheme being used is a fully homomorphic encryption scheme that sup-
ports addition and multiplication operations. The company has encrypted the salaries using the
homomorphic encryption scheme, with each salary encoded as an integer.
The encrypted salaries are as follows: e1= 24,e2= 37,e3= 19, and e4= 42, where each eiis
the encrypted salary of employee i.
a) Compute the encrypted sum of the salaries, Enc(24 + 37 + 19 + 42).
b) The company also wants to compute the encrypted product of the salaries. Find Enc(24 ×
37 ×19 ×42).
c) If the company decrypts the sum of the encrypted salaries, will it reveal any information about
the individual salaries? Justify your answer.
Solution 13.
a) To compute the encrypted sum of the salaries, we can directly add the encrypted salaries:
Enc(24 + 37 + 19 + 42) = e1+e2+e3+e4= 24 + 37 + 19 + 42 = 122.
Therefore, the encrypted sum of the salaries is Enc(24 + 37 + 19 + 42) = 122.
b) To compute the encrypted product of the salaries, we can multiply the encrypted salaries:
Enc(24 ×37 ×19 ×42) = e1×e2×e3×e4= 24 ×37 ×19 ×42 = 387216.
Therefore, the encrypted product of the salaries is Enc(24 ×37 ×19 ×42) = 387216.
c) Homomorphic encryption provides the ability to perform computations on encrypted data
without decrypting it. When the company decrypts only the sum of the encrypted salaries, it will
not reveal any information about the individual salaries. This is because the encryption scheme
used is secure and ensures that the individual encrypted values remain confidential even after the
computation.
15 14. HOMOMORPHIC ENCRYPTION IN REAL-WORLD APPLICATIONS
Problem 14. Consider a scenario where a data processing company wants to outsource the
computation of the average salary of its employees to a cloud server using homomorphic encryp-
tion. The employees’ salaries are encrypted using a partially homomorphic encryption scheme that
supports addition and multiplication operations. Each employee’s salary is encrypted as follows:
E(s) = s2mod 11, where sis the plaintext salary.
a) If the company has four employees with salaries s1= 3,s2= 5,s3= 4, and s4= 6, calculate
the encrypted values for each of their salaries.
b) Compute the sum of the encrypted salaries.
c) Using homomorphic properties, decrypt the result to obtain the average salary of the em-
ployees.
Solution 14. a) To calculate the encrypted values for each employee’s salary:
Given E(s) = s2mod 11,
For s1= 3:E(3) = 32mod 11 = 9 mod 11 = 9
For s2= 5:E(5) = 52mod 11 = 25 mod 11 = 3
For s3= 4:E(4) = 42mod 11 = 16 mod 11 = 5
For s4= 6:E(6) = 62mod 11 = 36 mod 11 = 3
Therefore, the encrypted values for the employees’ salaries are: 9, 3, 5, 3.
b) To compute the sum of the encrypted salaries:
Sum of encrypted salaries = 9 + 3 + 5 + 3 = 20.
c) Since the encryption scheme supports multiplication and addition homomorphically, we can
decrypt the result of the sum by computing the inverse operation of squaring modulo 11, which is
finding the square root modulo 11.
20 ≡x2mod 11
Calculating the square root modulo 11:
x≡ ±√20 mod 11
x≡ ±4 mod 11
Hence, the possible decrypted values are 4 and 7. Since 4 is the correct average salary of the
employees, the decrypted average salary is 4.
16 Cryptographic Applications of Homomorphic Encryption
Problem: Using a fully homomorphic encryption scheme, Alice wants to perform the following
computation: E(m1)·E(m2) + E(m3)−E(m4), where Edenotes the encryption function and
m1= 5,m2= 3,m3= 7, and m4= 2. The encryption function transforms each message to their
encrypted form using the public key.
Assume the following encrypted values are obtained: E(m1) = 10,E(m2) = 8,E(m3) = 15,
and E(m4) = 5. Alice wishes to calculate the result of the above computation without decrypting
any values.
Solution:
Given: E(m1) = 10,E(m2)=8,E(m3) = 15, and E(m4) = 5.
a) Calculate the result of the computation E(m1)·E(m2).
b) Calculate the result of the computation E(m1)·E(m2) + E(m3).
c) Calculate the final result of the original computation.
Solution:
a) E(m1)·E(m2) = 10 ·8 = 80.
b) E(m1)·E(m2) + E(m3) = 80 + 15 = 95.
c) Finally, the original computation E(m1)·E(m2) + E(m3)−E(m4)becomes 95 −5 = 90.
Therefore, the final result of the computation without decrypting any values is 90.
17 16. USABILITY CHALLENGES OF HOMOMORPHIC ENCRYPTION
Problem 16. Consider a homomorphic encryption scheme where the encryption function is
E(x) = x2mod 13. Encrypt the message m= 3 using this scheme.
Solution 16. To encrypt the message m= 3, we substitute x= 3 into the encryption function
E(x) = x2mod 13.
Therefore, the encrypted message is:
E(3) = 32mod 13 = 9 mod 13 = 9
So, the encrypted message for m= 3 is 9.
18 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to securely outsource a computation to a cloud server using fully homo-
morphic encryption. She encrypts her input data xusing the homomorphic encryption scheme, and
sends it to the server. The server performs some computation on the encrypted data and returns
the result yto Alice. If the encryption scheme is fully homomorphic with the following properties:
- Addition: E(a) + E(b) = E(a+b)- Multiplication: E(a)×E(b) = E(a×b)
and the server computes E(3x+ 2), what will be the decrypted result that Alice receives?
Solution 1. Given that E(3x+2) = E(3)×E(x)+E(2), we expand this using the homomorphic
properties:
=E(3) ×E(x) + E(2)
=E(3) ×E(x) + E(2 ×1)
=E(3) ×E(x) + E(2) = E(3) ×E(x+ 1)
=E(3) ×E(x+x) + E(2) = E(3) ×E(2x) + E(2)
=E(3) ×E(x×2) + E(2) = E(6) ×E(x) + E(2)
=E(6) ×E(x) + E(2) = E(6x) + E(2)
Therefore, the decrypted result that Alice receives is 6x+ 2.
Problem 2. Bob wants to perform the computation 4x2−2x+ 5 on his encrypted data using
a partially homomorphic encryption scheme that supports addition but not multiplication. If he
encrypts xas E(x) = x2+3x−1, calculate the result that Bob will receive after the server performs
the computation using this homomorphic property.
Solution 2. Given that E(4x2−2x+ 5) = E(4x2) + E(−2x) + E(5), we use the homomorphic
property of addition:
=E(4) ×E(x2) + E(−2) ×E(x) + E(5)
=E(4) ×(x2+ 3x−1) + E(−2) ×x2+E(5)
=E(4x2+ 12x−4) + E(−2x2) + E(5)
=E(2x2+ 12x+ 1)
Therefore, the result that Bob will receive after the server performs the computation is 2x2+
12x+ 1.
19 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to send sensitive medical data to Bob using homomorphic encryp-
tion. She encrypts the data with a homomorphic scheme that supports addition and multiplication
operations. The plaintext data is x= 7, and the encryption function is defined as:
E(x) = x+rmod q
where ris a random number from the range [0,10] and q= 13. Calculate the encryption of xand
determine what operations Bob can perform on the encrypted data.
Solution 1. Given: x= 7,q= 13,r∈[0,10]
First, we randomly select a value of rfrom the range [0,10]. Let’s choose r= 3.
The encryption of xis then:
E(x) = x+rmod q= 7 + 3 mod 13 = 10
Therefore, the encryption of xis 10. Bob can now perform additions and multiplications on the
encrypted data without decrypting it.
20 19. HOMOMORPHIC ENCRYPTION IN FINANCIAL TRANSACTIONS
Problem 19. A bank wants to use homomorphic encryption to securely calculate the total
balance of its customers without knowing the individual balances. The bank assigns encrypted
values to represent the balances of three customers as follows: Customer A’s balance is encrypted
as 10, Customer B’s balance is encrypted as 15, and Customer C’s balance is encrypted as 8.
The bank uses the homomorphic property to perform secure calculations without decrypting the
balances.
a) If the bank wants to calculate the sum of the balances of Customer A and Customer B using
homomorphic addition, what encrypted value represents this sum?
b) If the bank wants to calculate the product of the balances of Customer A and Customer C
using homomorphic multiplication, what encrypted value represents this product?
c) Using the result from part a, if the bank also wants to subtract the balance of Customer B from
the sum of Customer A and B, what encrypted value represents this subtraction using homomorphic
subtraction?
Solution 19.
a) To calculate the sum of the balances of Customer A and Customer B using homomorphic
addition, we simply add their encrypted values:
Encrypted sum = Encrypted value of A + Encrypted value of B = 10 + 15 = 25.
Therefore, the encrypted value representing the sum of the balances of Customer A and Cus-
tomer B is 25.
b) To calculate the product of the balances of Customer A and Customer C using homomorphic
multiplication, we multiply their encrypted values:
Encrypted product = Encrypted value of A ×Encrypted value of C = 10 ×8 = 80.
Therefore, the encrypted value representing the product of the balances of Customer A and
Customer C is 80.
c) Using the result from part a, we have the encrypted value representing the sum of the bal-
ances of Customer A and B as 25. To subtract the balance of Customer B (15) from this sum using
homomorphic subtraction, we perform:
Encrypted subtraction = Encrypted sum - Encrypted value of B = 25 −15 = 10.
Therefore, the encrypted value representing the subtraction of the balance of Customer B from
the sum of Customer A and B is 10.
21 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where Alice wants to perform a homomorphic encryption
operation using the Paillier cryptosystem. She has two plaintext values m1= 7 and m2= 5, and
random parameters p= 17,q= 11,n=p·q,g=n+ 1. Assume that the public key is (n, g).
a) Encrypt both plaintext values m1and m2using the Paillier cryptosystem. b) Compute the
homomorphic sum of the ciphertexts corresponding to m1and m2. c) Decrypt the result of the
homomorphic sum to obtain the plaintext value.
Solution 1. a) To encrypt a plaintext value min the Paillier cryptosystem, we use the encryption
function E(m) = gm·rnmod n2, where ris a random number.
For m1= 7:E(7) = g7·rnmod n2= (287·r187 mod 1872)
For m2= 5:E(5) = g5·rnmod n2= (285·r187 mod 1872)
b) To compute the homomorphic sum of two ciphertexts in the Paillier cryptosystem, we multiply
the ciphertexts together. Therefore, the homomorphic sum of m1and m2would be: E(m1)×
E(m2) = (287·r187 mod 1872)×(285·r187 mod 1872)
c) To decrypt the result of the homomorphic sum, we use the decryption function D(c) = L(cλ
mod n2)·µmod n, where L(x) = x−1
n,λ=lcm(p−1, q −1), and µ=L(gλmod n2)−1mod n.
First, we compute the homomorphic sum: E(m1)×E(m2) = [step to multiply the ciphertexts]
Then, we decrypt the result as follows: D(E(m1)×E(m2)) = [steps to decrypt and obtain the
plaintext value]
22 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where a data scientist wants to securely compute the average
of a list of numbers using homomorphic encryption. The data scientist encrypts the numbers using
a homomorphic encryption scheme and performs the necessary computation. If the list of numbers
to be averaged is encrypted as follows:
- Number 1: E(5) = 15 - Number 2: E(8) = 26 - Number 3: E(3) = 13 - Number 4: E(10) = 34
Determine the encrypted result after computing the average and decrypt it to obtain the final
result.
Solution 1.
a) To compute the average homomorphically, we need to sum all the encrypted numbers and
divide the result by the total count of numbers.
The sum of the encrypted numbers:
E(5) + E(8) + E(3) + E(10) = 15 + 26 + 13 + 34 = 88
b) Now, we need to divide the encrypted sum by the total count of numbers, which is 4:
E(average) = 88
4= 22
Thus, the encrypted result after computing the average is 22.
c) To obtain the final result, we need to decrypt the encrypted average using the homomorphic
encryption scheme’s decryption function.
Decryption:
D(22) = 22
2= 11
Therefore, the final result of averaging the list of numbers is 11.
23 22. HOMOMORPHIC ENCRYPTION IN DATA ANALYTICS
Problem 22. Consider a scenario where a data scientist wants to perform statistical analysis on
encrypted data using homomorphic encryption. The data scientist has two integer values encrypted
using a homomorphic encryption scheme: a=Enc(3) and b=Enc(5).
a) Compute the encrypted value of a+b.
b) Compute the encrypted value of 2a−b.
Solution 22.
a) To compute the encrypted value of a+b, we need to use the properties of homomorphic
encryption. In a partially homomorphic encryption scheme, we can perform addition on encrypted
values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of a+bis Enc(3) + Enc(5) = Enc(3 + 5) = Enc(8).
Therefore, the encrypted value of a+bis Enc(8).
b) To compute the encrypted value of 2a−b, we again utilize the properties of homomorphic
encryption. We can perform scalar multiplication and subtraction on encrypted values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of 2a−bis 2×Enc(3) −Enc(5) = Enc(2 ×3−5) = Enc(1).
Therefore, the encrypted value of 2a−bis Enc(1).
24 23. HOMOMORPHIC ENCRYPTION IN MACHINE LEARNING
Problem 23. Consider a machine learning model that uses homomorphic encryption for privacy-
preserving computations. The model receives encrypted features X={x1, x2, x3}and encrypted
labels Y={y1, y2, y3}. After performing the necessary computations, the encrypted predictions
are Z={z1, z2, z3}. Assume the computations follow the equation: zi=w×xi+b, where wis the
weight, bis the bias, and xi,yi, and ziare encrypted values.
Given: x1= 5,y1= 7,z1= 42 (all values encrypted) x2= 3,y2= 5, and z2= 24 (all values
encrypted)
a) Calculate the weight w.
b) Calculate the bias b.
Solution 23.
a) To find the weight w, we can use the formula zi=w×xi+b.
For i= 1:
z1=w×x1+b
42 = w×5 + b
For i= 2:
z2=w×x2+b
24 = w×3 + b
Solving these two equations simultaneously, we get:
w=z1−z2
x1−x2
=42 −24
5−3=18
2= 9
Therefore, the weight w= 9.
b) To find the bias b, we can substitue w= 9 into one of the equations. Let’s use the first
equation when i= 1:
42 = 9 ×5 + b
42 = 45 + b
b= 42 −45 = −3
Therefore, the bias b=−3.
25 Cryptographic Applications of Homomorphic Encryption
Problem 1. In an e-voting system that uses homomorphic encryption, the votes for candidates
A,B, and Care encrypted as follows: a= 6,b= 8, and c= 4, respectively. The encryption scheme
uses additive homomorphic properties. The result of multiplying the ciphertexts for candidates A
and Bis calculated as a×b= 30. Find out the encrypted vote for candidate C.
Solution 1. Given that the encryption scheme is additive homomorphic, we can calculate the
encrypted vote for candidate Cusing the properties of homomorphic encryption.
We know that a×brepresents the product of ciphertexts for candidates Aand B. Thus, a×b=
30.
Now, to find the encrypted vote for candidate C, we can utilize the additive homomorphic prop-
erty, which states that multiplying ciphertexts corresponds to adding plaintexts. Therefore, the
encrypted vote for candidate Cwill be:
a×b+c= 30 + c
Given a= 6,b= 8, and c= 4, substituting these values:
30 + 4 = 34
Therefore, the encrypted vote for candidate Cis 34.
26 25. HOMOMORPHIC ENCRYPTION IN SECURE COMMUNICATION PROTOCOLS
Problem 25. Alice wants to perform a secure computation on encrypted data using a homo-
morphic encryption scheme. She has two encrypted values c1and c2, where c1=Encpk(7) and
c2=Encpk(5), encrypted under a public key pk. She wants to calculate the sum and product of
the decrypted values without revealing the encryption key. Assume the homomorphic encryption
scheme supports both addition and multiplication operations homomorphically.
Solution 25. a) To calculate the sum of the decrypted values, Alice can perform homomorphic
addition on the encrypted values c1and c2. Let csum =c1⊕c2.
The decryption of csum will give the sum of the decrypted values:
Decsk(csum) = Decsk(c1⊕c2)
=Decsk(Encpk(7) ⊕Encpk (5))
=Decsk(Encpk(7 + 5))
=Decsk(Encpk(12))
= 12
Therefore, the sum of the decrypted values is 12.
b) To calculate the product of the decrypted values, Alice can perform homomorphic multipli-
cation on the encrypted values c1and c2. Let cprod =c1⊗c2.
The decryption of cprod will give the product of the decrypted values:
Decsk(cprod) = Decsk(c1⊗c2)
=Decsk(Encpk(7) ⊗Encpk (5))
=Decsk(Encpk(7 ×5))
=Decsk(Encpk(35))
= 35
Therefore, the product of the decrypted values is 35.
3 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to perform a homomorphic encryption on a message m= 7 using a fully
homomorphic encryption scheme. The public key for this scheme is n= 13 and the encryption
function is defined as E(x) = x2mod n. Calculate the encrypted message.
Solution 1. To encrypt the message using the homomorphic encryption scheme, we need to
compute E(m):
E(m) = E(7) = 72mod 13 = 49 mod 13 = 10
Therefore, the encrypted message is 10.
4 Cryptographic Applications of Homomorphic Encryption
Problem 2. Bob wants to perform a homomorphic addition on two encrypted messages. The
encrypted messages are c1= 8 and c2= 12, and the public key for the homomorphic encryption
scheme is n= 17. If the encryption function is defined as E(x) = x2mod n, calculate the result
of adding the two encrypted messages together.
Solution 2. To perform homomorphic addition on the encrypted messages, we first need to
decrypt the messages, add them together, and then re-encrypt the sum:
Step 1: Decrypt the messages
C1=c
n+1
4
1mod n= 85mod 17 = 8
C2=c
n+1
4
2mod n= 125mod 17 = 12
Step 2: Add the decrypted messages
D=C1+C2= 8 + 12 = 20
Step 3: Re-encrypt the sum
E(D) = D2mod 17 = 202mod 17 = 400 mod 17 = 11
Therefore, the result of adding the two encrypted messages together is 11.
5 4. LIMITATIONS OF HOMOMORPHIC ENCRYPTION
Problem 4. Consider a fully homomorphic encryption scheme where the ciphertext space is
integers modulo N= 29. Alice wants to perform the following computations:
a) Encrypt the integer 9 using the encryption function.
b) Add two encrypted integers, the encryption of 5 and 12.
c) Multiply an encrypted integer, the encryption of 3, by an encrypted integer, the encryption of
7.
Solution 4.
a) To encrypt the integer 9, we first need to choose a public key (N, q, h)for the encryption
scheme. Let q= 31 and h= 6. Then the encryption function is defined as follows:
Encrypt(m) = mh + 2rmod N
where m= 9, and ris a random integer modulo N. Let’s choose r= 7. Thus, the encryption
of 9 is:
Encrypt(9) = 9∗6+2∗7 mod 29 = 54 + 14 mod 29 = 68 mod 29 = 10
Therefore, the encryption of 9 is 10.
b) To add two encrypted integers, we simply add them modulo N. Let’s consider the encryption
of 5 and 12:
Encrypt(5) = 5∗6+2∗7 mod 29 = 32 mod 29 = 3
Encrypt(12) = 12 ∗6+2∗7 mod 29 = 74 mod 29 = 16
Adding the two encrypted integers:
Encrypt(5) +Encrypt(12) = 3 + 16 mod 29 = 19
Therefore, the sum of the encrypted integers 5 and 12 is 19.
c) For multiplication of two encrypted integers, we multiply the two ciphertexts modulo N. Let’s
multiply the encryption of 3 and 7:
Encrypt(3) = 3∗6+2∗7 mod 29 = 20
Encrypt(7) = 7∗6+2∗7 mod 29 = 49 mod 29 = 20
Multiplying the two encrypted integers:
Encrypt(3) ·Encrypt(7) = 20 ∗20 mod 29 = 400 mod 29 = 16
Therefore, the product of the encrypted integers 3 and 7 is 16.
6 Cryptographic Applications of Homomorphic Encryption
Problem: Suppose we have two ciphertexts c1and c2encrypted under the same homomorphic
encryption scheme, and we want to compute the product of the plaintexts they represent. Let the
decryption function be Dec(·).
Given that Dec(c1) = 7 and Dec(c2) = 4, and we know that the homomorphic encryption
scheme supports homomorphic multiplication, calculate the decryption of the product of the plain-
texts represented by c1and c2, i.e., find Dec(c1×c2).
Solution: Since the homomorphic encryption scheme supports homomorphic multiplication,
we can calculate the product of the plaintexts without decrypting c1and c2individually.
Let’s assume that the product of the plaintexts represented by c1and c2is denoted as m1×m2.
Since Dec(c1) = 7 and Dec(c2)=4, we have m1= 7 and m2= 4.
Now, to find Dec(c1×c2), we calculate the product of the plaintexts represented by c1and c2,
which is m1×m2= 7 ×4 = 28.
Therefore, Dec(c1×c2) = 28.
7 6. SCALABILITY PROBLEMS IN HOMOMORPHIC ENCRYPTION
Problem 6. Consider a homomorphic encryption scheme where the ciphertext size grows
linearly with the plaintext size. Suppose we have a plaintext vector p= [3,1,4,1,5] encrypted
using this scheme and a homomorphic operation that requires adding two ciphertexts together. If
the size of each ciphertext is 4 bytes, what is the total ciphertext size required for this operation?
Solution 6. a) Given that the plaintext vector p= [3,1,4,1,5] is encrypted using a homomorphic
encryption scheme with a ciphertext size of 4 bytes each, the total ciphertext size required for a
homomorphic addition operation can be calculated as follows:
b) Since the ciphertext size grows linearly with the plaintext size, the total ciphertext size re-
quired for encrypting the plaintext vector pis determined by multiplying the number of plaintext
elements by the size of each ciphertext. For a plaintext vector of length n, the total ciphertext size
is given by:
Total ciphertext size =n×Size of each ciphertext
In this case, n= 5 (as there are 5 elements in the plaintext vector) and the size of each ciphertext
is 4 bytes. Substituting these values into the formula:
Total ciphertext size = 5 ×4 = 20 bytes
Thus, the total ciphertext size required for a homomorphic addition operation on the given plain-
text vector using a 4-byte ciphertext scheme would be 20 bytes.
8 Cryptographic Applications of Homomorphic Encryption
Problem: Consider a fully homomorphic encryption scheme where the public key is (n= 5, q =
7) and the secret key is (a= 3).
a) Encrypt the plaintext message m= 4.
b) Perform a homomorphic addition on the ciphertexts corresponding to m1= 4 and m2= 3.
c) Perform a homomorphic multiplication on the ciphertext corresponding to m3= 2.
Solution:
a) To encrypt the plaintext message m= 4, we use the encryption function:
c= (a·r+ 2m) mod q
where ris a random integer. Plugging in m= 4,a= 3,q= 7, and choosing r= 2 for
demonstration purposes:
c= (3 ·2+2·4) mod 7 = (6 + 8) mod 7 = 14 mod 7 = 0
Therefore, the encrypted ciphertext for m= 4 is c= 0.
b) For homomorphic addition on two ciphertexts c1and c2corresponding to m1= 4 and m2= 3,
we can simply add the ciphertexts together modulo q:
cadd = (c1+c2) mod q
Given c1= 0 and c2= (3 ·2+2·3) mod 7 = 12 mod 7 = 5, we have:
cadd = (0 + 5) mod 7 = 5
Therefore, the resulting ciphertext after homomorphic addition is cadd = 5.
c) For homomorphic multiplication on the ciphertext corresponding to m3= 2, we perform the
multiplication modulo q:
cmul = (c·ma
3) mod q
Given c= 0 and m3= 2, we have:
cmul = (0 ·23) mod 7 = 0
Therefore, the resulting ciphertext after homomorphic multiplication is cmul = 0.
9 8. ERROR RATES IN HOMOMORPHIC ENCRYPTION
Problem 8. In a homomorphic encryption scheme, the probability of an error occurring during
the encryption process is 0.05. If a computation involves 20 homomorphic operations, what is the
probability that at least one error occurs during the computation?
Solution 8. Let’s denote the probability of an error occurring during a single homomorphic
operation as p= 0.05. The probability of no error occurring during a single operation is 1−p= 0.95.
The probability that at least one error occurs during the 20 computations can be calculated
using the complement rule (the probability of the event happening is 1 minus the probability of the
event not happening).
The probability of no error occurring during all 20 computations is (0.95)20.
Therefore, the probability of at least one error occurring is:
P(at least one error) = 1 −P(no error in 20 computations)
= 1 −(0.95)20
≈1−0.358485
≈0.641515 (approximately)
So, the probability that at least one error occurs during the computation involving 20 homomor-
phic operations is approximately 0.641515, or 64.15
10 9. KEY MANAGEMENT CHALLENGES IN HOMOMORPHIC ENCRYPTION
Problem 9. Consider a homomorphic encryption scheme where the public key is (n, e)and the
private key is (n, d), where n= 187,e= 7, and d= 23. Given a plaintext message m= 42, encrypt
the message using the public key and then decrypt the ciphertext using the private key.
Solution 9. a) To encrypt the message m= 42 using the public key (n, e), we compute the
ciphertext cusing the encryption function: c≡me(mod n).
Substitute m= 42,e= 7, and n= 187 into the encryption function:
c≡427(mod 187)
Calculating 427(mod 187):
427= 1406408618242
1406408618242 ≡29 (mod 187)
Therefore, the ciphertext cis 29.
b) To decrypt the ciphertext c= 29 using the private key (n, d), we compute the decrypted
message musing the decryption function: m≡cd(mod n).
Substitute c= 29,d= 23, and n= 187 into the decryption function:
m≡2923 (mod 187)
Calculating 2923 (mod 187):
2923 = 49298393010889
49298393010889 ≡42 (mod 187)
Therefore, the decrypted message mis 42, which matches the original plaintext message.
11 10. RELIABILITY CONCERNS IN HOMOMORPHIC ENCRYPTION
Problem 10. Consider a homomorphic encryption scheme where the key generation process
has a 5% chance of generating an incorrect key. Suppose a ciphertext is encrypted using such an
incorrect key.
a) What is the effect on the decryption process if the key is incorrect?
b) Calculate the probability that at least one out of five ciphertexts is decrypted incorrectly due
to a wrong key.
Solution 10.
a) If a ciphertext is encrypted using an incorrect key in a homomorphic encryption scheme,
the decryption process will result in an incorrect plaintext. This is because the decryption process
relies on the correctness of the key to properly recover the original plaintext from the ciphertext.
b) In this case, the probability of a key being incorrect is 5%, so the probability of a key being
correct is 95%, or 0.95. Since there are five ciphertexts, the probability of at least one being
decrypted incorrectly is equal to 1 minus the probability that all five are decrypted correctly.
Let pbe the probability that a ciphertext is decrypted correctly using the correct key. Therefore,
the probability that a ciphertext is decrypted incorrectly using the incorrect key is 1−p.
The probability that all five ciphertexts are decrypted correctly is p5, and the probability that at
least one is decrypted incorrectly is 1−p5.
Substitute p= 0.95 into the formula:
Probability of at least one incorrect decryption = 1 −(0.95)5
= 1 −0.77378
= 0.22622
Therefore, the probability that at least one out of five ciphertexts is decrypted incorrectly due to
a wrong key is approximately 0.22622 (or 22.622%).
12 11. TRUSTWORTHINESS OF HOMOMORPHIC ENCRYPTION
Problem 11. Consider a homomorphic encryption scheme where the encryption function E
and the decryption function Dare defined as follows:
E(x) = x2mod 17
D(y) = √ymod 17
Suppose we want to perform homomorphic addition and multiplication on two plaintext values.
Specifically, given the plaintext values m1= 4 and m2= 11, find the encryption of the sum m1+m2
and the encryption of the product m1×m2using the above encryption scheme. Also, decrypt the
results to obtain the plaintext values.
Solution 11.
a) To find the encryption of the sum m1+m2, we first calculate the sum modulo 17:
m1+m2= 4 + 11 = 15
Next, we calculate the encryption using the encryption function E:
E(15) = 152mod 17 = 225 mod 17 = 4
Therefore, the encryption of the sum m1+m2is 4.
b) To find the encryption of the product m1×m2, we first calculate the product modulo 17:
m1×m2= 4 ×11 = 44
Next, we calculate the encryption using the encryption function E:
E(44) = 442mod 17 = 1936 mod 17 = 16
Therefore, the encryption of the product m1×m2is 16.
c) To decrypt the results, we use the decryption function D:
For the encrypted sum 4:
D(4) = √4 mod 17 = 2
Thus, the decrypted plaintext value for the sum is 2.
For the encrypted product 16:
D(16) = √16 mod 17 = 4
Therefore, the decrypted plaintext value for the product is 4.
13 12. COMPLEXITY IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 12. Consider a homomorphic encryption scheme where the encryption function is
defined as E(m) = m2mod 13.
a) Encrypt the message m= 5.
b) Perform the homomorphic addition of two ciphertexts encrypted with the values m1= 3 and
m2= 4.
c) Decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13.
Solution 12.
a) We are given the encryption function E(m) = m2mod 13. To encrypt the message m= 5,
we substitute m= 5 into the encryption function:
E(5) = 52mod 13 = 25 mod 13 = 12.
Therefore, the encrypted ciphertext for the message m= 5 is 12.
b) To perform homomorphic addition, we calculate the sum of the ciphertexts created by en-
crypting m1= 3 and m2= 4:
E(3) = 32mod 13 = 9 mod 13 = 9
E(4) = 42mod 13 = 16 mod 13 = 3
Now, we add the ciphertexts: 9 + 3 = 12.
Therefore, the homomorphically added ciphertext is 12.
c) To decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13, we substitute c= 12 into the decryption function:
D(12) = √12 mod 13 ≈3.4641 mod 13 ≈3
Therefore, the decrypted message corresponding to the ciphertext 12 is 3.
14 13. PRIVACY RISKS OF HOMOMORPHIC ENCRYPTION
Problem 13. Consider a scenario where a company wants to use homomorphic encryption to
compute the sum of salaries of its employees without decrypting the individual salaries to ensure
privacy. The encryption scheme being used is a fully homomorphic encryption scheme that sup-
ports addition and multiplication operations. The company has encrypted the salaries using the
homomorphic encryption scheme, with each salary encoded as an integer.
The encrypted salaries are as follows: e1= 24,e2= 37,e3= 19, and e4= 42, where each eiis
the encrypted salary of employee i.
a) Compute the encrypted sum of the salaries, Enc(24 + 37 + 19 + 42).
b) The company also wants to compute the encrypted product of the salaries. Find Enc(24 ×
37 ×19 ×42).
c) If the company decrypts the sum of the encrypted salaries, will it reveal any information about
the individual salaries? Justify your answer.
Solution 13.
a) To compute the encrypted sum of the salaries, we can directly add the encrypted salaries:
Enc(24 + 37 + 19 + 42) = e1+e2+e3+e4= 24 + 37 + 19 + 42 = 122.
Therefore, the encrypted sum of the salaries is Enc(24 + 37 + 19 + 42) = 122.
b) To compute the encrypted product of the salaries, we can multiply the encrypted salaries:
Enc(24 ×37 ×19 ×42) = e1×e2×e3×e4= 24 ×37 ×19 ×42 = 387216.
Therefore, the encrypted product of the salaries is Enc(24 ×37 ×19 ×42) = 387216.
c) Homomorphic encryption provides the ability to perform computations on encrypted data
without decrypting it. When the company decrypts only the sum of the encrypted salaries, it will
not reveal any information about the individual salaries. This is because the encryption scheme
used is secure and ensures that the individual encrypted values remain confidential even after the
computation.
15 14. HOMOMORPHIC ENCRYPTION IN REAL-WORLD APPLICATIONS
Problem 14. Consider a scenario where a data processing company wants to outsource the
computation of the average salary of its employees to a cloud server using homomorphic encryp-
tion. The employees’ salaries are encrypted using a partially homomorphic encryption scheme that
supports addition and multiplication operations. Each employee’s salary is encrypted as follows:
E(s) = s2mod 11, where sis the plaintext salary.
a) If the company has four employees with salaries s1= 3,s2= 5,s3= 4, and s4= 6, calculate
the encrypted values for each of their salaries.
b) Compute the sum of the encrypted salaries.
c) Using homomorphic properties, decrypt the result to obtain the average salary of the em-
ployees.
Solution 14. a) To calculate the encrypted values for each employee’s salary:
Given E(s) = s2mod 11,
For s1= 3:E(3) = 32mod 11 = 9 mod 11 = 9
For s2= 5:E(5) = 52mod 11 = 25 mod 11 = 3
For s3= 4:E(4) = 42mod 11 = 16 mod 11 = 5
For s4= 6:E(6) = 62mod 11 = 36 mod 11 = 3
Therefore, the encrypted values for the employees’ salaries are: 9, 3, 5, 3.
b) To compute the sum of the encrypted salaries:
Sum of encrypted salaries = 9 + 3 + 5 + 3 = 20.
c) Since the encryption scheme supports multiplication and addition homomorphically, we can
decrypt the result of the sum by computing the inverse operation of squaring modulo 11, which is
finding the square root modulo 11.
20 ≡x2mod 11
Calculating the square root modulo 11:
x≡ ±√20 mod 11
x≡ ±4 mod 11
Hence, the possible decrypted values are 4 and 7. Since 4 is the correct average salary of the
employees, the decrypted average salary is 4.
16 Cryptographic Applications of Homomorphic Encryption
Problem: Using a fully homomorphic encryption scheme, Alice wants to perform the following
computation: E(m1)·E(m2) + E(m3)−E(m4), where Edenotes the encryption function and
m1= 5,m2= 3,m3= 7, and m4= 2. The encryption function transforms each message to their
encrypted form using the public key.
Assume the following encrypted values are obtained: E(m1) = 10,E(m2) = 8,E(m3) = 15,
and E(m4) = 5. Alice wishes to calculate the result of the above computation without decrypting
any values.
Solution:
Given: E(m1) = 10,E(m2)=8,E(m3) = 15, and E(m4) = 5.
a) Calculate the result of the computation E(m1)·E(m2).
b) Calculate the result of the computation E(m1)·E(m2) + E(m3).
c) Calculate the final result of the original computation.
Solution:
a) E(m1)·E(m2) = 10 ·8 = 80.
b) E(m1)·E(m2) + E(m3) = 80 + 15 = 95.
c) Finally, the original computation E(m1)·E(m2) + E(m3)−E(m4)becomes 95 −5 = 90.
Therefore, the final result of the computation without decrypting any values is 90.
17 16. USABILITY CHALLENGES OF HOMOMORPHIC ENCRYPTION
Problem 16. Consider a homomorphic encryption scheme where the encryption function is
E(x) = x2mod 13. Encrypt the message m= 3 using this scheme.
Solution 16. To encrypt the message m= 3, we substitute x= 3 into the encryption function
E(x) = x2mod 13.
Therefore, the encrypted message is:
E(3) = 32mod 13 = 9 mod 13 = 9
So, the encrypted message for m= 3 is 9.
18 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to securely outsource a computation to a cloud server using fully homo-
morphic encryption. She encrypts her input data xusing the homomorphic encryption scheme, and
sends it to the server. The server performs some computation on the encrypted data and returns
the result yto Alice. If the encryption scheme is fully homomorphic with the following properties:
- Addition: E(a) + E(b) = E(a+b)- Multiplication: E(a)×E(b) = E(a×b)
and the server computes E(3x+ 2), what will be the decrypted result that Alice receives?
Solution 1. Given that E(3x+2) = E(3)×E(x)+E(2), we expand this using the homomorphic
properties:
=E(3) ×E(x) + E(2)
=E(3) ×E(x) + E(2 ×1)
=E(3) ×E(x) + E(2) = E(3) ×E(x+ 1)
=E(3) ×E(x+x) + E(2) = E(3) ×E(2x) + E(2)
=E(3) ×E(x×2) + E(2) = E(6) ×E(x) + E(2)
=E(6) ×E(x) + E(2) = E(6x) + E(2)
Therefore, the decrypted result that Alice receives is 6x+ 2.
Problem 2. Bob wants to perform the computation 4x2−2x+ 5 on his encrypted data using
a partially homomorphic encryption scheme that supports addition but not multiplication. If he
encrypts xas E(x) = x2+3x−1, calculate the result that Bob will receive after the server performs
the computation using this homomorphic property.
Solution 2. Given that E(4x2−2x+ 5) = E(4x2) + E(−2x) + E(5), we use the homomorphic
property of addition:
=E(4) ×E(x2) + E(−2) ×E(x) + E(5)
=E(4) ×(x2+ 3x−1) + E(−2) ×x2+E(5)
=E(4x2+ 12x−4) + E(−2x2) + E(5)
=E(2x2+ 12x+ 1)
Therefore, the result that Bob will receive after the server performs the computation is 2x2+
12x+ 1.
19 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to send sensitive medical data to Bob using homomorphic encryp-
tion. She encrypts the data with a homomorphic scheme that supports addition and multiplication
operations. The plaintext data is x= 7, and the encryption function is defined as:
E(x) = x+rmod q
where ris a random number from the range [0,10] and q= 13. Calculate the encryption of xand
determine what operations Bob can perform on the encrypted data.
Solution 1. Given: x= 7,q= 13,r∈[0,10]
First, we randomly select a value of rfrom the range [0,10]. Let’s choose r= 3.
The encryption of xis then:
E(x) = x+rmod q= 7 + 3 mod 13 = 10
Therefore, the encryption of xis 10. Bob can now perform additions and multiplications on the
encrypted data without decrypting it.
20 19. HOMOMORPHIC ENCRYPTION IN FINANCIAL TRANSACTIONS
Problem 19. A bank wants to use homomorphic encryption to securely calculate the total
balance of its customers without knowing the individual balances. The bank assigns encrypted
values to represent the balances of three customers as follows: Customer A’s balance is encrypted
as 10, Customer B’s balance is encrypted as 15, and Customer C’s balance is encrypted as 8.
The bank uses the homomorphic property to perform secure calculations without decrypting the
balances.
a) If the bank wants to calculate the sum of the balances of Customer A and Customer B using
homomorphic addition, what encrypted value represents this sum?
b) If the bank wants to calculate the product of the balances of Customer A and Customer C
using homomorphic multiplication, what encrypted value represents this product?
c) Using the result from part a, if the bank also wants to subtract the balance of Customer B from
the sum of Customer A and B, what encrypted value represents this subtraction using homomorphic
subtraction?
Solution 19.
a) To calculate the sum of the balances of Customer A and Customer B using homomorphic
addition, we simply add their encrypted values:
Encrypted sum = Encrypted value of A + Encrypted value of B = 10 + 15 = 25.
Therefore, the encrypted value representing the sum of the balances of Customer A and Cus-
tomer B is 25.
b) To calculate the product of the balances of Customer A and Customer C using homomorphic
multiplication, we multiply their encrypted values:
Encrypted product = Encrypted value of A ×Encrypted value of C = 10 ×8 = 80.
Therefore, the encrypted value representing the product of the balances of Customer A and
Customer C is 80.
c) Using the result from part a, we have the encrypted value representing the sum of the bal-
ances of Customer A and B as 25. To subtract the balance of Customer B (15) from this sum using
homomorphic subtraction, we perform:
Encrypted subtraction = Encrypted sum - Encrypted value of B = 25 −15 = 10.
Therefore, the encrypted value representing the subtraction of the balance of Customer B from
the sum of Customer A and B is 10.
21 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where Alice wants to perform a homomorphic encryption
operation using the Paillier cryptosystem. She has two plaintext values m1= 7 and m2= 5, and
random parameters p= 17,q= 11,n=p·q,g=n+ 1. Assume that the public key is (n, g).
a) Encrypt both plaintext values m1and m2using the Paillier cryptosystem. b) Compute the
homomorphic sum of the ciphertexts corresponding to m1and m2. c) Decrypt the result of the
homomorphic sum to obtain the plaintext value.
Solution 1. a) To encrypt a plaintext value min the Paillier cryptosystem, we use the encryption
function E(m) = gm·rnmod n2, where ris a random number.
For m1= 7:E(7) = g7·rnmod n2= (287·r187 mod 1872)
For m2= 5:E(5) = g5·rnmod n2= (285·r187 mod 1872)
b) To compute the homomorphic sum of two ciphertexts in the Paillier cryptosystem, we multiply
the ciphertexts together. Therefore, the homomorphic sum of m1and m2would be: E(m1)×
E(m2) = (287·r187 mod 1872)×(285·r187 mod 1872)
c) To decrypt the result of the homomorphic sum, we use the decryption function D(c) = L(cλ
mod n2)·µmod n, where L(x) = x−1
n,λ=lcm(p−1, q −1), and µ=L(gλmod n2)−1mod n.
First, we compute the homomorphic sum: E(m1)×E(m2) = [step to multiply the ciphertexts]
Then, we decrypt the result as follows: D(E(m1)×E(m2)) = [steps to decrypt and obtain the
plaintext value]
22 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where a data scientist wants to securely compute the average
of a list of numbers using homomorphic encryption. The data scientist encrypts the numbers using
a homomorphic encryption scheme and performs the necessary computation. If the list of numbers
to be averaged is encrypted as follows:
- Number 1: E(5) = 15 - Number 2: E(8) = 26 - Number 3: E(3) = 13 - Number 4: E(10) = 34
Determine the encrypted result after computing the average and decrypt it to obtain the final
result.
Solution 1.
a) To compute the average homomorphically, we need to sum all the encrypted numbers and
divide the result by the total count of numbers.
The sum of the encrypted numbers:
E(5) + E(8) + E(3) + E(10) = 15 + 26 + 13 + 34 = 88
b) Now, we need to divide the encrypted sum by the total count of numbers, which is 4:
E(average) = 88
4= 22
Thus, the encrypted result after computing the average is 22.
c) To obtain the final result, we need to decrypt the encrypted average using the homomorphic
encryption scheme’s decryption function.
Decryption:
D(22) = 22
2= 11
Therefore, the final result of averaging the list of numbers is 11.
23 22. HOMOMORPHIC ENCRYPTION IN DATA ANALYTICS
Problem 22. Consider a scenario where a data scientist wants to perform statistical analysis on
encrypted data using homomorphic encryption. The data scientist has two integer values encrypted
using a homomorphic encryption scheme: a=Enc(3) and b=Enc(5).
a) Compute the encrypted value of a+b.
b) Compute the encrypted value of 2a−b.
Solution 22.
a) To compute the encrypted value of a+b, we need to use the properties of homomorphic
encryption. In a partially homomorphic encryption scheme, we can perform addition on encrypted
values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of a+bis Enc(3) + Enc(5) = Enc(3 + 5) = Enc(8).
Therefore, the encrypted value of a+bis Enc(8).
b) To compute the encrypted value of 2a−b, we again utilize the properties of homomorphic
encryption. We can perform scalar multiplication and subtraction on encrypted values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of 2a−bis 2×Enc(3) −Enc(5) = Enc(2 ×3−5) = Enc(1).
Therefore, the encrypted value of 2a−bis Enc(1).
24 23. HOMOMORPHIC ENCRYPTION IN MACHINE LEARNING
Problem 23. Consider a machine learning model that uses homomorphic encryption for privacy-
preserving computations. The model receives encrypted features X={x1, x2, x3}and encrypted
labels Y={y1, y2, y3}. After performing the necessary computations, the encrypted predictions
are Z={z1, z2, z3}. Assume the computations follow the equation: zi=w×xi+b, where wis the
weight, bis the bias, and xi,yi, and ziare encrypted values.
Given: x1= 5,y1= 7,z1= 42 (all values encrypted) x2= 3,y2= 5, and z2= 24 (all values
encrypted)
a) Calculate the weight w.
b) Calculate the bias b.
Solution 23.
a) To find the weight w, we can use the formula zi=w×xi+b.
For i= 1:
z1=w×x1+b
42 = w×5 + b
For i= 2:
z2=w×x2+b
24 = w×3 + b
Solving these two equations simultaneously, we get:
w=z1−z2
x1−x2
=42 −24
5−3=18
2= 9
Therefore, the weight w= 9.
b) To find the bias b, we can substitue w= 9 into one of the equations. Let’s use the first
equation when i= 1:
42 = 9 ×5 + b
42 = 45 + b
b= 42 −45 = −3
Therefore, the bias b=−3.
25 Cryptographic Applications of Homomorphic Encryption
Problem 1. In an e-voting system that uses homomorphic encryption, the votes for candidates
A,B, and Care encrypted as follows: a= 6,b= 8, and c= 4, respectively. The encryption scheme
uses additive homomorphic properties. The result of multiplying the ciphertexts for candidates A
and Bis calculated as a×b= 30. Find out the encrypted vote for candidate C.
Solution 1. Given that the encryption scheme is additive homomorphic, we can calculate the
encrypted vote for candidate Cusing the properties of homomorphic encryption.
We know that a×brepresents the product of ciphertexts for candidates Aand B. Thus, a×b=
30.
Now, to find the encrypted vote for candidate C, we can utilize the additive homomorphic prop-
erty, which states that multiplying ciphertexts corresponds to adding plaintexts. Therefore, the
encrypted vote for candidate Cwill be:
a×b+c= 30 + c
Given a= 6,b= 8, and c= 4, substituting these values:
30 + 4 = 34
Therefore, the encrypted vote for candidate Cis 34.
26 25. HOMOMORPHIC ENCRYPTION IN SECURE COMMUNICATION PROTOCOLS
Problem 25. Alice wants to perform a secure computation on encrypted data using a homo-
morphic encryption scheme. She has two encrypted values c1and c2, where c1=Encpk(7) and
c2=Encpk(5), encrypted under a public key pk. She wants to calculate the sum and product of
the decrypted values without revealing the encryption key. Assume the homomorphic encryption
scheme supports both addition and multiplication operations homomorphically.
Solution 25. a) To calculate the sum of the decrypted values, Alice can perform homomorphic
addition on the encrypted values c1and c2. Let csum =c1⊕c2.
The decryption of csum will give the sum of the decrypted values:
Decsk(csum) = Decsk(c1⊕c2)
=Decsk(Encpk(7) ⊕Encpk (5))
=Decsk(Encpk(7 + 5))
=Decsk(Encpk(12))
= 12
Therefore, the sum of the decrypted values is 12.
b) To calculate the product of the decrypted values, Alice can perform homomorphic multipli-
cation on the encrypted values c1and c2. Let cprod =c1⊗c2.
The decryption of cprod will give the product of the decrypted values:
Decsk(cprod) = Decsk(c1⊗c2)
=Decsk(Encpk(7) ⊗Encpk (5))
=Decsk(Encpk(7 ×5))
=Decsk(Encpk(35))
= 35
Therefore, the product of the decrypted values is 35.
3 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to perform a homomorphic encryption on a message m= 7 using a fully
homomorphic encryption scheme. The public key for this scheme is n= 13 and the encryption
function is defined as E(x) = x2mod n. Calculate the encrypted message.
Solution 1. To encrypt the message using the homomorphic encryption scheme, we need to
compute E(m):
E(m) = E(7) = 72mod 13 = 49 mod 13 = 10
Therefore, the encrypted message is 10.
4 Cryptographic Applications of Homomorphic Encryption
Problem 2. Bob wants to perform a homomorphic addition on two encrypted messages. The
encrypted messages are c1= 8 and c2= 12, and the public key for the homomorphic encryption
scheme is n= 17. If the encryption function is defined as E(x) = x2mod n, calculate the result
of adding the two encrypted messages together.
Solution 2. To perform homomorphic addition on the encrypted messages, we first need to
decrypt the messages, add them together, and then re-encrypt the sum:
Step 1: Decrypt the messages
C1=c
n+1
4
1mod n= 85mod 17 = 8
C2=c
n+1
4
2mod n= 125mod 17 = 12
Step 2: Add the decrypted messages
D=C1+C2= 8 + 12 = 20
Step 3: Re-encrypt the sum
E(D) = D2mod 17 = 202mod 17 = 400 mod 17 = 11
Therefore, the result of adding the two encrypted messages together is 11.
5 4. LIMITATIONS OF HOMOMORPHIC ENCRYPTION
Problem 4. Consider a fully homomorphic encryption scheme where the ciphertext space is
integers modulo N= 29. Alice wants to perform the following computations:
a) Encrypt the integer 9 using the encryption function.
b) Add two encrypted integers, the encryption of 5 and 12.
c) Multiply an encrypted integer, the encryption of 3, by an encrypted integer, the encryption of
7.
Solution 4.
a) To encrypt the integer 9, we first need to choose a public key (N, q, h)for the encryption
scheme. Let q= 31 and h= 6. Then the encryption function is defined as follows:
Encrypt(m) = mh + 2rmod N
where m= 9, and ris a random integer modulo N. Let’s choose r= 7. Thus, the encryption
of 9 is:
Encrypt(9) = 9∗6+2∗7 mod 29 = 54 + 14 mod 29 = 68 mod 29 = 10
Therefore, the encryption of 9 is 10.
b) To add two encrypted integers, we simply add them modulo N. Let’s consider the encryption
of 5 and 12:
Encrypt(5) = 5∗6+2∗7 mod 29 = 32 mod 29 = 3
Encrypt(12) = 12 ∗6+2∗7 mod 29 = 74 mod 29 = 16
Adding the two encrypted integers:
Encrypt(5) +Encrypt(12) = 3 + 16 mod 29 = 19
Therefore, the sum of the encrypted integers 5 and 12 is 19.
c) For multiplication of two encrypted integers, we multiply the two ciphertexts modulo N. Let’s
multiply the encryption of 3 and 7:
Encrypt(3) = 3∗6+2∗7 mod 29 = 20
Encrypt(7) = 7∗6+2∗7 mod 29 = 49 mod 29 = 20
Multiplying the two encrypted integers:
Encrypt(3) ·Encrypt(7) = 20 ∗20 mod 29 = 400 mod 29 = 16
Therefore, the product of the encrypted integers 3 and 7 is 16.
6 Cryptographic Applications of Homomorphic Encryption
Problem: Suppose we have two ciphertexts c1and c2encrypted under the same homomorphic
encryption scheme, and we want to compute the product of the plaintexts they represent. Let the
decryption function be Dec(·).
Given that Dec(c1) = 7 and Dec(c2) = 4, and we know that the homomorphic encryption
scheme supports homomorphic multiplication, calculate the decryption of the product of the plain-
texts represented by c1and c2, i.e., find Dec(c1×c2).
Solution: Since the homomorphic encryption scheme supports homomorphic multiplication,
we can calculate the product of the plaintexts without decrypting c1and c2individually.
Let’s assume that the product of the plaintexts represented by c1and c2is denoted as m1×m2.
Since Dec(c1) = 7 and Dec(c2)=4, we have m1= 7 and m2= 4.
Now, to find Dec(c1×c2), we calculate the product of the plaintexts represented by c1and c2,
which is m1×m2= 7 ×4 = 28.
Therefore, Dec(c1×c2) = 28.
7 6. SCALABILITY PROBLEMS IN HOMOMORPHIC ENCRYPTION
Problem 6. Consider a homomorphic encryption scheme where the ciphertext size grows
linearly with the plaintext size. Suppose we have a plaintext vector p= [3,1,4,1,5] encrypted
using this scheme and a homomorphic operation that requires adding two ciphertexts together. If
the size of each ciphertext is 4 bytes, what is the total ciphertext size required for this operation?
Solution 6. a) Given that the plaintext vector p= [3,1,4,1,5] is encrypted using a homomorphic
encryption scheme with a ciphertext size of 4 bytes each, the total ciphertext size required for a
homomorphic addition operation can be calculated as follows:
b) Since the ciphertext size grows linearly with the plaintext size, the total ciphertext size re-
quired for encrypting the plaintext vector pis determined by multiplying the number of plaintext
elements by the size of each ciphertext. For a plaintext vector of length n, the total ciphertext size
is given by:
Total ciphertext size =n×Size of each ciphertext
In this case, n= 5 (as there are 5 elements in the plaintext vector) and the size of each ciphertext
is 4 bytes. Substituting these values into the formula:
Total ciphertext size = 5 ×4 = 20 bytes
Thus, the total ciphertext size required for a homomorphic addition operation on the given plain-
text vector using a 4-byte ciphertext scheme would be 20 bytes.
8 Cryptographic Applications of Homomorphic Encryption
Problem: Consider a fully homomorphic encryption scheme where the public key is (n= 5, q =
7) and the secret key is (a= 3).
a) Encrypt the plaintext message m= 4.
b) Perform a homomorphic addition on the ciphertexts corresponding to m1= 4 and m2= 3.
c) Perform a homomorphic multiplication on the ciphertext corresponding to m3= 2.
Solution:
a) To encrypt the plaintext message m= 4, we use the encryption function:
c= (a·r+ 2m) mod q
where ris a random integer. Plugging in m= 4,a= 3,q= 7, and choosing r= 2 for
demonstration purposes:
c= (3 ·2+2·4) mod 7 = (6 + 8) mod 7 = 14 mod 7 = 0
Therefore, the encrypted ciphertext for m= 4 is c= 0.
b) For homomorphic addition on two ciphertexts c1and c2corresponding to m1= 4 and m2= 3,
we can simply add the ciphertexts together modulo q:
cadd = (c1+c2) mod q
Given c1= 0 and c2= (3 ·2+2·3) mod 7 = 12 mod 7 = 5, we have:
cadd = (0 + 5) mod 7 = 5
Therefore, the resulting ciphertext after homomorphic addition is cadd = 5.
c) For homomorphic multiplication on the ciphertext corresponding to m3= 2, we perform the
multiplication modulo q:
cmul = (c·ma
3) mod q
Given c= 0 and m3= 2, we have:
cmul = (0 ·23) mod 7 = 0
Therefore, the resulting ciphertext after homomorphic multiplication is cmul = 0.
9 8. ERROR RATES IN HOMOMORPHIC ENCRYPTION
Problem 8. In a homomorphic encryption scheme, the probability of an error occurring during
the encryption process is 0.05. If a computation involves 20 homomorphic operations, what is the
probability that at least one error occurs during the computation?
Solution 8. Let’s denote the probability of an error occurring during a single homomorphic
operation as p= 0.05. The probability of no error occurring during a single operation is 1−p= 0.95.
The probability that at least one error occurs during the 20 computations can be calculated
using the complement rule (the probability of the event happening is 1 minus the probability of the
event not happening).
The probability of no error occurring during all 20 computations is (0.95)20.
Therefore, the probability of at least one error occurring is:
P(at least one error) = 1 −P(no error in 20 computations)
= 1 −(0.95)20
≈1−0.358485
≈0.641515 (approximately)
So, the probability that at least one error occurs during the computation involving 20 homomor-
phic operations is approximately 0.641515, or 64.15
10 9. KEY MANAGEMENT CHALLENGES IN HOMOMORPHIC ENCRYPTION
Problem 9. Consider a homomorphic encryption scheme where the public key is (n, e)and the
private key is (n, d), where n= 187,e= 7, and d= 23. Given a plaintext message m= 42, encrypt
the message using the public key and then decrypt the ciphertext using the private key.
Solution 9. a) To encrypt the message m= 42 using the public key (n, e), we compute the
ciphertext cusing the encryption function: c≡me(mod n).
Substitute m= 42,e= 7, and n= 187 into the encryption function:
c≡427(mod 187)
Calculating 427(mod 187):
427= 1406408618242
1406408618242 ≡29 (mod 187)
Therefore, the ciphertext cis 29.
b) To decrypt the ciphertext c= 29 using the private key (n, d), we compute the decrypted
message musing the decryption function: m≡cd(mod n).
Substitute c= 29,d= 23, and n= 187 into the decryption function:
m≡2923 (mod 187)
Calculating 2923 (mod 187):
2923 = 49298393010889
49298393010889 ≡42 (mod 187)
Therefore, the decrypted message mis 42, which matches the original plaintext message.
11 10. RELIABILITY CONCERNS IN HOMOMORPHIC ENCRYPTION
Problem 10. Consider a homomorphic encryption scheme where the key generation process
has a 5% chance of generating an incorrect key. Suppose a ciphertext is encrypted using such an
incorrect key.
a) What is the effect on the decryption process if the key is incorrect?
b) Calculate the probability that at least one out of five ciphertexts is decrypted incorrectly due
to a wrong key.
Solution 10.
a) If a ciphertext is encrypted using an incorrect key in a homomorphic encryption scheme,
the decryption process will result in an incorrect plaintext. This is because the decryption process
relies on the correctness of the key to properly recover the original plaintext from the ciphertext.
b) In this case, the probability of a key being incorrect is 5%, so the probability of a key being
correct is 95%, or 0.95. Since there are five ciphertexts, the probability of at least one being
decrypted incorrectly is equal to 1 minus the probability that all five are decrypted correctly.
Let pbe the probability that a ciphertext is decrypted correctly using the correct key. Therefore,
the probability that a ciphertext is decrypted incorrectly using the incorrect key is 1−p.
The probability that all five ciphertexts are decrypted correctly is p5, and the probability that at
least one is decrypted incorrectly is 1−p5.
Substitute p= 0.95 into the formula:
Probability of at least one incorrect decryption = 1 −(0.95)5
= 1 −0.77378
= 0.22622
Therefore, the probability that at least one out of five ciphertexts is decrypted incorrectly due to
a wrong key is approximately 0.22622 (or 22.622%).
12 11. TRUSTWORTHINESS OF HOMOMORPHIC ENCRYPTION
Problem 11. Consider a homomorphic encryption scheme where the encryption function E
and the decryption function Dare defined as follows:
E(x) = x2mod 17
D(y) = √ymod 17
Suppose we want to perform homomorphic addition and multiplication on two plaintext values.
Specifically, given the plaintext values m1= 4 and m2= 11, find the encryption of the sum m1+m2
and the encryption of the product m1×m2using the above encryption scheme. Also, decrypt the
results to obtain the plaintext values.
Solution 11.
a) To find the encryption of the sum m1+m2, we first calculate the sum modulo 17:
m1+m2= 4 + 11 = 15
Next, we calculate the encryption using the encryption function E:
E(15) = 152mod 17 = 225 mod 17 = 4
Therefore, the encryption of the sum m1+m2is 4.
b) To find the encryption of the product m1×m2, we first calculate the product modulo 17:
m1×m2= 4 ×11 = 44
Next, we calculate the encryption using the encryption function E:
E(44) = 442mod 17 = 1936 mod 17 = 16
Therefore, the encryption of the product m1×m2is 16.
c) To decrypt the results, we use the decryption function D:
For the encrypted sum 4:
D(4) = √4 mod 17 = 2
Thus, the decrypted plaintext value for the sum is 2.
For the encrypted product 16:
D(16) = √16 mod 17 = 4
Therefore, the decrypted plaintext value for the product is 4.
13 12. COMPLEXITY IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 12. Consider a homomorphic encryption scheme where the encryption function is
defined as E(m) = m2mod 13.
a) Encrypt the message m= 5.
b) Perform the homomorphic addition of two ciphertexts encrypted with the values m1= 3 and
m2= 4.
c) Decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13.
Solution 12.
a) We are given the encryption function E(m) = m2mod 13. To encrypt the message m= 5,
we substitute m= 5 into the encryption function:
E(5) = 52mod 13 = 25 mod 13 = 12.
Therefore, the encrypted ciphertext for the message m= 5 is 12.
b) To perform homomorphic addition, we calculate the sum of the ciphertexts created by en-
crypting m1= 3 and m2= 4:
E(3) = 32mod 13 = 9 mod 13 = 9
E(4) = 42mod 13 = 16 mod 13 = 3
Now, we add the ciphertexts: 9 + 3 = 12.
Therefore, the homomorphically added ciphertext is 12.
c) To decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13, we substitute c= 12 into the decryption function:
D(12) = √12 mod 13 ≈3.4641 mod 13 ≈3
Therefore, the decrypted message corresponding to the ciphertext 12 is 3.
14 13. PRIVACY RISKS OF HOMOMORPHIC ENCRYPTION
Problem 13. Consider a scenario where a company wants to use homomorphic encryption to
compute the sum of salaries of its employees without decrypting the individual salaries to ensure
privacy. The encryption scheme being used is a fully homomorphic encryption scheme that sup-
ports addition and multiplication operations. The company has encrypted the salaries using the
homomorphic encryption scheme, with each salary encoded as an integer.
The encrypted salaries are as follows: e1= 24,e2= 37,e3= 19, and e4= 42, where each eiis
the encrypted salary of employee i.
a) Compute the encrypted sum of the salaries, Enc(24 + 37 + 19 + 42).
b) The company also wants to compute the encrypted product of the salaries. Find Enc(24 ×
37 ×19 ×42).
c) If the company decrypts the sum of the encrypted salaries, will it reveal any information about
the individual salaries? Justify your answer.
Solution 13.
a) To compute the encrypted sum of the salaries, we can directly add the encrypted salaries:
Enc(24 + 37 + 19 + 42) = e1+e2+e3+e4= 24 + 37 + 19 + 42 = 122.
Therefore, the encrypted sum of the salaries is Enc(24 + 37 + 19 + 42) = 122.
b) To compute the encrypted product of the salaries, we can multiply the encrypted salaries:
Enc(24 ×37 ×19 ×42) = e1×e2×e3×e4= 24 ×37 ×19 ×42 = 387216.
Therefore, the encrypted product of the salaries is Enc(24 ×37 ×19 ×42) = 387216.
c) Homomorphic encryption provides the ability to perform computations on encrypted data
without decrypting it. When the company decrypts only the sum of the encrypted salaries, it will
not reveal any information about the individual salaries. This is because the encryption scheme
used is secure and ensures that the individual encrypted values remain confidential even after the
computation.
15 14. HOMOMORPHIC ENCRYPTION IN REAL-WORLD APPLICATIONS
Problem 14. Consider a scenario where a data processing company wants to outsource the
computation of the average salary of its employees to a cloud server using homomorphic encryp-
tion. The employees’ salaries are encrypted using a partially homomorphic encryption scheme that
supports addition and multiplication operations. Each employee’s salary is encrypted as follows:
E(s) = s2mod 11, where sis the plaintext salary.
a) If the company has four employees with salaries s1= 3,s2= 5,s3= 4, and s4= 6, calculate
the encrypted values for each of their salaries.
b) Compute the sum of the encrypted salaries.
c) Using homomorphic properties, decrypt the result to obtain the average salary of the em-
ployees.
Solution 14. a) To calculate the encrypted values for each employee’s salary:
Given E(s) = s2mod 11,
For s1= 3:E(3) = 32mod 11 = 9 mod 11 = 9
For s2= 5:E(5) = 52mod 11 = 25 mod 11 = 3
For s3= 4:E(4) = 42mod 11 = 16 mod 11 = 5
For s4= 6:E(6) = 62mod 11 = 36 mod 11 = 3
Therefore, the encrypted values for the employees’ salaries are: 9, 3, 5, 3.
b) To compute the sum of the encrypted salaries:
Sum of encrypted salaries = 9 + 3 + 5 + 3 = 20.
c) Since the encryption scheme supports multiplication and addition homomorphically, we can
decrypt the result of the sum by computing the inverse operation of squaring modulo 11, which is
finding the square root modulo 11.
20 ≡x2mod 11
Calculating the square root modulo 11:
x≡ ±√20 mod 11
x≡ ±4 mod 11
Hence, the possible decrypted values are 4 and 7. Since 4 is the correct average salary of the
employees, the decrypted average salary is 4.
16 Cryptographic Applications of Homomorphic Encryption
Problem: Using a fully homomorphic encryption scheme, Alice wants to perform the following
computation: E(m1)·E(m2) + E(m3)−E(m4), where Edenotes the encryption function and
m1= 5,m2= 3,m3= 7, and m4= 2. The encryption function transforms each message to their
encrypted form using the public key.
Assume the following encrypted values are obtained: E(m1) = 10,E(m2) = 8,E(m3) = 15,
and E(m4) = 5. Alice wishes to calculate the result of the above computation without decrypting
any values.
Solution:
Given: E(m1) = 10,E(m2)=8,E(m3) = 15, and E(m4) = 5.
a) Calculate the result of the computation E(m1)·E(m2).
b) Calculate the result of the computation E(m1)·E(m2) + E(m3).
c) Calculate the final result of the original computation.
Solution:
a) E(m1)·E(m2) = 10 ·8 = 80.
b) E(m1)·E(m2) + E(m3) = 80 + 15 = 95.
c) Finally, the original computation E(m1)·E(m2) + E(m3)−E(m4)becomes 95 −5 = 90.
Therefore, the final result of the computation without decrypting any values is 90.
17 16. USABILITY CHALLENGES OF HOMOMORPHIC ENCRYPTION
Problem 16. Consider a homomorphic encryption scheme where the encryption function is
E(x) = x2mod 13. Encrypt the message m= 3 using this scheme.
Solution 16. To encrypt the message m= 3, we substitute x= 3 into the encryption function
E(x) = x2mod 13.
Therefore, the encrypted message is:
E(3) = 32mod 13 = 9 mod 13 = 9
So, the encrypted message for m= 3 is 9.
18 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to securely outsource a computation to a cloud server using fully homo-
morphic encryption. She encrypts her input data xusing the homomorphic encryption scheme, and
sends it to the server. The server performs some computation on the encrypted data and returns
the result yto Alice. If the encryption scheme is fully homomorphic with the following properties:
- Addition: E(a) + E(b) = E(a+b)- Multiplication: E(a)×E(b) = E(a×b)
and the server computes E(3x+ 2), what will be the decrypted result that Alice receives?
Solution 1. Given that E(3x+2) = E(3)×E(x)+E(2), we expand this using the homomorphic
properties:
=E(3) ×E(x) + E(2)
=E(3) ×E(x) + E(2 ×1)
=E(3) ×E(x) + E(2) = E(3) ×E(x+ 1)
=E(3) ×E(x+x) + E(2) = E(3) ×E(2x) + E(2)
=E(3) ×E(x×2) + E(2) = E(6) ×E(x) + E(2)
=E(6) ×E(x) + E(2) = E(6x) + E(2)
Therefore, the decrypted result that Alice receives is 6x+ 2.
Problem 2. Bob wants to perform the computation 4x2−2x+ 5 on his encrypted data using
a partially homomorphic encryption scheme that supports addition but not multiplication. If he
encrypts xas E(x) = x2+3x−1, calculate the result that Bob will receive after the server performs
the computation using this homomorphic property.
Solution 2. Given that E(4x2−2x+ 5) = E(4x2) + E(−2x) + E(5), we use the homomorphic
property of addition:
=E(4) ×E(x2) + E(−2) ×E(x) + E(5)
=E(4) ×(x2+ 3x−1) + E(−2) ×x2+E(5)
=E(4x2+ 12x−4) + E(−2x2) + E(5)
=E(2x2+ 12x+ 1)
Therefore, the result that Bob will receive after the server performs the computation is 2x2+
12x+ 1.
19 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to send sensitive medical data to Bob using homomorphic encryp-
tion. She encrypts the data with a homomorphic scheme that supports addition and multiplication
operations. The plaintext data is x= 7, and the encryption function is defined as:
E(x) = x+rmod q
where ris a random number from the range [0,10] and q= 13. Calculate the encryption of xand
determine what operations Bob can perform on the encrypted data.
Solution 1. Given: x= 7,q= 13,r∈[0,10]
First, we randomly select a value of rfrom the range [0,10]. Let’s choose r= 3.
The encryption of xis then:
E(x) = x+rmod q= 7 + 3 mod 13 = 10
Therefore, the encryption of xis 10. Bob can now perform additions and multiplications on the
encrypted data without decrypting it.
20 19. HOMOMORPHIC ENCRYPTION IN FINANCIAL TRANSACTIONS
Problem 19. A bank wants to use homomorphic encryption to securely calculate the total
balance of its customers without knowing the individual balances. The bank assigns encrypted
values to represent the balances of three customers as follows: Customer A’s balance is encrypted
as 10, Customer B’s balance is encrypted as 15, and Customer C’s balance is encrypted as 8.
The bank uses the homomorphic property to perform secure calculations without decrypting the
balances.
a) If the bank wants to calculate the sum of the balances of Customer A and Customer B using
homomorphic addition, what encrypted value represents this sum?
b) If the bank wants to calculate the product of the balances of Customer A and Customer C
using homomorphic multiplication, what encrypted value represents this product?
c) Using the result from part a, if the bank also wants to subtract the balance of Customer B from
the sum of Customer A and B, what encrypted value represents this subtraction using homomorphic
subtraction?
Solution 19.
a) To calculate the sum of the balances of Customer A and Customer B using homomorphic
addition, we simply add their encrypted values:
Encrypted sum = Encrypted value of A + Encrypted value of B = 10 + 15 = 25.
Therefore, the encrypted value representing the sum of the balances of Customer A and Cus-
tomer B is 25.
b) To calculate the product of the balances of Customer A and Customer C using homomorphic
multiplication, we multiply their encrypted values:
Encrypted product = Encrypted value of A ×Encrypted value of C = 10 ×8 = 80.
Therefore, the encrypted value representing the product of the balances of Customer A and
Customer C is 80.
c) Using the result from part a, we have the encrypted value representing the sum of the bal-
ances of Customer A and B as 25. To subtract the balance of Customer B (15) from this sum using
homomorphic subtraction, we perform:
Encrypted subtraction = Encrypted sum - Encrypted value of B = 25 −15 = 10.
Therefore, the encrypted value representing the subtraction of the balance of Customer B from
the sum of Customer A and B is 10.
21 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where Alice wants to perform a homomorphic encryption
operation using the Paillier cryptosystem. She has two plaintext values m1= 7 and m2= 5, and
random parameters p= 17,q= 11,n=p·q,g=n+ 1. Assume that the public key is (n, g).
a) Encrypt both plaintext values m1and m2using the Paillier cryptosystem. b) Compute the
homomorphic sum of the ciphertexts corresponding to m1and m2. c) Decrypt the result of the
homomorphic sum to obtain the plaintext value.
Solution 1. a) To encrypt a plaintext value min the Paillier cryptosystem, we use the encryption
function E(m) = gm·rnmod n2, where ris a random number.
For m1= 7:E(7) = g7·rnmod n2= (287·r187 mod 1872)
For m2= 5:E(5) = g5·rnmod n2= (285·r187 mod 1872)
b) To compute the homomorphic sum of two ciphertexts in the Paillier cryptosystem, we multiply
the ciphertexts together. Therefore, the homomorphic sum of m1and m2would be: E(m1)×
E(m2) = (287·r187 mod 1872)×(285·r187 mod 1872)
c) To decrypt the result of the homomorphic sum, we use the decryption function D(c) = L(cλ
mod n2)·µmod n, where L(x) = x−1
n,λ=lcm(p−1, q −1), and µ=L(gλmod n2)−1mod n.
First, we compute the homomorphic sum: E(m1)×E(m2) = [step to multiply the ciphertexts]
Then, we decrypt the result as follows: D(E(m1)×E(m2)) = [steps to decrypt and obtain the
plaintext value]
22 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where a data scientist wants to securely compute the average
of a list of numbers using homomorphic encryption. The data scientist encrypts the numbers using
a homomorphic encryption scheme and performs the necessary computation. If the list of numbers
to be averaged is encrypted as follows:
- Number 1: E(5) = 15 - Number 2: E(8) = 26 - Number 3: E(3) = 13 - Number 4: E(10) = 34
Determine the encrypted result after computing the average and decrypt it to obtain the final
result.
Solution 1.
a) To compute the average homomorphically, we need to sum all the encrypted numbers and
divide the result by the total count of numbers.
The sum of the encrypted numbers:
E(5) + E(8) + E(3) + E(10) = 15 + 26 + 13 + 34 = 88
b) Now, we need to divide the encrypted sum by the total count of numbers, which is 4:
E(average) = 88
4= 22
Thus, the encrypted result after computing the average is 22.
c) To obtain the final result, we need to decrypt the encrypted average using the homomorphic
encryption scheme’s decryption function.
Decryption:
D(22) = 22
2= 11
Therefore, the final result of averaging the list of numbers is 11.
23 22. HOMOMORPHIC ENCRYPTION IN DATA ANALYTICS
Problem 22. Consider a scenario where a data scientist wants to perform statistical analysis on
encrypted data using homomorphic encryption. The data scientist has two integer values encrypted
using a homomorphic encryption scheme: a=Enc(3) and b=Enc(5).
a) Compute the encrypted value of a+b.
b) Compute the encrypted value of 2a−b.
Solution 22.
a) To compute the encrypted value of a+b, we need to use the properties of homomorphic
encryption. In a partially homomorphic encryption scheme, we can perform addition on encrypted
values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of a+bis Enc(3) + Enc(5) = Enc(3 + 5) = Enc(8).
Therefore, the encrypted value of a+bis Enc(8).
b) To compute the encrypted value of 2a−b, we again utilize the properties of homomorphic
encryption. We can perform scalar multiplication and subtraction on encrypted values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of 2a−bis 2×Enc(3) −Enc(5) = Enc(2 ×3−5) = Enc(1).
Therefore, the encrypted value of 2a−bis Enc(1).
24 23. HOMOMORPHIC ENCRYPTION IN MACHINE LEARNING
Problem 23. Consider a machine learning model that uses homomorphic encryption for privacy-
preserving computations. The model receives encrypted features X={x1, x2, x3}and encrypted
labels Y={y1, y2, y3}. After performing the necessary computations, the encrypted predictions
are Z={z1, z2, z3}. Assume the computations follow the equation: zi=w×xi+b, where wis the
weight, bis the bias, and xi,yi, and ziare encrypted values.
Given: x1= 5,y1= 7,z1= 42 (all values encrypted) x2= 3,y2= 5, and z2= 24 (all values
encrypted)
a) Calculate the weight w.
b) Calculate the bias b.
Solution 23.
a) To find the weight w, we can use the formula zi=w×xi+b.
For i= 1:
z1=w×x1+b
42 = w×5 + b
For i= 2:
z2=w×x2+b
24 = w×3 + b
Solving these two equations simultaneously, we get:
w=z1−z2
x1−x2
=42 −24
5−3=18
2= 9
Therefore, the weight w= 9.
b) To find the bias b, we can substitue w= 9 into one of the equations. Let’s use the first
equation when i= 1:
42 = 9 ×5 + b
42 = 45 + b
b= 42 −45 = −3
Therefore, the bias b=−3.
25 Cryptographic Applications of Homomorphic Encryption
Problem 1. In an e-voting system that uses homomorphic encryption, the votes for candidates
A,B, and Care encrypted as follows: a= 6,b= 8, and c= 4, respectively. The encryption scheme
uses additive homomorphic properties. The result of multiplying the ciphertexts for candidates A
and Bis calculated as a×b= 30. Find out the encrypted vote for candidate C.
Solution 1. Given that the encryption scheme is additive homomorphic, we can calculate the
encrypted vote for candidate Cusing the properties of homomorphic encryption.
We know that a×brepresents the product of ciphertexts for candidates Aand B. Thus, a×b=
30.
Now, to find the encrypted vote for candidate C, we can utilize the additive homomorphic prop-
erty, which states that multiplying ciphertexts corresponds to adding plaintexts. Therefore, the
encrypted vote for candidate Cwill be:
a×b+c= 30 + c
Given a= 6,b= 8, and c= 4, substituting these values:
30 + 4 = 34
Therefore, the encrypted vote for candidate Cis 34.
26 25. HOMOMORPHIC ENCRYPTION IN SECURE COMMUNICATION PROTOCOLS
Problem 25. Alice wants to perform a secure computation on encrypted data using a homo-
morphic encryption scheme. She has two encrypted values c1and c2, where c1=Encpk(7) and
c2=Encpk(5), encrypted under a public key pk. She wants to calculate the sum and product of
the decrypted values without revealing the encryption key. Assume the homomorphic encryption
scheme supports both addition and multiplication operations homomorphically.
Solution 25. a) To calculate the sum of the decrypted values, Alice can perform homomorphic
addition on the encrypted values c1and c2. Let csum =c1⊕c2.
The decryption of csum will give the sum of the decrypted values:
Decsk(csum) = Decsk(c1⊕c2)
=Decsk(Encpk(7) ⊕Encpk (5))
=Decsk(Encpk(7 + 5))
=Decsk(Encpk(12))
= 12
Therefore, the sum of the decrypted values is 12.
b) To calculate the product of the decrypted values, Alice can perform homomorphic multipli-
cation on the encrypted values c1and c2. Let cprod =c1⊗c2.
The decryption of cprod will give the product of the decrypted values:
Decsk(cprod) = Decsk(c1⊗c2)
=Decsk(Encpk(7) ⊗Encpk (5))
=Decsk(Encpk(7 ×5))
=Decsk(Encpk(35))
= 35
Therefore, the product of the decrypted values is 35.
3 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to perform a homomorphic encryption on a message m= 7 using a fully
homomorphic encryption scheme. The public key for this scheme is n= 13 and the encryption
function is defined as E(x) = x2mod n. Calculate the encrypted message.
Solution 1. To encrypt the message using the homomorphic encryption scheme, we need to
compute E(m):
E(m) = E(7) = 72mod 13 = 49 mod 13 = 10
Therefore, the encrypted message is 10.
4 Cryptographic Applications of Homomorphic Encryption
Problem 2. Bob wants to perform a homomorphic addition on two encrypted messages. The
encrypted messages are c1= 8 and c2= 12, and the public key for the homomorphic encryption
scheme is n= 17. If the encryption function is defined as E(x) = x2mod n, calculate the result
of adding the two encrypted messages together.
Solution 2. To perform homomorphic addition on the encrypted messages, we first need to
decrypt the messages, add them together, and then re-encrypt the sum:
Step 1: Decrypt the messages
C1=c
n+1
4
1mod n= 85mod 17 = 8
C2=c
n+1
4
2mod n= 125mod 17 = 12
Step 2: Add the decrypted messages
D=C1+C2= 8 + 12 = 20
Step 3: Re-encrypt the sum
E(D) = D2mod 17 = 202mod 17 = 400 mod 17 = 11
Therefore, the result of adding the two encrypted messages together is 11.
5 4. LIMITATIONS OF HOMOMORPHIC ENCRYPTION
Problem 4. Consider a fully homomorphic encryption scheme where the ciphertext space is
integers modulo N= 29. Alice wants to perform the following computations:
a) Encrypt the integer 9 using the encryption function.
b) Add two encrypted integers, the encryption of 5 and 12.
c) Multiply an encrypted integer, the encryption of 3, by an encrypted integer, the encryption of
7.
Solution 4.
a) To encrypt the integer 9, we first need to choose a public key (N, q, h)for the encryption
scheme. Let q= 31 and h= 6. Then the encryption function is defined as follows:
Encrypt(m) = mh + 2rmod N
where m= 9, and ris a random integer modulo N. Let’s choose r= 7. Thus, the encryption
of 9 is:
Encrypt(9) = 9∗6+2∗7 mod 29 = 54 + 14 mod 29 = 68 mod 29 = 10
Therefore, the encryption of 9 is 10.
b) To add two encrypted integers, we simply add them modulo N. Let’s consider the encryption
of 5 and 12:
Encrypt(5) = 5∗6+2∗7 mod 29 = 32 mod 29 = 3
Encrypt(12) = 12 ∗6+2∗7 mod 29 = 74 mod 29 = 16
Adding the two encrypted integers:
Encrypt(5) +Encrypt(12) = 3 + 16 mod 29 = 19
Therefore, the sum of the encrypted integers 5 and 12 is 19.
c) For multiplication of two encrypted integers, we multiply the two ciphertexts modulo N. Let’s
multiply the encryption of 3 and 7:
Encrypt(3) = 3∗6+2∗7 mod 29 = 20
Encrypt(7) = 7∗6+2∗7 mod 29 = 49 mod 29 = 20
Multiplying the two encrypted integers:
Encrypt(3) ·Encrypt(7) = 20 ∗20 mod 29 = 400 mod 29 = 16
Therefore, the product of the encrypted integers 3 and 7 is 16.
6 Cryptographic Applications of Homomorphic Encryption
Problem: Suppose we have two ciphertexts c1and c2encrypted under the same homomorphic
encryption scheme, and we want to compute the product of the plaintexts they represent. Let the
decryption function be Dec(·).
Given that Dec(c1) = 7 and Dec(c2) = 4, and we know that the homomorphic encryption
scheme supports homomorphic multiplication, calculate the decryption of the product of the plain-
texts represented by c1and c2, i.e., find Dec(c1×c2).
Solution: Since the homomorphic encryption scheme supports homomorphic multiplication,
we can calculate the product of the plaintexts without decrypting c1and c2individually.
Let’s assume that the product of the plaintexts represented by c1and c2is denoted as m1×m2.
Since Dec(c1) = 7 and Dec(c2)=4, we have m1= 7 and m2= 4.
Now, to find Dec(c1×c2), we calculate the product of the plaintexts represented by c1and c2,
which is m1×m2= 7 ×4 = 28.
Therefore, Dec(c1×c2) = 28.
7 6. SCALABILITY PROBLEMS IN HOMOMORPHIC ENCRYPTION
Problem 6. Consider a homomorphic encryption scheme where the ciphertext size grows
linearly with the plaintext size. Suppose we have a plaintext vector p= [3,1,4,1,5] encrypted
using this scheme and a homomorphic operation that requires adding two ciphertexts together. If
the size of each ciphertext is 4 bytes, what is the total ciphertext size required for this operation?
Solution 6. a) Given that the plaintext vector p= [3,1,4,1,5] is encrypted using a homomorphic
encryption scheme with a ciphertext size of 4 bytes each, the total ciphertext size required for a
homomorphic addition operation can be calculated as follows:
b) Since the ciphertext size grows linearly with the plaintext size, the total ciphertext size re-
quired for encrypting the plaintext vector pis determined by multiplying the number of plaintext
elements by the size of each ciphertext. For a plaintext vector of length n, the total ciphertext size
is given by:
Total ciphertext size =n×Size of each ciphertext
In this case, n= 5 (as there are 5 elements in the plaintext vector) and the size of each ciphertext
is 4 bytes. Substituting these values into the formula:
Total ciphertext size = 5 ×4 = 20 bytes
Thus, the total ciphertext size required for a homomorphic addition operation on the given plain-
text vector using a 4-byte ciphertext scheme would be 20 bytes.
8 Cryptographic Applications of Homomorphic Encryption
Problem: Consider a fully homomorphic encryption scheme where the public key is (n= 5, q =
7) and the secret key is (a= 3).
a) Encrypt the plaintext message m= 4.
b) Perform a homomorphic addition on the ciphertexts corresponding to m1= 4 and m2= 3.
c) Perform a homomorphic multiplication on the ciphertext corresponding to m3= 2.
Solution:
a) To encrypt the plaintext message m= 4, we use the encryption function:
c= (a·r+ 2m) mod q
where ris a random integer. Plugging in m= 4,a= 3,q= 7, and choosing r= 2 for
demonstration purposes:
c= (3 ·2+2·4) mod 7 = (6 + 8) mod 7 = 14 mod 7 = 0
Therefore, the encrypted ciphertext for m= 4 is c= 0.
b) For homomorphic addition on two ciphertexts c1and c2corresponding to m1= 4 and m2= 3,
we can simply add the ciphertexts together modulo q:
cadd = (c1+c2) mod q
Given c1= 0 and c2= (3 ·2+2·3) mod 7 = 12 mod 7 = 5, we have:
cadd = (0 + 5) mod 7 = 5
Therefore, the resulting ciphertext after homomorphic addition is cadd = 5.
c) For homomorphic multiplication on the ciphertext corresponding to m3= 2, we perform the
multiplication modulo q:
cmul = (c·ma
3) mod q
Given c= 0 and m3= 2, we have:
cmul = (0 ·23) mod 7 = 0
Therefore, the resulting ciphertext after homomorphic multiplication is cmul = 0.
9 8. ERROR RATES IN HOMOMORPHIC ENCRYPTION
Problem 8. In a homomorphic encryption scheme, the probability of an error occurring during
the encryption process is 0.05. If a computation involves 20 homomorphic operations, what is the
probability that at least one error occurs during the computation?
Solution 8. Let’s denote the probability of an error occurring during a single homomorphic
operation as p= 0.05. The probability of no error occurring during a single operation is 1−p= 0.95.
The probability that at least one error occurs during the 20 computations can be calculated
using the complement rule (the probability of the event happening is 1 minus the probability of the
event not happening).
The probability of no error occurring during all 20 computations is (0.95)20.
Therefore, the probability of at least one error occurring is:
P(at least one error) = 1 −P(no error in 20 computations)
= 1 −(0.95)20
≈1−0.358485
≈0.641515 (approximately)
So, the probability that at least one error occurs during the computation involving 20 homomor-
phic operations is approximately 0.641515, or 64.15
10 9. KEY MANAGEMENT CHALLENGES IN HOMOMORPHIC ENCRYPTION
Problem 9. Consider a homomorphic encryption scheme where the public key is (n, e)and the
private key is (n, d), where n= 187,e= 7, and d= 23. Given a plaintext message m= 42, encrypt
the message using the public key and then decrypt the ciphertext using the private key.
Solution 9. a) To encrypt the message m= 42 using the public key (n, e), we compute the
ciphertext cusing the encryption function: c≡me(mod n).
Substitute m= 42,e= 7, and n= 187 into the encryption function:
c≡427(mod 187)
Calculating 427(mod 187):
427= 1406408618242
1406408618242 ≡29 (mod 187)
Therefore, the ciphertext cis 29.
b) To decrypt the ciphertext c= 29 using the private key (n, d), we compute the decrypted
message musing the decryption function: m≡cd(mod n).
Substitute c= 29,d= 23, and n= 187 into the decryption function:
m≡2923 (mod 187)
Calculating 2923 (mod 187):
2923 = 49298393010889
49298393010889 ≡42 (mod 187)
Therefore, the decrypted message mis 42, which matches the original plaintext message.
11 10. RELIABILITY CONCERNS IN HOMOMORPHIC ENCRYPTION
Problem 10. Consider a homomorphic encryption scheme where the key generation process
has a 5% chance of generating an incorrect key. Suppose a ciphertext is encrypted using such an
incorrect key.
a) What is the effect on the decryption process if the key is incorrect?
b) Calculate the probability that at least one out of five ciphertexts is decrypted incorrectly due
to a wrong key.
Solution 10.
a) If a ciphertext is encrypted using an incorrect key in a homomorphic encryption scheme,
the decryption process will result in an incorrect plaintext. This is because the decryption process
relies on the correctness of the key to properly recover the original plaintext from the ciphertext.
b) In this case, the probability of a key being incorrect is 5%, so the probability of a key being
correct is 95%, or 0.95. Since there are five ciphertexts, the probability of at least one being
decrypted incorrectly is equal to 1 minus the probability that all five are decrypted correctly.
Let pbe the probability that a ciphertext is decrypted correctly using the correct key. Therefore,
the probability that a ciphertext is decrypted incorrectly using the incorrect key is 1−p.
The probability that all five ciphertexts are decrypted correctly is p5, and the probability that at
least one is decrypted incorrectly is 1−p5.
Substitute p= 0.95 into the formula:
Probability of at least one incorrect decryption = 1 −(0.95)5
= 1 −0.77378
= 0.22622
Therefore, the probability that at least one out of five ciphertexts is decrypted incorrectly due to
a wrong key is approximately 0.22622 (or 22.622%).
12 11. TRUSTWORTHINESS OF HOMOMORPHIC ENCRYPTION
Problem 11. Consider a homomorphic encryption scheme where the encryption function E
and the decryption function Dare defined as follows:
E(x) = x2mod 17
D(y) = √ymod 17
Suppose we want to perform homomorphic addition and multiplication on two plaintext values.
Specifically, given the plaintext values m1= 4 and m2= 11, find the encryption of the sum m1+m2
and the encryption of the product m1×m2using the above encryption scheme. Also, decrypt the
results to obtain the plaintext values.
Solution 11.
a) To find the encryption of the sum m1+m2, we first calculate the sum modulo 17:
m1+m2= 4 + 11 = 15
Next, we calculate the encryption using the encryption function E:
E(15) = 152mod 17 = 225 mod 17 = 4
Therefore, the encryption of the sum m1+m2is 4.
b) To find the encryption of the product m1×m2, we first calculate the product modulo 17:
m1×m2= 4 ×11 = 44
Next, we calculate the encryption using the encryption function E:
E(44) = 442mod 17 = 1936 mod 17 = 16
Therefore, the encryption of the product m1×m2is 16.
c) To decrypt the results, we use the decryption function D:
For the encrypted sum 4:
D(4) = √4 mod 17 = 2
Thus, the decrypted plaintext value for the sum is 2.
For the encrypted product 16:
D(16) = √16 mod 17 = 4
Therefore, the decrypted plaintext value for the product is 4.
13 12. COMPLEXITY IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 12. Consider a homomorphic encryption scheme where the encryption function is
defined as E(m) = m2mod 13.
a) Encrypt the message m= 5.
b) Perform the homomorphic addition of two ciphertexts encrypted with the values m1= 3 and
m2= 4.
c) Decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13.
Solution 12.
a) We are given the encryption function E(m) = m2mod 13. To encrypt the message m= 5,
we substitute m= 5 into the encryption function:
E(5) = 52mod 13 = 25 mod 13 = 12.
Therefore, the encrypted ciphertext for the message m= 5 is 12.
b) To perform homomorphic addition, we calculate the sum of the ciphertexts created by en-
crypting m1= 3 and m2= 4:
E(3) = 32mod 13 = 9 mod 13 = 9
E(4) = 42mod 13 = 16 mod 13 = 3
Now, we add the ciphertexts: 9 + 3 = 12.
Therefore, the homomorphically added ciphertext is 12.
c) To decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13, we substitute c= 12 into the decryption function:
D(12) = √12 mod 13 ≈3.4641 mod 13 ≈3
Therefore, the decrypted message corresponding to the ciphertext 12 is 3.
14 13. PRIVACY RISKS OF HOMOMORPHIC ENCRYPTION
Problem 13. Consider a scenario where a company wants to use homomorphic encryption to
compute the sum of salaries of its employees without decrypting the individual salaries to ensure
privacy. The encryption scheme being used is a fully homomorphic encryption scheme that sup-
ports addition and multiplication operations. The company has encrypted the salaries using the
homomorphic encryption scheme, with each salary encoded as an integer.
The encrypted salaries are as follows: e1= 24,e2= 37,e3= 19, and e4= 42, where each eiis
the encrypted salary of employee i.
a) Compute the encrypted sum of the salaries, Enc(24 + 37 + 19 + 42).
b) The company also wants to compute the encrypted product of the salaries. Find Enc(24 ×
37 ×19 ×42).
c) If the company decrypts the sum of the encrypted salaries, will it reveal any information about
the individual salaries? Justify your answer.
Solution 13.
a) To compute the encrypted sum of the salaries, we can directly add the encrypted salaries:
Enc(24 + 37 + 19 + 42) = e1+e2+e3+e4= 24 + 37 + 19 + 42 = 122.
Therefore, the encrypted sum of the salaries is Enc(24 + 37 + 19 + 42) = 122.
b) To compute the encrypted product of the salaries, we can multiply the encrypted salaries:
Enc(24 ×37 ×19 ×42) = e1×e2×e3×e4= 24 ×37 ×19 ×42 = 387216.
Therefore, the encrypted product of the salaries is Enc(24 ×37 ×19 ×42) = 387216.
c) Homomorphic encryption provides the ability to perform computations on encrypted data
without decrypting it. When the company decrypts only the sum of the encrypted salaries, it will
not reveal any information about the individual salaries. This is because the encryption scheme
used is secure and ensures that the individual encrypted values remain confidential even after the
computation.
15 14. HOMOMORPHIC ENCRYPTION IN REAL-WORLD APPLICATIONS
Problem 14. Consider a scenario where a data processing company wants to outsource the
computation of the average salary of its employees to a cloud server using homomorphic encryp-
tion. The employees’ salaries are encrypted using a partially homomorphic encryption scheme that
supports addition and multiplication operations. Each employee’s salary is encrypted as follows:
E(s) = s2mod 11, where sis the plaintext salary.
a) If the company has four employees with salaries s1= 3,s2= 5,s3= 4, and s4= 6, calculate
the encrypted values for each of their salaries.
b) Compute the sum of the encrypted salaries.
c) Using homomorphic properties, decrypt the result to obtain the average salary of the em-
ployees.
Solution 14. a) To calculate the encrypted values for each employee’s salary:
Given E(s) = s2mod 11,
For s1= 3:E(3) = 32mod 11 = 9 mod 11 = 9
For s2= 5:E(5) = 52mod 11 = 25 mod 11 = 3
For s3= 4:E(4) = 42mod 11 = 16 mod 11 = 5
For s4= 6:E(6) = 62mod 11 = 36 mod 11 = 3
Therefore, the encrypted values for the employees’ salaries are: 9, 3, 5, 3.
b) To compute the sum of the encrypted salaries:
Sum of encrypted salaries = 9 + 3 + 5 + 3 = 20.
c) Since the encryption scheme supports multiplication and addition homomorphically, we can
decrypt the result of the sum by computing the inverse operation of squaring modulo 11, which is
finding the square root modulo 11.
20 ≡x2mod 11
Calculating the square root modulo 11:
x≡ ±√20 mod 11
x≡ ±4 mod 11
Hence, the possible decrypted values are 4 and 7. Since 4 is the correct average salary of the
employees, the decrypted average salary is 4.
16 Cryptographic Applications of Homomorphic Encryption
Problem: Using a fully homomorphic encryption scheme, Alice wants to perform the following
computation: E(m1)·E(m2) + E(m3)−E(m4), where Edenotes the encryption function and
m1= 5,m2= 3,m3= 7, and m4= 2. The encryption function transforms each message to their
encrypted form using the public key.
Assume the following encrypted values are obtained: E(m1) = 10,E(m2) = 8,E(m3) = 15,
and E(m4) = 5. Alice wishes to calculate the result of the above computation without decrypting
any values.
Solution:
Given: E(m1) = 10,E(m2)=8,E(m3) = 15, and E(m4) = 5.
a) Calculate the result of the computation E(m1)·E(m2).
b) Calculate the result of the computation E(m1)·E(m2) + E(m3).
c) Calculate the final result of the original computation.
Solution:
a) E(m1)·E(m2) = 10 ·8 = 80.
b) E(m1)·E(m2) + E(m3) = 80 + 15 = 95.
c) Finally, the original computation E(m1)·E(m2) + E(m3)−E(m4)becomes 95 −5 = 90.
Therefore, the final result of the computation without decrypting any values is 90.
17 16. USABILITY CHALLENGES OF HOMOMORPHIC ENCRYPTION
Problem 16. Consider a homomorphic encryption scheme where the encryption function is
E(x) = x2mod 13. Encrypt the message m= 3 using this scheme.
Solution 16. To encrypt the message m= 3, we substitute x= 3 into the encryption function
E(x) = x2mod 13.
Therefore, the encrypted message is:
E(3) = 32mod 13 = 9 mod 13 = 9
So, the encrypted message for m= 3 is 9.
18 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to securely outsource a computation to a cloud server using fully homo-
morphic encryption. She encrypts her input data xusing the homomorphic encryption scheme, and
sends it to the server. The server performs some computation on the encrypted data and returns
the result yto Alice. If the encryption scheme is fully homomorphic with the following properties:
- Addition: E(a) + E(b) = E(a+b)- Multiplication: E(a)×E(b) = E(a×b)
and the server computes E(3x+ 2), what will be the decrypted result that Alice receives?
Solution 1. Given that E(3x+2) = E(3)×E(x)+E(2), we expand this using the homomorphic
properties:
=E(3) ×E(x) + E(2)
=E(3) ×E(x) + E(2 ×1)
=E(3) ×E(x) + E(2) = E(3) ×E(x+ 1)
=E(3) ×E(x+x) + E(2) = E(3) ×E(2x) + E(2)
=E(3) ×E(x×2) + E(2) = E(6) ×E(x) + E(2)
=E(6) ×E(x) + E(2) = E(6x) + E(2)
Therefore, the decrypted result that Alice receives is 6x+ 2.
Problem 2. Bob wants to perform the computation 4x2−2x+ 5 on his encrypted data using
a partially homomorphic encryption scheme that supports addition but not multiplication. If he
encrypts xas E(x) = x2+3x−1, calculate the result that Bob will receive after the server performs
the computation using this homomorphic property.
Solution 2. Given that E(4x2−2x+ 5) = E(4x2) + E(−2x) + E(5), we use the homomorphic
property of addition:
=E(4) ×E(x2) + E(−2) ×E(x) + E(5)
=E(4) ×(x2+ 3x−1) + E(−2) ×x2+E(5)
=E(4x2+ 12x−4) + E(−2x2) + E(5)
=E(2x2+ 12x+ 1)
Therefore, the result that Bob will receive after the server performs the computation is 2x2+
12x+ 1.
19 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to send sensitive medical data to Bob using homomorphic encryp-
tion. She encrypts the data with a homomorphic scheme that supports addition and multiplication
operations. The plaintext data is x= 7, and the encryption function is defined as:
E(x) = x+rmod q
where ris a random number from the range [0,10] and q= 13. Calculate the encryption of xand
determine what operations Bob can perform on the encrypted data.
Solution 1. Given: x= 7,q= 13,r∈[0,10]
First, we randomly select a value of rfrom the range [0,10]. Let’s choose r= 3.
The encryption of xis then:
E(x) = x+rmod q= 7 + 3 mod 13 = 10
Therefore, the encryption of xis 10. Bob can now perform additions and multiplications on the
encrypted data without decrypting it.
20 19. HOMOMORPHIC ENCRYPTION IN FINANCIAL TRANSACTIONS
Problem 19. A bank wants to use homomorphic encryption to securely calculate the total
balance of its customers without knowing the individual balances. The bank assigns encrypted
values to represent the balances of three customers as follows: Customer A’s balance is encrypted
as 10, Customer B’s balance is encrypted as 15, and Customer C’s balance is encrypted as 8.
The bank uses the homomorphic property to perform secure calculations without decrypting the
balances.
a) If the bank wants to calculate the sum of the balances of Customer A and Customer B using
homomorphic addition, what encrypted value represents this sum?
b) If the bank wants to calculate the product of the balances of Customer A and Customer C
using homomorphic multiplication, what encrypted value represents this product?
c) Using the result from part a, if the bank also wants to subtract the balance of Customer B from
the sum of Customer A and B, what encrypted value represents this subtraction using homomorphic
subtraction?
Solution 19.
a) To calculate the sum of the balances of Customer A and Customer B using homomorphic
addition, we simply add their encrypted values:
Encrypted sum = Encrypted value of A + Encrypted value of B = 10 + 15 = 25.
Therefore, the encrypted value representing the sum of the balances of Customer A and Cus-
tomer B is 25.
b) To calculate the product of the balances of Customer A and Customer C using homomorphic
multiplication, we multiply their encrypted values:
Encrypted product = Encrypted value of A ×Encrypted value of C = 10 ×8 = 80.
Therefore, the encrypted value representing the product of the balances of Customer A and
Customer C is 80.
c) Using the result from part a, we have the encrypted value representing the sum of the bal-
ances of Customer A and B as 25. To subtract the balance of Customer B (15) from this sum using
homomorphic subtraction, we perform:
Encrypted subtraction = Encrypted sum - Encrypted value of B = 25 −15 = 10.
Therefore, the encrypted value representing the subtraction of the balance of Customer B from
the sum of Customer A and B is 10.
21 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where Alice wants to perform a homomorphic encryption
operation using the Paillier cryptosystem. She has two plaintext values m1= 7 and m2= 5, and
random parameters p= 17,q= 11,n=p·q,g=n+ 1. Assume that the public key is (n, g).
a) Encrypt both plaintext values m1and m2using the Paillier cryptosystem. b) Compute the
homomorphic sum of the ciphertexts corresponding to m1and m2. c) Decrypt the result of the
homomorphic sum to obtain the plaintext value.
Solution 1. a) To encrypt a plaintext value min the Paillier cryptosystem, we use the encryption
function E(m) = gm·rnmod n2, where ris a random number.
For m1= 7:E(7) = g7·rnmod n2= (287·r187 mod 1872)
For m2= 5:E(5) = g5·rnmod n2= (285·r187 mod 1872)
b) To compute the homomorphic sum of two ciphertexts in the Paillier cryptosystem, we multiply
the ciphertexts together. Therefore, the homomorphic sum of m1and m2would be: E(m1)×
E(m2) = (287·r187 mod 1872)×(285·r187 mod 1872)
c) To decrypt the result of the homomorphic sum, we use the decryption function D(c) = L(cλ
mod n2)·µmod n, where L(x) = x−1
n,λ=lcm(p−1, q −1), and µ=L(gλmod n2)−1mod n.
First, we compute the homomorphic sum: E(m1)×E(m2) = [step to multiply the ciphertexts]
Then, we decrypt the result as follows: D(E(m1)×E(m2)) = [steps to decrypt and obtain the
plaintext value]
22 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where a data scientist wants to securely compute the average
of a list of numbers using homomorphic encryption. The data scientist encrypts the numbers using
a homomorphic encryption scheme and performs the necessary computation. If the list of numbers
to be averaged is encrypted as follows:
- Number 1: E(5) = 15 - Number 2: E(8) = 26 - Number 3: E(3) = 13 - Number 4: E(10) = 34
Determine the encrypted result after computing the average and decrypt it to obtain the final
result.
Solution 1.
a) To compute the average homomorphically, we need to sum all the encrypted numbers and
divide the result by the total count of numbers.
The sum of the encrypted numbers:
E(5) + E(8) + E(3) + E(10) = 15 + 26 + 13 + 34 = 88
b) Now, we need to divide the encrypted sum by the total count of numbers, which is 4:
E(average) = 88
4= 22
Thus, the encrypted result after computing the average is 22.
c) To obtain the final result, we need to decrypt the encrypted average using the homomorphic
encryption scheme’s decryption function.
Decryption:
D(22) = 22
2= 11
Therefore, the final result of averaging the list of numbers is 11.
23 22. HOMOMORPHIC ENCRYPTION IN DATA ANALYTICS
Problem 22. Consider a scenario where a data scientist wants to perform statistical analysis on
encrypted data using homomorphic encryption. The data scientist has two integer values encrypted
using a homomorphic encryption scheme: a=Enc(3) and b=Enc(5).
a) Compute the encrypted value of a+b.
b) Compute the encrypted value of 2a−b.
Solution 22.
a) To compute the encrypted value of a+b, we need to use the properties of homomorphic
encryption. In a partially homomorphic encryption scheme, we can perform addition on encrypted
values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of a+bis Enc(3) + Enc(5) = Enc(3 + 5) = Enc(8).
Therefore, the encrypted value of a+bis Enc(8).
b) To compute the encrypted value of 2a−b, we again utilize the properties of homomorphic
encryption. We can perform scalar multiplication and subtraction on encrypted values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of 2a−bis 2×Enc(3) −Enc(5) = Enc(2 ×3−5) = Enc(1).
Therefore, the encrypted value of 2a−bis Enc(1).
24 23. HOMOMORPHIC ENCRYPTION IN MACHINE LEARNING
Problem 23. Consider a machine learning model that uses homomorphic encryption for privacy-
preserving computations. The model receives encrypted features X={x1, x2, x3}and encrypted
labels Y={y1, y2, y3}. After performing the necessary computations, the encrypted predictions
are Z={z1, z2, z3}. Assume the computations follow the equation: zi=w×xi+b, where wis the
weight, bis the bias, and xi,yi, and ziare encrypted values.
Given: x1= 5,y1= 7,z1= 42 (all values encrypted) x2= 3,y2= 5, and z2= 24 (all values
encrypted)
a) Calculate the weight w.
b) Calculate the bias b.
Solution 23.
a) To find the weight w, we can use the formula zi=w×xi+b.
For i= 1:
z1=w×x1+b
42 = w×5 + b
For i= 2:
z2=w×x2+b
24 = w×3 + b
Solving these two equations simultaneously, we get:
w=z1−z2
x1−x2
=42 −24
5−3=18
2= 9
Therefore, the weight w= 9.
b) To find the bias b, we can substitue w= 9 into one of the equations. Let’s use the first
equation when i= 1:
42 = 9 ×5 + b
42 = 45 + b
b= 42 −45 = −3
Therefore, the bias b=−3.
25 Cryptographic Applications of Homomorphic Encryption
Problem 1. In an e-voting system that uses homomorphic encryption, the votes for candidates
A,B, and Care encrypted as follows: a= 6,b= 8, and c= 4, respectively. The encryption scheme
uses additive homomorphic properties. The result of multiplying the ciphertexts for candidates A
and Bis calculated as a×b= 30. Find out the encrypted vote for candidate C.
Solution 1. Given that the encryption scheme is additive homomorphic, we can calculate the
encrypted vote for candidate Cusing the properties of homomorphic encryption.
We know that a×brepresents the product of ciphertexts for candidates Aand B. Thus, a×b=
30.
Now, to find the encrypted vote for candidate C, we can utilize the additive homomorphic prop-
erty, which states that multiplying ciphertexts corresponds to adding plaintexts. Therefore, the
encrypted vote for candidate Cwill be:
a×b+c= 30 + c
Given a= 6,b= 8, and c= 4, substituting these values:
30 + 4 = 34
Therefore, the encrypted vote for candidate Cis 34.
26 25. HOMOMORPHIC ENCRYPTION IN SECURE COMMUNICATION PROTOCOLS
Problem 25. Alice wants to perform a secure computation on encrypted data using a homo-
morphic encryption scheme. She has two encrypted values c1and c2, where c1=Encpk(7) and
c2=Encpk(5), encrypted under a public key pk. She wants to calculate the sum and product of
the decrypted values without revealing the encryption key. Assume the homomorphic encryption
scheme supports both addition and multiplication operations homomorphically.
Solution 25. a) To calculate the sum of the decrypted values, Alice can perform homomorphic
addition on the encrypted values c1and c2. Let csum =c1⊕c2.
The decryption of csum will give the sum of the decrypted values:
Decsk(csum) = Decsk(c1⊕c2)
=Decsk(Encpk(7) ⊕Encpk (5))
=Decsk(Encpk(7 + 5))
=Decsk(Encpk(12))
= 12
Therefore, the sum of the decrypted values is 12.
b) To calculate the product of the decrypted values, Alice can perform homomorphic multipli-
cation on the encrypted values c1and c2. Let cprod =c1⊗c2.
The decryption of cprod will give the product of the decrypted values:
Decsk(cprod) = Decsk(c1⊗c2)
=Decsk(Encpk(7) ⊗Encpk (5))
=Decsk(Encpk(7 ×5))
=Decsk(Encpk(35))
= 35
Therefore, the product of the decrypted values is 35.
3 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to perform a homomorphic encryption on a message m= 7 using a fully
homomorphic encryption scheme. The public key for this scheme is n= 13 and the encryption
function is defined as E(x) = x2mod n. Calculate the encrypted message.
Solution 1. To encrypt the message using the homomorphic encryption scheme, we need to
compute E(m):
E(m) = E(7) = 72mod 13 = 49 mod 13 = 10
Therefore, the encrypted message is 10.
4 Cryptographic Applications of Homomorphic Encryption
Problem 2. Bob wants to perform a homomorphic addition on two encrypted messages. The
encrypted messages are c1= 8 and c2= 12, and the public key for the homomorphic encryption
scheme is n= 17. If the encryption function is defined as E(x) = x2mod n, calculate the result
of adding the two encrypted messages together.
Solution 2. To perform homomorphic addition on the encrypted messages, we first need to
decrypt the messages, add them together, and then re-encrypt the sum:
Step 1: Decrypt the messages
C1=c
n+1
4
1mod n= 85mod 17 = 8
C2=c
n+1
4
2mod n= 125mod 17 = 12
Step 2: Add the decrypted messages
D=C1+C2= 8 + 12 = 20
Step 3: Re-encrypt the sum
E(D) = D2mod 17 = 202mod 17 = 400 mod 17 = 11
Therefore, the result of adding the two encrypted messages together is 11.
5 4. LIMITATIONS OF HOMOMORPHIC ENCRYPTION
Problem 4. Consider a fully homomorphic encryption scheme where the ciphertext space is
integers modulo N= 29. Alice wants to perform the following computations:
a) Encrypt the integer 9 using the encryption function.
b) Add two encrypted integers, the encryption of 5 and 12.
c) Multiply an encrypted integer, the encryption of 3, by an encrypted integer, the encryption of
7.
Solution 4.
a) To encrypt the integer 9, we first need to choose a public key (N, q, h)for the encryption
scheme. Let q= 31 and h= 6. Then the encryption function is defined as follows:
Encrypt(m) = mh + 2rmod N
where m= 9, and ris a random integer modulo N. Let’s choose r= 7. Thus, the encryption
of 9 is:
Encrypt(9) = 9∗6+2∗7 mod 29 = 54 + 14 mod 29 = 68 mod 29 = 10
Therefore, the encryption of 9 is 10.
b) To add two encrypted integers, we simply add them modulo N. Let’s consider the encryption
of 5 and 12:
Encrypt(5) = 5∗6+2∗7 mod 29 = 32 mod 29 = 3
Encrypt(12) = 12 ∗6+2∗7 mod 29 = 74 mod 29 = 16
Adding the two encrypted integers:
Encrypt(5) +Encrypt(12) = 3 + 16 mod 29 = 19
Therefore, the sum of the encrypted integers 5 and 12 is 19.
c) For multiplication of two encrypted integers, we multiply the two ciphertexts modulo N. Let’s
multiply the encryption of 3 and 7:
Encrypt(3) = 3∗6+2∗7 mod 29 = 20
Encrypt(7) = 7∗6+2∗7 mod 29 = 49 mod 29 = 20
Multiplying the two encrypted integers:
Encrypt(3) ·Encrypt(7) = 20 ∗20 mod 29 = 400 mod 29 = 16
Therefore, the product of the encrypted integers 3 and 7 is 16.
6 Cryptographic Applications of Homomorphic Encryption
Problem: Suppose we have two ciphertexts c1and c2encrypted under the same homomorphic
encryption scheme, and we want to compute the product of the plaintexts they represent. Let the
decryption function be Dec(·).
Given that Dec(c1) = 7 and Dec(c2) = 4, and we know that the homomorphic encryption
scheme supports homomorphic multiplication, calculate the decryption of the product of the plain-
texts represented by c1and c2, i.e., find Dec(c1×c2).
Solution: Since the homomorphic encryption scheme supports homomorphic multiplication,
we can calculate the product of the plaintexts without decrypting c1and c2individually.
Let’s assume that the product of the plaintexts represented by c1and c2is denoted as m1×m2.
Since Dec(c1) = 7 and Dec(c2)=4, we have m1= 7 and m2= 4.
Now, to find Dec(c1×c2), we calculate the product of the plaintexts represented by c1and c2,
which is m1×m2= 7 ×4 = 28.
Therefore, Dec(c1×c2) = 28.
7 6. SCALABILITY PROBLEMS IN HOMOMORPHIC ENCRYPTION
Problem 6. Consider a homomorphic encryption scheme where the ciphertext size grows
linearly with the plaintext size. Suppose we have a plaintext vector p= [3,1,4,1,5] encrypted
using this scheme and a homomorphic operation that requires adding two ciphertexts together. If
the size of each ciphertext is 4 bytes, what is the total ciphertext size required for this operation?
Solution 6. a) Given that the plaintext vector p= [3,1,4,1,5] is encrypted using a homomorphic
encryption scheme with a ciphertext size of 4 bytes each, the total ciphertext size required for a
homomorphic addition operation can be calculated as follows:
b) Since the ciphertext size grows linearly with the plaintext size, the total ciphertext size re-
quired for encrypting the plaintext vector pis determined by multiplying the number of plaintext
elements by the size of each ciphertext. For a plaintext vector of length n, the total ciphertext size
is given by:
Total ciphertext size =n×Size of each ciphertext
In this case, n= 5 (as there are 5 elements in the plaintext vector) and the size of each ciphertext
is 4 bytes. Substituting these values into the formula:
Total ciphertext size = 5 ×4 = 20 bytes
Thus, the total ciphertext size required for a homomorphic addition operation on the given plain-
text vector using a 4-byte ciphertext scheme would be 20 bytes.
8 Cryptographic Applications of Homomorphic Encryption
Problem: Consider a fully homomorphic encryption scheme where the public key is (n= 5, q =
7) and the secret key is (a= 3).
a) Encrypt the plaintext message m= 4.
b) Perform a homomorphic addition on the ciphertexts corresponding to m1= 4 and m2= 3.
c) Perform a homomorphic multiplication on the ciphertext corresponding to m3= 2.
Solution:
a) To encrypt the plaintext message m= 4, we use the encryption function:
c= (a·r+ 2m) mod q
where ris a random integer. Plugging in m= 4,a= 3,q= 7, and choosing r= 2 for
demonstration purposes:
c= (3 ·2+2·4) mod 7 = (6 + 8) mod 7 = 14 mod 7 = 0
Therefore, the encrypted ciphertext for m= 4 is c= 0.
b) For homomorphic addition on two ciphertexts c1and c2corresponding to m1= 4 and m2= 3,
we can simply add the ciphertexts together modulo q:
cadd = (c1+c2) mod q
Given c1= 0 and c2= (3 ·2+2·3) mod 7 = 12 mod 7 = 5, we have:
cadd = (0 + 5) mod 7 = 5
Therefore, the resulting ciphertext after homomorphic addition is cadd = 5.
c) For homomorphic multiplication on the ciphertext corresponding to m3= 2, we perform the
multiplication modulo q:
cmul = (c·ma
3) mod q
Given c= 0 and m3= 2, we have:
cmul = (0 ·23) mod 7 = 0
Therefore, the resulting ciphertext after homomorphic multiplication is cmul = 0.
9 8. ERROR RATES IN HOMOMORPHIC ENCRYPTION
Problem 8. In a homomorphic encryption scheme, the probability of an error occurring during
the encryption process is 0.05. If a computation involves 20 homomorphic operations, what is the
probability that at least one error occurs during the computation?
Solution 8. Let’s denote the probability of an error occurring during a single homomorphic
operation as p= 0.05. The probability of no error occurring during a single operation is 1−p= 0.95.
The probability that at least one error occurs during the 20 computations can be calculated
using the complement rule (the probability of the event happening is 1 minus the probability of the
event not happening).
The probability of no error occurring during all 20 computations is (0.95)20.
Therefore, the probability of at least one error occurring is:
P(at least one error) = 1 −P(no error in 20 computations)
= 1 −(0.95)20
≈1−0.358485
≈0.641515 (approximately)
So, the probability that at least one error occurs during the computation involving 20 homomor-
phic operations is approximately 0.641515, or 64.15
10 9. KEY MANAGEMENT CHALLENGES IN HOMOMORPHIC ENCRYPTION
Problem 9. Consider a homomorphic encryption scheme where the public key is (n, e)and the
private key is (n, d), where n= 187,e= 7, and d= 23. Given a plaintext message m= 42, encrypt
the message using the public key and then decrypt the ciphertext using the private key.
Solution 9. a) To encrypt the message m= 42 using the public key (n, e), we compute the
ciphertext cusing the encryption function: c≡me(mod n).
Substitute m= 42,e= 7, and n= 187 into the encryption function:
c≡427(mod 187)
Calculating 427(mod 187):
427= 1406408618242
1406408618242 ≡29 (mod 187)
Therefore, the ciphertext cis 29.
b) To decrypt the ciphertext c= 29 using the private key (n, d), we compute the decrypted
message musing the decryption function: m≡cd(mod n).
Substitute c= 29,d= 23, and n= 187 into the decryption function:
m≡2923 (mod 187)
Calculating 2923 (mod 187):
2923 = 49298393010889
49298393010889 ≡42 (mod 187)
Therefore, the decrypted message mis 42, which matches the original plaintext message.
11 10. RELIABILITY CONCERNS IN HOMOMORPHIC ENCRYPTION
Problem 10. Consider a homomorphic encryption scheme where the key generation process
has a 5% chance of generating an incorrect key. Suppose a ciphertext is encrypted using such an
incorrect key.
a) What is the effect on the decryption process if the key is incorrect?
b) Calculate the probability that at least one out of five ciphertexts is decrypted incorrectly due
to a wrong key.
Solution 10.
a) If a ciphertext is encrypted using an incorrect key in a homomorphic encryption scheme,
the decryption process will result in an incorrect plaintext. This is because the decryption process
relies on the correctness of the key to properly recover the original plaintext from the ciphertext.
b) In this case, the probability of a key being incorrect is 5%, so the probability of a key being
correct is 95%, or 0.95. Since there are five ciphertexts, the probability of at least one being
decrypted incorrectly is equal to 1 minus the probability that all five are decrypted correctly.
Let pbe the probability that a ciphertext is decrypted correctly using the correct key. Therefore,
the probability that a ciphertext is decrypted incorrectly using the incorrect key is 1−p.
The probability that all five ciphertexts are decrypted correctly is p5, and the probability that at
least one is decrypted incorrectly is 1−p5.
Substitute p= 0.95 into the formula:
Probability of at least one incorrect decryption = 1 −(0.95)5
= 1 −0.77378
= 0.22622
Therefore, the probability that at least one out of five ciphertexts is decrypted incorrectly due to
a wrong key is approximately 0.22622 (or 22.622%).
12 11. TRUSTWORTHINESS OF HOMOMORPHIC ENCRYPTION
Problem 11. Consider a homomorphic encryption scheme where the encryption function E
and the decryption function Dare defined as follows:
E(x) = x2mod 17
D(y) = √ymod 17
Suppose we want to perform homomorphic addition and multiplication on two plaintext values.
Specifically, given the plaintext values m1= 4 and m2= 11, find the encryption of the sum m1+m2
and the encryption of the product m1×m2using the above encryption scheme. Also, decrypt the
results to obtain the plaintext values.
Solution 11.
a) To find the encryption of the sum m1+m2, we first calculate the sum modulo 17:
m1+m2= 4 + 11 = 15
Next, we calculate the encryption using the encryption function E:
E(15) = 152mod 17 = 225 mod 17 = 4
Therefore, the encryption of the sum m1+m2is 4.
b) To find the encryption of the product m1×m2, we first calculate the product modulo 17:
m1×m2= 4 ×11 = 44
Next, we calculate the encryption using the encryption function E:
E(44) = 442mod 17 = 1936 mod 17 = 16
Therefore, the encryption of the product m1×m2is 16.
c) To decrypt the results, we use the decryption function D:
For the encrypted sum 4:
D(4) = √4 mod 17 = 2
Thus, the decrypted plaintext value for the sum is 2.
For the encrypted product 16:
D(16) = √16 mod 17 = 4
Therefore, the decrypted plaintext value for the product is 4.
13 12. COMPLEXITY IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 12. Consider a homomorphic encryption scheme where the encryption function is
defined as E(m) = m2mod 13.
a) Encrypt the message m= 5.
b) Perform the homomorphic addition of two ciphertexts encrypted with the values m1= 3 and
m2= 4.
c) Decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13.
Solution 12.
a) We are given the encryption function E(m) = m2mod 13. To encrypt the message m= 5,
we substitute m= 5 into the encryption function:
E(5) = 52mod 13 = 25 mod 13 = 12.
Therefore, the encrypted ciphertext for the message m= 5 is 12.
b) To perform homomorphic addition, we calculate the sum of the ciphertexts created by en-
crypting m1= 3 and m2= 4:
E(3) = 32mod 13 = 9 mod 13 = 9
E(4) = 42mod 13 = 16 mod 13 = 3
Now, we add the ciphertexts: 9 + 3 = 12.
Therefore, the homomorphically added ciphertext is 12.
c) To decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13, we substitute c= 12 into the decryption function:
D(12) = √12 mod 13 ≈3.4641 mod 13 ≈3
Therefore, the decrypted message corresponding to the ciphertext 12 is 3.
14 13. PRIVACY RISKS OF HOMOMORPHIC ENCRYPTION
Problem 13. Consider a scenario where a company wants to use homomorphic encryption to
compute the sum of salaries of its employees without decrypting the individual salaries to ensure
privacy. The encryption scheme being used is a fully homomorphic encryption scheme that sup-
ports addition and multiplication operations. The company has encrypted the salaries using the
homomorphic encryption scheme, with each salary encoded as an integer.
The encrypted salaries are as follows: e1= 24,e2= 37,e3= 19, and e4= 42, where each eiis
the encrypted salary of employee i.
a) Compute the encrypted sum of the salaries, Enc(24 + 37 + 19 + 42).
b) The company also wants to compute the encrypted product of the salaries. Find Enc(24 ×
37 ×19 ×42).
c) If the company decrypts the sum of the encrypted salaries, will it reveal any information about
the individual salaries? Justify your answer.
Solution 13.
a) To compute the encrypted sum of the salaries, we can directly add the encrypted salaries:
Enc(24 + 37 + 19 + 42) = e1+e2+e3+e4= 24 + 37 + 19 + 42 = 122.
Therefore, the encrypted sum of the salaries is Enc(24 + 37 + 19 + 42) = 122.
b) To compute the encrypted product of the salaries, we can multiply the encrypted salaries:
Enc(24 ×37 ×19 ×42) = e1×e2×e3×e4= 24 ×37 ×19 ×42 = 387216.
Therefore, the encrypted product of the salaries is Enc(24 ×37 ×19 ×42) = 387216.
c) Homomorphic encryption provides the ability to perform computations on encrypted data
without decrypting it. When the company decrypts only the sum of the encrypted salaries, it will
not reveal any information about the individual salaries. This is because the encryption scheme
used is secure and ensures that the individual encrypted values remain confidential even after the
computation.
15 14. HOMOMORPHIC ENCRYPTION IN REAL-WORLD APPLICATIONS
Problem 14. Consider a scenario where a data processing company wants to outsource the
computation of the average salary of its employees to a cloud server using homomorphic encryp-
tion. The employees’ salaries are encrypted using a partially homomorphic encryption scheme that
supports addition and multiplication operations. Each employee’s salary is encrypted as follows:
E(s) = s2mod 11, where sis the plaintext salary.
a) If the company has four employees with salaries s1= 3,s2= 5,s3= 4, and s4= 6, calculate
the encrypted values for each of their salaries.
b) Compute the sum of the encrypted salaries.
c) Using homomorphic properties, decrypt the result to obtain the average salary of the em-
ployees.
Solution 14. a) To calculate the encrypted values for each employee’s salary:
Given E(s) = s2mod 11,
For s1= 3:E(3) = 32mod 11 = 9 mod 11 = 9
For s2= 5:E(5) = 52mod 11 = 25 mod 11 = 3
For s3= 4:E(4) = 42mod 11 = 16 mod 11 = 5
For s4= 6:E(6) = 62mod 11 = 36 mod 11 = 3
Therefore, the encrypted values for the employees’ salaries are: 9, 3, 5, 3.
b) To compute the sum of the encrypted salaries:
Sum of encrypted salaries = 9 + 3 + 5 + 3 = 20.
c) Since the encryption scheme supports multiplication and addition homomorphically, we can
decrypt the result of the sum by computing the inverse operation of squaring modulo 11, which is
finding the square root modulo 11.
20 ≡x2mod 11
Calculating the square root modulo 11:
x≡ ±√20 mod 11
x≡ ±4 mod 11
Hence, the possible decrypted values are 4 and 7. Since 4 is the correct average salary of the
employees, the decrypted average salary is 4.
16 Cryptographic Applications of Homomorphic Encryption
Problem: Using a fully homomorphic encryption scheme, Alice wants to perform the following
computation: E(m1)·E(m2) + E(m3)−E(m4), where Edenotes the encryption function and
m1= 5,m2= 3,m3= 7, and m4= 2. The encryption function transforms each message to their
encrypted form using the public key.
Assume the following encrypted values are obtained: E(m1) = 10,E(m2) = 8,E(m3) = 15,
and E(m4) = 5. Alice wishes to calculate the result of the above computation without decrypting
any values.
Solution:
Given: E(m1) = 10,E(m2)=8,E(m3) = 15, and E(m4) = 5.
a) Calculate the result of the computation E(m1)·E(m2).
b) Calculate the result of the computation E(m1)·E(m2) + E(m3).
c) Calculate the final result of the original computation.
Solution:
a) E(m1)·E(m2) = 10 ·8 = 80.
b) E(m1)·E(m2) + E(m3) = 80 + 15 = 95.
c) Finally, the original computation E(m1)·E(m2) + E(m3)−E(m4)becomes 95 −5 = 90.
Therefore, the final result of the computation without decrypting any values is 90.
17 16. USABILITY CHALLENGES OF HOMOMORPHIC ENCRYPTION
Problem 16. Consider a homomorphic encryption scheme where the encryption function is
E(x) = x2mod 13. Encrypt the message m= 3 using this scheme.
Solution 16. To encrypt the message m= 3, we substitute x= 3 into the encryption function
E(x) = x2mod 13.
Therefore, the encrypted message is:
E(3) = 32mod 13 = 9 mod 13 = 9
So, the encrypted message for m= 3 is 9.
18 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to securely outsource a computation to a cloud server using fully homo-
morphic encryption. She encrypts her input data xusing the homomorphic encryption scheme, and
sends it to the server. The server performs some computation on the encrypted data and returns
the result yto Alice. If the encryption scheme is fully homomorphic with the following properties:
- Addition: E(a) + E(b) = E(a+b)- Multiplication: E(a)×E(b) = E(a×b)
and the server computes E(3x+ 2), what will be the decrypted result that Alice receives?
Solution 1. Given that E(3x+2) = E(3)×E(x)+E(2), we expand this using the homomorphic
properties:
=E(3) ×E(x) + E(2)
=E(3) ×E(x) + E(2 ×1)
=E(3) ×E(x) + E(2) = E(3) ×E(x+ 1)
=E(3) ×E(x+x) + E(2) = E(3) ×E(2x) + E(2)
=E(3) ×E(x×2) + E(2) = E(6) ×E(x) + E(2)
=E(6) ×E(x) + E(2) = E(6x) + E(2)
Therefore, the decrypted result that Alice receives is 6x+ 2.
Problem 2. Bob wants to perform the computation 4x2−2x+ 5 on his encrypted data using
a partially homomorphic encryption scheme that supports addition but not multiplication. If he
encrypts xas E(x) = x2+3x−1, calculate the result that Bob will receive after the server performs
the computation using this homomorphic property.
Solution 2. Given that E(4x2−2x+ 5) = E(4x2) + E(−2x) + E(5), we use the homomorphic
property of addition:
=E(4) ×E(x2) + E(−2) ×E(x) + E(5)
=E(4) ×(x2+ 3x−1) + E(−2) ×x2+E(5)
=E(4x2+ 12x−4) + E(−2x2) + E(5)
=E(2x2+ 12x+ 1)
Therefore, the result that Bob will receive after the server performs the computation is 2x2+
12x+ 1.
19 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to send sensitive medical data to Bob using homomorphic encryp-
tion. She encrypts the data with a homomorphic scheme that supports addition and multiplication
operations. The plaintext data is x= 7, and the encryption function is defined as:
E(x) = x+rmod q
where ris a random number from the range [0,10] and q= 13. Calculate the encryption of xand
determine what operations Bob can perform on the encrypted data.
Solution 1. Given: x= 7,q= 13,r∈[0,10]
First, we randomly select a value of rfrom the range [0,10]. Let’s choose r= 3.
The encryption of xis then:
E(x) = x+rmod q= 7 + 3 mod 13 = 10
Therefore, the encryption of xis 10. Bob can now perform additions and multiplications on the
encrypted data without decrypting it.
20 19. HOMOMORPHIC ENCRYPTION IN FINANCIAL TRANSACTIONS
Problem 19. A bank wants to use homomorphic encryption to securely calculate the total
balance of its customers without knowing the individual balances. The bank assigns encrypted
values to represent the balances of three customers as follows: Customer A’s balance is encrypted
as 10, Customer B’s balance is encrypted as 15, and Customer C’s balance is encrypted as 8.
The bank uses the homomorphic property to perform secure calculations without decrypting the
balances.
a) If the bank wants to calculate the sum of the balances of Customer A and Customer B using
homomorphic addition, what encrypted value represents this sum?
b) If the bank wants to calculate the product of the balances of Customer A and Customer C
using homomorphic multiplication, what encrypted value represents this product?
c) Using the result from part a, if the bank also wants to subtract the balance of Customer B from
the sum of Customer A and B, what encrypted value represents this subtraction using homomorphic
subtraction?
Solution 19.
a) To calculate the sum of the balances of Customer A and Customer B using homomorphic
addition, we simply add their encrypted values:
Encrypted sum = Encrypted value of A + Encrypted value of B = 10 + 15 = 25.
Therefore, the encrypted value representing the sum of the balances of Customer A and Cus-
tomer B is 25.
b) To calculate the product of the balances of Customer A and Customer C using homomorphic
multiplication, we multiply their encrypted values:
Encrypted product = Encrypted value of A ×Encrypted value of C = 10 ×8 = 80.
Therefore, the encrypted value representing the product of the balances of Customer A and
Customer C is 80.
c) Using the result from part a, we have the encrypted value representing the sum of the bal-
ances of Customer A and B as 25. To subtract the balance of Customer B (15) from this sum using
homomorphic subtraction, we perform:
Encrypted subtraction = Encrypted sum - Encrypted value of B = 25 −15 = 10.
Therefore, the encrypted value representing the subtraction of the balance of Customer B from
the sum of Customer A and B is 10.
21 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where Alice wants to perform a homomorphic encryption
operation using the Paillier cryptosystem. She has two plaintext values m1= 7 and m2= 5, and
random parameters p= 17,q= 11,n=p·q,g=n+ 1. Assume that the public key is (n, g).
a) Encrypt both plaintext values m1and m2using the Paillier cryptosystem. b) Compute the
homomorphic sum of the ciphertexts corresponding to m1and m2. c) Decrypt the result of the
homomorphic sum to obtain the plaintext value.
Solution 1. a) To encrypt a plaintext value min the Paillier cryptosystem, we use the encryption
function E(m) = gm·rnmod n2, where ris a random number.
For m1= 7:E(7) = g7·rnmod n2= (287·r187 mod 1872)
For m2= 5:E(5) = g5·rnmod n2= (285·r187 mod 1872)
b) To compute the homomorphic sum of two ciphertexts in the Paillier cryptosystem, we multiply
the ciphertexts together. Therefore, the homomorphic sum of m1and m2would be: E(m1)×
E(m2) = (287·r187 mod 1872)×(285·r187 mod 1872)
c) To decrypt the result of the homomorphic sum, we use the decryption function D(c) = L(cλ
mod n2)·µmod n, where L(x) = x−1
n,λ=lcm(p−1, q −1), and µ=L(gλmod n2)−1mod n.
First, we compute the homomorphic sum: E(m1)×E(m2) = [step to multiply the ciphertexts]
Then, we decrypt the result as follows: D(E(m1)×E(m2)) = [steps to decrypt and obtain the
plaintext value]
22 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where a data scientist wants to securely compute the average
of a list of numbers using homomorphic encryption. The data scientist encrypts the numbers using
a homomorphic encryption scheme and performs the necessary computation. If the list of numbers
to be averaged is encrypted as follows:
- Number 1: E(5) = 15 - Number 2: E(8) = 26 - Number 3: E(3) = 13 - Number 4: E(10) = 34
Determine the encrypted result after computing the average and decrypt it to obtain the final
result.
Solution 1.
a) To compute the average homomorphically, we need to sum all the encrypted numbers and
divide the result by the total count of numbers.
The sum of the encrypted numbers:
E(5) + E(8) + E(3) + E(10) = 15 + 26 + 13 + 34 = 88
b) Now, we need to divide the encrypted sum by the total count of numbers, which is 4:
E(average) = 88
4= 22
Thus, the encrypted result after computing the average is 22.
c) To obtain the final result, we need to decrypt the encrypted average using the homomorphic
encryption scheme’s decryption function.
Decryption:
D(22) = 22
2= 11
Therefore, the final result of averaging the list of numbers is 11.
23 22. HOMOMORPHIC ENCRYPTION IN DATA ANALYTICS
Problem 22. Consider a scenario where a data scientist wants to perform statistical analysis on
encrypted data using homomorphic encryption. The data scientist has two integer values encrypted
using a homomorphic encryption scheme: a=Enc(3) and b=Enc(5).
a) Compute the encrypted value of a+b.
b) Compute the encrypted value of 2a−b.
Solution 22.
a) To compute the encrypted value of a+b, we need to use the properties of homomorphic
encryption. In a partially homomorphic encryption scheme, we can perform addition on encrypted
values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of a+bis Enc(3) + Enc(5) = Enc(3 + 5) = Enc(8).
Therefore, the encrypted value of a+bis Enc(8).
b) To compute the encrypted value of 2a−b, we again utilize the properties of homomorphic
encryption. We can perform scalar multiplication and subtraction on encrypted values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of 2a−bis 2×Enc(3) −Enc(5) = Enc(2 ×3−5) = Enc(1).
Therefore, the encrypted value of 2a−bis Enc(1).
24 23. HOMOMORPHIC ENCRYPTION IN MACHINE LEARNING
Problem 23. Consider a machine learning model that uses homomorphic encryption for privacy-
preserving computations. The model receives encrypted features X={x1, x2, x3}and encrypted
labels Y={y1, y2, y3}. After performing the necessary computations, the encrypted predictions
are Z={z1, z2, z3}. Assume the computations follow the equation: zi=w×xi+b, where wis the
weight, bis the bias, and xi,yi, and ziare encrypted values.
Given: x1= 5,y1= 7,z1= 42 (all values encrypted) x2= 3,y2= 5, and z2= 24 (all values
encrypted)
a) Calculate the weight w.
b) Calculate the bias b.
Solution 23.
a) To find the weight w, we can use the formula zi=w×xi+b.
For i= 1:
z1=w×x1+b
42 = w×5 + b
For i= 2:
z2=w×x2+b
24 = w×3 + b
Solving these two equations simultaneously, we get:
w=z1−z2
x1−x2
=42 −24
5−3=18
2= 9
Therefore, the weight w= 9.
b) To find the bias b, we can substitue w= 9 into one of the equations. Let’s use the first
equation when i= 1:
42 = 9 ×5 + b
42 = 45 + b
b= 42 −45 = −3
Therefore, the bias b=−3.
25 Cryptographic Applications of Homomorphic Encryption
Problem 1. In an e-voting system that uses homomorphic encryption, the votes for candidates
A,B, and Care encrypted as follows: a= 6,b= 8, and c= 4, respectively. The encryption scheme
uses additive homomorphic properties. The result of multiplying the ciphertexts for candidates A
and Bis calculated as a×b= 30. Find out the encrypted vote for candidate C.
Solution 1. Given that the encryption scheme is additive homomorphic, we can calculate the
encrypted vote for candidate Cusing the properties of homomorphic encryption.
We know that a×brepresents the product of ciphertexts for candidates Aand B. Thus, a×b=
30.
Now, to find the encrypted vote for candidate C, we can utilize the additive homomorphic prop-
erty, which states that multiplying ciphertexts corresponds to adding plaintexts. Therefore, the
encrypted vote for candidate Cwill be:
a×b+c= 30 + c
Given a= 6,b= 8, and c= 4, substituting these values:
30 + 4 = 34
Therefore, the encrypted vote for candidate Cis 34.
26 25. HOMOMORPHIC ENCRYPTION IN SECURE COMMUNICATION PROTOCOLS
Problem 25. Alice wants to perform a secure computation on encrypted data using a homo-
morphic encryption scheme. She has two encrypted values c1and c2, where c1=Encpk(7) and
c2=Encpk(5), encrypted under a public key pk. She wants to calculate the sum and product of
the decrypted values without revealing the encryption key. Assume the homomorphic encryption
scheme supports both addition and multiplication operations homomorphically.
Solution 25. a) To calculate the sum of the decrypted values, Alice can perform homomorphic
addition on the encrypted values c1and c2. Let csum =c1⊕c2.
The decryption of csum will give the sum of the decrypted values:
Decsk(csum) = Decsk(c1⊕c2)
=Decsk(Encpk(7) ⊕Encpk (5))
=Decsk(Encpk(7 + 5))
=Decsk(Encpk(12))
= 12
Therefore, the sum of the decrypted values is 12.
b) To calculate the product of the decrypted values, Alice can perform homomorphic multipli-
cation on the encrypted values c1and c2. Let cprod =c1⊗c2.
The decryption of cprod will give the product of the decrypted values:
Decsk(cprod) = Decsk(c1⊗c2)
=Decsk(Encpk(7) ⊗Encpk (5))
=Decsk(Encpk(7 ×5))
=Decsk(Encpk(35))
= 35
Therefore, the product of the decrypted values is 35.
3 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to perform a homomorphic encryption on a message m= 7 using a fully
homomorphic encryption scheme. The public key for this scheme is n= 13 and the encryption
function is defined as E(x) = x2mod n. Calculate the encrypted message.
Solution 1. To encrypt the message using the homomorphic encryption scheme, we need to
compute E(m):
E(m) = E(7) = 72mod 13 = 49 mod 13 = 10
Therefore, the encrypted message is 10.
4 Cryptographic Applications of Homomorphic Encryption
Problem 2. Bob wants to perform a homomorphic addition on two encrypted messages. The
encrypted messages are c1= 8 and c2= 12, and the public key for the homomorphic encryption
scheme is n= 17. If the encryption function is defined as E(x) = x2mod n, calculate the result
of adding the two encrypted messages together.
Solution 2. To perform homomorphic addition on the encrypted messages, we first need to
decrypt the messages, add them together, and then re-encrypt the sum:
Step 1: Decrypt the messages
C1=c
n+1
4
1mod n= 85mod 17 = 8
C2=c
n+1
4
2mod n= 125mod 17 = 12
Step 2: Add the decrypted messages
D=C1+C2= 8 + 12 = 20
Step 3: Re-encrypt the sum
E(D) = D2mod 17 = 202mod 17 = 400 mod 17 = 11
Therefore, the result of adding the two encrypted messages together is 11.
5 4. LIMITATIONS OF HOMOMORPHIC ENCRYPTION
Problem 4. Consider a fully homomorphic encryption scheme where the ciphertext space is
integers modulo N= 29. Alice wants to perform the following computations:
a) Encrypt the integer 9 using the encryption function.
b) Add two encrypted integers, the encryption of 5 and 12.
c) Multiply an encrypted integer, the encryption of 3, by an encrypted integer, the encryption of
7.
Solution 4.
a) To encrypt the integer 9, we first need to choose a public key (N, q, h)for the encryption
scheme. Let q= 31 and h= 6. Then the encryption function is defined as follows:
Encrypt(m) = mh + 2rmod N
where m= 9, and ris a random integer modulo N. Let’s choose r= 7. Thus, the encryption
of 9 is:
Encrypt(9) = 9∗6+2∗7 mod 29 = 54 + 14 mod 29 = 68 mod 29 = 10
Therefore, the encryption of 9 is 10.
b) To add two encrypted integers, we simply add them modulo N. Let’s consider the encryption
of 5 and 12:
Encrypt(5) = 5∗6+2∗7 mod 29 = 32 mod 29 = 3
Encrypt(12) = 12 ∗6+2∗7 mod 29 = 74 mod 29 = 16
Adding the two encrypted integers:
Encrypt(5) +Encrypt(12) = 3 + 16 mod 29 = 19
Therefore, the sum of the encrypted integers 5 and 12 is 19.
c) For multiplication of two encrypted integers, we multiply the two ciphertexts modulo N. Let’s
multiply the encryption of 3 and 7:
Encrypt(3) = 3∗6+2∗7 mod 29 = 20
Encrypt(7) = 7∗6+2∗7 mod 29 = 49 mod 29 = 20
Multiplying the two encrypted integers:
Encrypt(3) ·Encrypt(7) = 20 ∗20 mod 29 = 400 mod 29 = 16
Therefore, the product of the encrypted integers 3 and 7 is 16.
6 Cryptographic Applications of Homomorphic Encryption
Problem: Suppose we have two ciphertexts c1and c2encrypted under the same homomorphic
encryption scheme, and we want to compute the product of the plaintexts they represent. Let the
decryption function be Dec(·).
Given that Dec(c1) = 7 and Dec(c2) = 4, and we know that the homomorphic encryption
scheme supports homomorphic multiplication, calculate the decryption of the product of the plain-
texts represented by c1and c2, i.e., find Dec(c1×c2).
Solution: Since the homomorphic encryption scheme supports homomorphic multiplication,
we can calculate the product of the plaintexts without decrypting c1and c2individually.
Let’s assume that the product of the plaintexts represented by c1and c2is denoted as m1×m2.
Since Dec(c1) = 7 and Dec(c2)=4, we have m1= 7 and m2= 4.
Now, to find Dec(c1×c2), we calculate the product of the plaintexts represented by c1and c2,
which is m1×m2= 7 ×4 = 28.
Therefore, Dec(c1×c2) = 28.
7 6. SCALABILITY PROBLEMS IN HOMOMORPHIC ENCRYPTION
Problem 6. Consider a homomorphic encryption scheme where the ciphertext size grows
linearly with the plaintext size. Suppose we have a plaintext vector p= [3,1,4,1,5] encrypted
using this scheme and a homomorphic operation that requires adding two ciphertexts together. If
the size of each ciphertext is 4 bytes, what is the total ciphertext size required for this operation?
Solution 6. a) Given that the plaintext vector p= [3,1,4,1,5] is encrypted using a homomorphic
encryption scheme with a ciphertext size of 4 bytes each, the total ciphertext size required for a
homomorphic addition operation can be calculated as follows:
b) Since the ciphertext size grows linearly with the plaintext size, the total ciphertext size re-
quired for encrypting the plaintext vector pis determined by multiplying the number of plaintext
elements by the size of each ciphertext. For a plaintext vector of length n, the total ciphertext size
is given by:
Total ciphertext size =n×Size of each ciphertext
In this case, n= 5 (as there are 5 elements in the plaintext vector) and the size of each ciphertext
is 4 bytes. Substituting these values into the formula:
Total ciphertext size = 5 ×4 = 20 bytes
Thus, the total ciphertext size required for a homomorphic addition operation on the given plain-
text vector using a 4-byte ciphertext scheme would be 20 bytes.
8 Cryptographic Applications of Homomorphic Encryption
Problem: Consider a fully homomorphic encryption scheme where the public key is (n= 5, q =
7) and the secret key is (a= 3).
a) Encrypt the plaintext message m= 4.
b) Perform a homomorphic addition on the ciphertexts corresponding to m1= 4 and m2= 3.
c) Perform a homomorphic multiplication on the ciphertext corresponding to m3= 2.
Solution:
a) To encrypt the plaintext message m= 4, we use the encryption function:
c= (a·r+ 2m) mod q
where ris a random integer. Plugging in m= 4,a= 3,q= 7, and choosing r= 2 for
demonstration purposes:
c= (3 ·2+2·4) mod 7 = (6 + 8) mod 7 = 14 mod 7 = 0
Therefore, the encrypted ciphertext for m= 4 is c= 0.
b) For homomorphic addition on two ciphertexts c1and c2corresponding to m1= 4 and m2= 3,
we can simply add the ciphertexts together modulo q:
cadd = (c1+c2) mod q
Given c1= 0 and c2= (3 ·2+2·3) mod 7 = 12 mod 7 = 5, we have:
cadd = (0 + 5) mod 7 = 5
Therefore, the resulting ciphertext after homomorphic addition is cadd = 5.
c) For homomorphic multiplication on the ciphertext corresponding to m3= 2, we perform the
multiplication modulo q:
cmul = (c·ma
3) mod q
Given c= 0 and m3= 2, we have:
cmul = (0 ·23) mod 7 = 0
Therefore, the resulting ciphertext after homomorphic multiplication is cmul = 0.
9 8. ERROR RATES IN HOMOMORPHIC ENCRYPTION
Problem 8. In a homomorphic encryption scheme, the probability of an error occurring during
the encryption process is 0.05. If a computation involves 20 homomorphic operations, what is the
probability that at least one error occurs during the computation?
Solution 8. Let’s denote the probability of an error occurring during a single homomorphic
operation as p= 0.05. The probability of no error occurring during a single operation is 1−p= 0.95.
The probability that at least one error occurs during the 20 computations can be calculated
using the complement rule (the probability of the event happening is 1 minus the probability of the
event not happening).
The probability of no error occurring during all 20 computations is (0.95)20.
Therefore, the probability of at least one error occurring is:
P(at least one error) = 1 −P(no error in 20 computations)
= 1 −(0.95)20
≈1−0.358485
≈0.641515 (approximately)
So, the probability that at least one error occurs during the computation involving 20 homomor-
phic operations is approximately 0.641515, or 64.15
10 9. KEY MANAGEMENT CHALLENGES IN HOMOMORPHIC ENCRYPTION
Problem 9. Consider a homomorphic encryption scheme where the public key is (n, e)and the
private key is (n, d), where n= 187,e= 7, and d= 23. Given a plaintext message m= 42, encrypt
the message using the public key and then decrypt the ciphertext using the private key.
Solution 9. a) To encrypt the message m= 42 using the public key (n, e), we compute the
ciphertext cusing the encryption function: c≡me(mod n).
Substitute m= 42,e= 7, and n= 187 into the encryption function:
c≡427(mod 187)
Calculating 427(mod 187):
427= 1406408618242
1406408618242 ≡29 (mod 187)
Therefore, the ciphertext cis 29.
b) To decrypt the ciphertext c= 29 using the private key (n, d), we compute the decrypted
message musing the decryption function: m≡cd(mod n).
Substitute c= 29,d= 23, and n= 187 into the decryption function:
m≡2923 (mod 187)
Calculating 2923 (mod 187):
2923 = 49298393010889
49298393010889 ≡42 (mod 187)
Therefore, the decrypted message mis 42, which matches the original plaintext message.
11 10. RELIABILITY CONCERNS IN HOMOMORPHIC ENCRYPTION
Problem 10. Consider a homomorphic encryption scheme where the key generation process
has a 5% chance of generating an incorrect key. Suppose a ciphertext is encrypted using such an
incorrect key.
a) What is the effect on the decryption process if the key is incorrect?
b) Calculate the probability that at least one out of five ciphertexts is decrypted incorrectly due
to a wrong key.
Solution 10.
a) If a ciphertext is encrypted using an incorrect key in a homomorphic encryption scheme,
the decryption process will result in an incorrect plaintext. This is because the decryption process
relies on the correctness of the key to properly recover the original plaintext from the ciphertext.
b) In this case, the probability of a key being incorrect is 5%, so the probability of a key being
correct is 95%, or 0.95. Since there are five ciphertexts, the probability of at least one being
decrypted incorrectly is equal to 1 minus the probability that all five are decrypted correctly.
Let pbe the probability that a ciphertext is decrypted correctly using the correct key. Therefore,
the probability that a ciphertext is decrypted incorrectly using the incorrect key is 1−p.
The probability that all five ciphertexts are decrypted correctly is p5, and the probability that at
least one is decrypted incorrectly is 1−p5.
Substitute p= 0.95 into the formula:
Probability of at least one incorrect decryption = 1 −(0.95)5
= 1 −0.77378
= 0.22622
Therefore, the probability that at least one out of five ciphertexts is decrypted incorrectly due to
a wrong key is approximately 0.22622 (or 22.622%).
12 11. TRUSTWORTHINESS OF HOMOMORPHIC ENCRYPTION
Problem 11. Consider a homomorphic encryption scheme where the encryption function E
and the decryption function Dare defined as follows:
E(x) = x2mod 17
D(y) = √ymod 17
Suppose we want to perform homomorphic addition and multiplication on two plaintext values.
Specifically, given the plaintext values m1= 4 and m2= 11, find the encryption of the sum m1+m2
and the encryption of the product m1×m2using the above encryption scheme. Also, decrypt the
results to obtain the plaintext values.
Solution 11.
a) To find the encryption of the sum m1+m2, we first calculate the sum modulo 17:
m1+m2= 4 + 11 = 15
Next, we calculate the encryption using the encryption function E:
E(15) = 152mod 17 = 225 mod 17 = 4
Therefore, the encryption of the sum m1+m2is 4.
b) To find the encryption of the product m1×m2, we first calculate the product modulo 17:
m1×m2= 4 ×11 = 44
Next, we calculate the encryption using the encryption function E:
E(44) = 442mod 17 = 1936 mod 17 = 16
Therefore, the encryption of the product m1×m2is 16.
c) To decrypt the results, we use the decryption function D:
For the encrypted sum 4:
D(4) = √4 mod 17 = 2
Thus, the decrypted plaintext value for the sum is 2.
For the encrypted product 16:
D(16) = √16 mod 17 = 4
Therefore, the decrypted plaintext value for the product is 4.
13 12. COMPLEXITY IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 12. Consider a homomorphic encryption scheme where the encryption function is
defined as E(m) = m2mod 13.
a) Encrypt the message m= 5.
b) Perform the homomorphic addition of two ciphertexts encrypted with the values m1= 3 and
m2= 4.
c) Decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13.
Solution 12.
a) We are given the encryption function E(m) = m2mod 13. To encrypt the message m= 5,
we substitute m= 5 into the encryption function:
E(5) = 52mod 13 = 25 mod 13 = 12.
Therefore, the encrypted ciphertext for the message m= 5 is 12.
b) To perform homomorphic addition, we calculate the sum of the ciphertexts created by en-
crypting m1= 3 and m2= 4:
E(3) = 32mod 13 = 9 mod 13 = 9
E(4) = 42mod 13 = 16 mod 13 = 3
Now, we add the ciphertexts: 9 + 3 = 12.
Therefore, the homomorphically added ciphertext is 12.
c) To decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13, we substitute c= 12 into the decryption function:
D(12) = √12 mod 13 ≈3.4641 mod 13 ≈3
Therefore, the decrypted message corresponding to the ciphertext 12 is 3.
14 13. PRIVACY RISKS OF HOMOMORPHIC ENCRYPTION
Problem 13. Consider a scenario where a company wants to use homomorphic encryption to
compute the sum of salaries of its employees without decrypting the individual salaries to ensure
privacy. The encryption scheme being used is a fully homomorphic encryption scheme that sup-
ports addition and multiplication operations. The company has encrypted the salaries using the
homomorphic encryption scheme, with each salary encoded as an integer.
The encrypted salaries are as follows: e1= 24,e2= 37,e3= 19, and e4= 42, where each eiis
the encrypted salary of employee i.
a) Compute the encrypted sum of the salaries, Enc(24 + 37 + 19 + 42).
b) The company also wants to compute the encrypted product of the salaries. Find Enc(24 ×
37 ×19 ×42).
c) If the company decrypts the sum of the encrypted salaries, will it reveal any information about
the individual salaries? Justify your answer.
Solution 13.
a) To compute the encrypted sum of the salaries, we can directly add the encrypted salaries:
Enc(24 + 37 + 19 + 42) = e1+e2+e3+e4= 24 + 37 + 19 + 42 = 122.
Therefore, the encrypted sum of the salaries is Enc(24 + 37 + 19 + 42) = 122.
b) To compute the encrypted product of the salaries, we can multiply the encrypted salaries:
Enc(24 ×37 ×19 ×42) = e1×e2×e3×e4= 24 ×37 ×19 ×42 = 387216.
Therefore, the encrypted product of the salaries is Enc(24 ×37 ×19 ×42) = 387216.
c) Homomorphic encryption provides the ability to perform computations on encrypted data
without decrypting it. When the company decrypts only the sum of the encrypted salaries, it will
not reveal any information about the individual salaries. This is because the encryption scheme
used is secure and ensures that the individual encrypted values remain confidential even after the
computation.
15 14. HOMOMORPHIC ENCRYPTION IN REAL-WORLD APPLICATIONS
Problem 14. Consider a scenario where a data processing company wants to outsource the
computation of the average salary of its employees to a cloud server using homomorphic encryp-
tion. The employees’ salaries are encrypted using a partially homomorphic encryption scheme that
supports addition and multiplication operations. Each employee’s salary is encrypted as follows:
E(s) = s2mod 11, where sis the plaintext salary.
a) If the company has four employees with salaries s1= 3,s2= 5,s3= 4, and s4= 6, calculate
the encrypted values for each of their salaries.
b) Compute the sum of the encrypted salaries.
c) Using homomorphic properties, decrypt the result to obtain the average salary of the em-
ployees.
Solution 14. a) To calculate the encrypted values for each employee’s salary:
Given E(s) = s2mod 11,
For s1= 3:E(3) = 32mod 11 = 9 mod 11 = 9
For s2= 5:E(5) = 52mod 11 = 25 mod 11 = 3
For s3= 4:E(4) = 42mod 11 = 16 mod 11 = 5
For s4= 6:E(6) = 62mod 11 = 36 mod 11 = 3
Therefore, the encrypted values for the employees’ salaries are: 9, 3, 5, 3.
b) To compute the sum of the encrypted salaries:
Sum of encrypted salaries = 9 + 3 + 5 + 3 = 20.
c) Since the encryption scheme supports multiplication and addition homomorphically, we can
decrypt the result of the sum by computing the inverse operation of squaring modulo 11, which is
finding the square root modulo 11.
20 ≡x2mod 11
Calculating the square root modulo 11:
x≡ ±√20 mod 11
x≡ ±4 mod 11
Hence, the possible decrypted values are 4 and 7. Since 4 is the correct average salary of the
employees, the decrypted average salary is 4.
16 Cryptographic Applications of Homomorphic Encryption
Problem: Using a fully homomorphic encryption scheme, Alice wants to perform the following
computation: E(m1)·E(m2) + E(m3)−E(m4), where Edenotes the encryption function and
m1= 5,m2= 3,m3= 7, and m4= 2. The encryption function transforms each message to their
encrypted form using the public key.
Assume the following encrypted values are obtained: E(m1) = 10,E(m2) = 8,E(m3) = 15,
and E(m4) = 5. Alice wishes to calculate the result of the above computation without decrypting
any values.
Solution:
Given: E(m1) = 10,E(m2)=8,E(m3) = 15, and E(m4) = 5.
a) Calculate the result of the computation E(m1)·E(m2).
b) Calculate the result of the computation E(m1)·E(m2) + E(m3).
c) Calculate the final result of the original computation.
Solution:
a) E(m1)·E(m2) = 10 ·8 = 80.
b) E(m1)·E(m2) + E(m3) = 80 + 15 = 95.
c) Finally, the original computation E(m1)·E(m2) + E(m3)−E(m4)becomes 95 −5 = 90.
Therefore, the final result of the computation without decrypting any values is 90.
17 16. USABILITY CHALLENGES OF HOMOMORPHIC ENCRYPTION
Problem 16. Consider a homomorphic encryption scheme where the encryption function is
E(x) = x2mod 13. Encrypt the message m= 3 using this scheme.
Solution 16. To encrypt the message m= 3, we substitute x= 3 into the encryption function
E(x) = x2mod 13.
Therefore, the encrypted message is:
E(3) = 32mod 13 = 9 mod 13 = 9
So, the encrypted message for m= 3 is 9.
18 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to securely outsource a computation to a cloud server using fully homo-
morphic encryption. She encrypts her input data xusing the homomorphic encryption scheme, and
sends it to the server. The server performs some computation on the encrypted data and returns
the result yto Alice. If the encryption scheme is fully homomorphic with the following properties:
- Addition: E(a) + E(b) = E(a+b)- Multiplication: E(a)×E(b) = E(a×b)
and the server computes E(3x+ 2), what will be the decrypted result that Alice receives?
Solution 1. Given that E(3x+2) = E(3)×E(x)+E(2), we expand this using the homomorphic
properties:
=E(3) ×E(x) + E(2)
=E(3) ×E(x) + E(2 ×1)
=E(3) ×E(x) + E(2) = E(3) ×E(x+ 1)
=E(3) ×E(x+x) + E(2) = E(3) ×E(2x) + E(2)
=E(3) ×E(x×2) + E(2) = E(6) ×E(x) + E(2)
=E(6) ×E(x) + E(2) = E(6x) + E(2)
Therefore, the decrypted result that Alice receives is 6x+ 2.
Problem 2. Bob wants to perform the computation 4x2−2x+ 5 on his encrypted data using
a partially homomorphic encryption scheme that supports addition but not multiplication. If he
encrypts xas E(x) = x2+3x−1, calculate the result that Bob will receive after the server performs
the computation using this homomorphic property.
Solution 2. Given that E(4x2−2x+ 5) = E(4x2) + E(−2x) + E(5), we use the homomorphic
property of addition:
=E(4) ×E(x2) + E(−2) ×E(x) + E(5)
=E(4) ×(x2+ 3x−1) + E(−2) ×x2+E(5)
=E(4x2+ 12x−4) + E(−2x2) + E(5)
=E(2x2+ 12x+ 1)
Therefore, the result that Bob will receive after the server performs the computation is 2x2+
12x+ 1.
19 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to send sensitive medical data to Bob using homomorphic encryp-
tion. She encrypts the data with a homomorphic scheme that supports addition and multiplication
operations. The plaintext data is x= 7, and the encryption function is defined as:
E(x) = x+rmod q
where ris a random number from the range [0,10] and q= 13. Calculate the encryption of xand
determine what operations Bob can perform on the encrypted data.
Solution 1. Given: x= 7,q= 13,r∈[0,10]
First, we randomly select a value of rfrom the range [0,10]. Let’s choose r= 3.
The encryption of xis then:
E(x) = x+rmod q= 7 + 3 mod 13 = 10
Therefore, the encryption of xis 10. Bob can now perform additions and multiplications on the
encrypted data without decrypting it.
20 19. HOMOMORPHIC ENCRYPTION IN FINANCIAL TRANSACTIONS
Problem 19. A bank wants to use homomorphic encryption to securely calculate the total
balance of its customers without knowing the individual balances. The bank assigns encrypted
values to represent the balances of three customers as follows: Customer A’s balance is encrypted
as 10, Customer B’s balance is encrypted as 15, and Customer C’s balance is encrypted as 8.
The bank uses the homomorphic property to perform secure calculations without decrypting the
balances.
a) If the bank wants to calculate the sum of the balances of Customer A and Customer B using
homomorphic addition, what encrypted value represents this sum?
b) If the bank wants to calculate the product of the balances of Customer A and Customer C
using homomorphic multiplication, what encrypted value represents this product?
c) Using the result from part a, if the bank also wants to subtract the balance of Customer B from
the sum of Customer A and B, what encrypted value represents this subtraction using homomorphic
subtraction?
Solution 19.
a) To calculate the sum of the balances of Customer A and Customer B using homomorphic
addition, we simply add their encrypted values:
Encrypted sum = Encrypted value of A + Encrypted value of B = 10 + 15 = 25.
Therefore, the encrypted value representing the sum of the balances of Customer A and Cus-
tomer B is 25.
b) To calculate the product of the balances of Customer A and Customer C using homomorphic
multiplication, we multiply their encrypted values:
Encrypted product = Encrypted value of A ×Encrypted value of C = 10 ×8 = 80.
Therefore, the encrypted value representing the product of the balances of Customer A and
Customer C is 80.
c) Using the result from part a, we have the encrypted value representing the sum of the bal-
ances of Customer A and B as 25. To subtract the balance of Customer B (15) from this sum using
homomorphic subtraction, we perform:
Encrypted subtraction = Encrypted sum - Encrypted value of B = 25 −15 = 10.
Therefore, the encrypted value representing the subtraction of the balance of Customer B from
the sum of Customer A and B is 10.
21 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where Alice wants to perform a homomorphic encryption
operation using the Paillier cryptosystem. She has two plaintext values m1= 7 and m2= 5, and
random parameters p= 17,q= 11,n=p·q,g=n+ 1. Assume that the public key is (n, g).
a) Encrypt both plaintext values m1and m2using the Paillier cryptosystem. b) Compute the
homomorphic sum of the ciphertexts corresponding to m1and m2. c) Decrypt the result of the
homomorphic sum to obtain the plaintext value.
Solution 1. a) To encrypt a plaintext value min the Paillier cryptosystem, we use the encryption
function E(m) = gm·rnmod n2, where ris a random number.
For m1= 7:E(7) = g7·rnmod n2= (287·r187 mod 1872)
For m2= 5:E(5) = g5·rnmod n2= (285·r187 mod 1872)
b) To compute the homomorphic sum of two ciphertexts in the Paillier cryptosystem, we multiply
the ciphertexts together. Therefore, the homomorphic sum of m1and m2would be: E(m1)×
E(m2) = (287·r187 mod 1872)×(285·r187 mod 1872)
c) To decrypt the result of the homomorphic sum, we use the decryption function D(c) = L(cλ
mod n2)·µmod n, where L(x) = x−1
n,λ=lcm(p−1, q −1), and µ=L(gλmod n2)−1mod n.
First, we compute the homomorphic sum: E(m1)×E(m2) = [step to multiply the ciphertexts]
Then, we decrypt the result as follows: D(E(m1)×E(m2)) = [steps to decrypt and obtain the
plaintext value]
22 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where a data scientist wants to securely compute the average
of a list of numbers using homomorphic encryption. The data scientist encrypts the numbers using
a homomorphic encryption scheme and performs the necessary computation. If the list of numbers
to be averaged is encrypted as follows:
- Number 1: E(5) = 15 - Number 2: E(8) = 26 - Number 3: E(3) = 13 - Number 4: E(10) = 34
Determine the encrypted result after computing the average and decrypt it to obtain the final
result.
Solution 1.
a) To compute the average homomorphically, we need to sum all the encrypted numbers and
divide the result by the total count of numbers.
The sum of the encrypted numbers:
E(5) + E(8) + E(3) + E(10) = 15 + 26 + 13 + 34 = 88
b) Now, we need to divide the encrypted sum by the total count of numbers, which is 4:
E(average) = 88
4= 22
Thus, the encrypted result after computing the average is 22.
c) To obtain the final result, we need to decrypt the encrypted average using the homomorphic
encryption scheme’s decryption function.
Decryption:
D(22) = 22
2= 11
Therefore, the final result of averaging the list of numbers is 11.
23 22. HOMOMORPHIC ENCRYPTION IN DATA ANALYTICS
Problem 22. Consider a scenario where a data scientist wants to perform statistical analysis on
encrypted data using homomorphic encryption. The data scientist has two integer values encrypted
using a homomorphic encryption scheme: a=Enc(3) and b=Enc(5).
a) Compute the encrypted value of a+b.
b) Compute the encrypted value of 2a−b.
Solution 22.
a) To compute the encrypted value of a+b, we need to use the properties of homomorphic
encryption. In a partially homomorphic encryption scheme, we can perform addition on encrypted
values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of a+bis Enc(3) + Enc(5) = Enc(3 + 5) = Enc(8).
Therefore, the encrypted value of a+bis Enc(8).
b) To compute the encrypted value of 2a−b, we again utilize the properties of homomorphic
encryption. We can perform scalar multiplication and subtraction on encrypted values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of 2a−bis 2×Enc(3) −Enc(5) = Enc(2 ×3−5) = Enc(1).
Therefore, the encrypted value of 2a−bis Enc(1).
24 23. HOMOMORPHIC ENCRYPTION IN MACHINE LEARNING
Problem 23. Consider a machine learning model that uses homomorphic encryption for privacy-
preserving computations. The model receives encrypted features X={x1, x2, x3}and encrypted
labels Y={y1, y2, y3}. After performing the necessary computations, the encrypted predictions
are Z={z1, z2, z3}. Assume the computations follow the equation: zi=w×xi+b, where wis the
weight, bis the bias, and xi,yi, and ziare encrypted values.
Given: x1= 5,y1= 7,z1= 42 (all values encrypted) x2= 3,y2= 5, and z2= 24 (all values
encrypted)
a) Calculate the weight w.
b) Calculate the bias b.
Solution 23.
a) To find the weight w, we can use the formula zi=w×xi+b.
For i= 1:
z1=w×x1+b
42 = w×5 + b
For i= 2:
z2=w×x2+b
24 = w×3 + b
Solving these two equations simultaneously, we get:
w=z1−z2
x1−x2
=42 −24
5−3=18
2= 9
Therefore, the weight w= 9.
b) To find the bias b, we can substitue w= 9 into one of the equations. Let’s use the first
equation when i= 1:
42 = 9 ×5 + b
42 = 45 + b
b= 42 −45 = −3
Therefore, the bias b=−3.
25 Cryptographic Applications of Homomorphic Encryption
Problem 1. In an e-voting system that uses homomorphic encryption, the votes for candidates
A,B, and Care encrypted as follows: a= 6,b= 8, and c= 4, respectively. The encryption scheme
uses additive homomorphic properties. The result of multiplying the ciphertexts for candidates A
and Bis calculated as a×b= 30. Find out the encrypted vote for candidate C.
Solution 1. Given that the encryption scheme is additive homomorphic, we can calculate the
encrypted vote for candidate Cusing the properties of homomorphic encryption.
We know that a×brepresents the product of ciphertexts for candidates Aand B. Thus, a×b=
30.
Now, to find the encrypted vote for candidate C, we can utilize the additive homomorphic prop-
erty, which states that multiplying ciphertexts corresponds to adding plaintexts. Therefore, the
encrypted vote for candidate Cwill be:
a×b+c= 30 + c
Given a= 6,b= 8, and c= 4, substituting these values:
30 + 4 = 34
Therefore, the encrypted vote for candidate Cis 34.
26 25. HOMOMORPHIC ENCRYPTION IN SECURE COMMUNICATION PROTOCOLS
Problem 25. Alice wants to perform a secure computation on encrypted data using a homo-
morphic encryption scheme. She has two encrypted values c1and c2, where c1=Encpk(7) and
c2=Encpk(5), encrypted under a public key pk. She wants to calculate the sum and product of
the decrypted values without revealing the encryption key. Assume the homomorphic encryption
scheme supports both addition and multiplication operations homomorphically.
Solution 25. a) To calculate the sum of the decrypted values, Alice can perform homomorphic
addition on the encrypted values c1and c2. Let csum =c1⊕c2.
The decryption of csum will give the sum of the decrypted values:
Decsk(csum) = Decsk(c1⊕c2)
=Decsk(Encpk(7) ⊕Encpk (5))
=Decsk(Encpk(7 + 5))
=Decsk(Encpk(12))
= 12
Therefore, the sum of the decrypted values is 12.
b) To calculate the product of the decrypted values, Alice can perform homomorphic multipli-
cation on the encrypted values c1and c2. Let cprod =c1⊗c2.
The decryption of cprod will give the product of the decrypted values:
Decsk(cprod) = Decsk(c1⊗c2)
=Decsk(Encpk(7) ⊗Encpk (5))
=Decsk(Encpk(7 ×5))
=Decsk(Encpk(35))
= 35
Therefore, the product of the decrypted values is 35.
3 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to perform a homomorphic encryption on a message m= 7 using a fully
homomorphic encryption scheme. The public key for this scheme is n= 13 and the encryption
function is defined as E(x) = x2mod n. Calculate the encrypted message.
Solution 1. To encrypt the message using the homomorphic encryption scheme, we need to
compute E(m):
E(m) = E(7) = 72mod 13 = 49 mod 13 = 10
Therefore, the encrypted message is 10.
4 Cryptographic Applications of Homomorphic Encryption
Problem 2. Bob wants to perform a homomorphic addition on two encrypted messages. The
encrypted messages are c1= 8 and c2= 12, and the public key for the homomorphic encryption
scheme is n= 17. If the encryption function is defined as E(x) = x2mod n, calculate the result
of adding the two encrypted messages together.
Solution 2. To perform homomorphic addition on the encrypted messages, we first need to
decrypt the messages, add them together, and then re-encrypt the sum:
Step 1: Decrypt the messages
C1=c
n+1
4
1mod n= 85mod 17 = 8
C2=c
n+1
4
2mod n= 125mod 17 = 12
Step 2: Add the decrypted messages
D=C1+C2= 8 + 12 = 20
Step 3: Re-encrypt the sum
E(D) = D2mod 17 = 202mod 17 = 400 mod 17 = 11
Therefore, the result of adding the two encrypted messages together is 11.
5 4. LIMITATIONS OF HOMOMORPHIC ENCRYPTION
Problem 4. Consider a fully homomorphic encryption scheme where the ciphertext space is
integers modulo N= 29. Alice wants to perform the following computations:
a) Encrypt the integer 9 using the encryption function.
b) Add two encrypted integers, the encryption of 5 and 12.
c) Multiply an encrypted integer, the encryption of 3, by an encrypted integer, the encryption of
7.
Solution 4.
a) To encrypt the integer 9, we first need to choose a public key (N, q, h)for the encryption
scheme. Let q= 31 and h= 6. Then the encryption function is defined as follows:
Encrypt(m) = mh + 2rmod N
where m= 9, and ris a random integer modulo N. Let’s choose r= 7. Thus, the encryption
of 9 is:
Encrypt(9) = 9∗6+2∗7 mod 29 = 54 + 14 mod 29 = 68 mod 29 = 10
Therefore, the encryption of 9 is 10.
b) To add two encrypted integers, we simply add them modulo N. Let’s consider the encryption
of 5 and 12:
Encrypt(5) = 5∗6+2∗7 mod 29 = 32 mod 29 = 3
Encrypt(12) = 12 ∗6+2∗7 mod 29 = 74 mod 29 = 16
Adding the two encrypted integers:
Encrypt(5) +Encrypt(12) = 3 + 16 mod 29 = 19
Therefore, the sum of the encrypted integers 5 and 12 is 19.
c) For multiplication of two encrypted integers, we multiply the two ciphertexts modulo N. Let’s
multiply the encryption of 3 and 7:
Encrypt(3) = 3∗6+2∗7 mod 29 = 20
Encrypt(7) = 7∗6+2∗7 mod 29 = 49 mod 29 = 20
Multiplying the two encrypted integers:
Encrypt(3) ·Encrypt(7) = 20 ∗20 mod 29 = 400 mod 29 = 16
Therefore, the product of the encrypted integers 3 and 7 is 16.
6 Cryptographic Applications of Homomorphic Encryption
Problem: Suppose we have two ciphertexts c1and c2encrypted under the same homomorphic
encryption scheme, and we want to compute the product of the plaintexts they represent. Let the
decryption function be Dec(·).
Given that Dec(c1) = 7 and Dec(c2) = 4, and we know that the homomorphic encryption
scheme supports homomorphic multiplication, calculate the decryption of the product of the plain-
texts represented by c1and c2, i.e., find Dec(c1×c2).
Solution: Since the homomorphic encryption scheme supports homomorphic multiplication,
we can calculate the product of the plaintexts without decrypting c1and c2individually.
Let’s assume that the product of the plaintexts represented by c1and c2is denoted as m1×m2.
Since Dec(c1) = 7 and Dec(c2)=4, we have m1= 7 and m2= 4.
Now, to find Dec(c1×c2), we calculate the product of the plaintexts represented by c1and c2,
which is m1×m2= 7 ×4 = 28.
Therefore, Dec(c1×c2) = 28.
7 6. SCALABILITY PROBLEMS IN HOMOMORPHIC ENCRYPTION
Problem 6. Consider a homomorphic encryption scheme where the ciphertext size grows
linearly with the plaintext size. Suppose we have a plaintext vector p= [3,1,4,1,5] encrypted
using this scheme and a homomorphic operation that requires adding two ciphertexts together. If
the size of each ciphertext is 4 bytes, what is the total ciphertext size required for this operation?
Solution 6. a) Given that the plaintext vector p= [3,1,4,1,5] is encrypted using a homomorphic
encryption scheme with a ciphertext size of 4 bytes each, the total ciphertext size required for a
homomorphic addition operation can be calculated as follows:
b) Since the ciphertext size grows linearly with the plaintext size, the total ciphertext size re-
quired for encrypting the plaintext vector pis determined by multiplying the number of plaintext
elements by the size of each ciphertext. For a plaintext vector of length n, the total ciphertext size
is given by:
Total ciphertext size =n×Size of each ciphertext
In this case, n= 5 (as there are 5 elements in the plaintext vector) and the size of each ciphertext
is 4 bytes. Substituting these values into the formula:
Total ciphertext size = 5 ×4 = 20 bytes
Thus, the total ciphertext size required for a homomorphic addition operation on the given plain-
text vector using a 4-byte ciphertext scheme would be 20 bytes.
8 Cryptographic Applications of Homomorphic Encryption
Problem: Consider a fully homomorphic encryption scheme where the public key is (n= 5, q =
7) and the secret key is (a= 3).
a) Encrypt the plaintext message m= 4.
b) Perform a homomorphic addition on the ciphertexts corresponding to m1= 4 and m2= 3.
c) Perform a homomorphic multiplication on the ciphertext corresponding to m3= 2.
Solution:
a) To encrypt the plaintext message m= 4, we use the encryption function:
c= (a·r+ 2m) mod q
where ris a random integer. Plugging in m= 4,a= 3,q= 7, and choosing r= 2 for
demonstration purposes:
c= (3 ·2+2·4) mod 7 = (6 + 8) mod 7 = 14 mod 7 = 0
Therefore, the encrypted ciphertext for m= 4 is c= 0.
b) For homomorphic addition on two ciphertexts c1and c2corresponding to m1= 4 and m2= 3,
we can simply add the ciphertexts together modulo q:
cadd = (c1+c2) mod q
Given c1= 0 and c2= (3 ·2+2·3) mod 7 = 12 mod 7 = 5, we have:
cadd = (0 + 5) mod 7 = 5
Therefore, the resulting ciphertext after homomorphic addition is cadd = 5.
c) For homomorphic multiplication on the ciphertext corresponding to m3= 2, we perform the
multiplication modulo q:
cmul = (c·ma
3) mod q
Given c= 0 and m3= 2, we have:
cmul = (0 ·23) mod 7 = 0
Therefore, the resulting ciphertext after homomorphic multiplication is cmul = 0.
9 8. ERROR RATES IN HOMOMORPHIC ENCRYPTION
Problem 8. In a homomorphic encryption scheme, the probability of an error occurring during
the encryption process is 0.05. If a computation involves 20 homomorphic operations, what is the
probability that at least one error occurs during the computation?
Solution 8. Let’s denote the probability of an error occurring during a single homomorphic
operation as p= 0.05. The probability of no error occurring during a single operation is 1−p= 0.95.
The probability that at least one error occurs during the 20 computations can be calculated
using the complement rule (the probability of the event happening is 1 minus the probability of the
event not happening).
The probability of no error occurring during all 20 computations is (0.95)20.
Therefore, the probability of at least one error occurring is:
P(at least one error) = 1 −P(no error in 20 computations)
= 1 −(0.95)20
≈1−0.358485
≈0.641515 (approximately)
So, the probability that at least one error occurs during the computation involving 20 homomor-
phic operations is approximately 0.641515, or 64.15
10 9. KEY MANAGEMENT CHALLENGES IN HOMOMORPHIC ENCRYPTION
Problem 9. Consider a homomorphic encryption scheme where the public key is (n, e)and the
private key is (n, d), where n= 187,e= 7, and d= 23. Given a plaintext message m= 42, encrypt
the message using the public key and then decrypt the ciphertext using the private key.
Solution 9. a) To encrypt the message m= 42 using the public key (n, e), we compute the
ciphertext cusing the encryption function: c≡me(mod n).
Substitute m= 42,e= 7, and n= 187 into the encryption function:
c≡427(mod 187)
Calculating 427(mod 187):
427= 1406408618242
1406408618242 ≡29 (mod 187)
Therefore, the ciphertext cis 29.
b) To decrypt the ciphertext c= 29 using the private key (n, d), we compute the decrypted
message musing the decryption function: m≡cd(mod n).
Substitute c= 29,d= 23, and n= 187 into the decryption function:
m≡2923 (mod 187)
Calculating 2923 (mod 187):
2923 = 49298393010889
49298393010889 ≡42 (mod 187)
Therefore, the decrypted message mis 42, which matches the original plaintext message.
11 10. RELIABILITY CONCERNS IN HOMOMORPHIC ENCRYPTION
Problem 10. Consider a homomorphic encryption scheme where the key generation process
has a 5% chance of generating an incorrect key. Suppose a ciphertext is encrypted using such an
incorrect key.
a) What is the effect on the decryption process if the key is incorrect?
b) Calculate the probability that at least one out of five ciphertexts is decrypted incorrectly due
to a wrong key.
Solution 10.
a) If a ciphertext is encrypted using an incorrect key in a homomorphic encryption scheme,
the decryption process will result in an incorrect plaintext. This is because the decryption process
relies on the correctness of the key to properly recover the original plaintext from the ciphertext.
b) In this case, the probability of a key being incorrect is 5%, so the probability of a key being
correct is 95%, or 0.95. Since there are five ciphertexts, the probability of at least one being
decrypted incorrectly is equal to 1 minus the probability that all five are decrypted correctly.
Let pbe the probability that a ciphertext is decrypted correctly using the correct key. Therefore,
the probability that a ciphertext is decrypted incorrectly using the incorrect key is 1−p.
The probability that all five ciphertexts are decrypted correctly is p5, and the probability that at
least one is decrypted incorrectly is 1−p5.
Substitute p= 0.95 into the formula:
Probability of at least one incorrect decryption = 1 −(0.95)5
= 1 −0.77378
= 0.22622
Therefore, the probability that at least one out of five ciphertexts is decrypted incorrectly due to
a wrong key is approximately 0.22622 (or 22.622%).
12 11. TRUSTWORTHINESS OF HOMOMORPHIC ENCRYPTION
Problem 11. Consider a homomorphic encryption scheme where the encryption function E
and the decryption function Dare defined as follows:
E(x) = x2mod 17
D(y) = √ymod 17
Suppose we want to perform homomorphic addition and multiplication on two plaintext values.
Specifically, given the plaintext values m1= 4 and m2= 11, find the encryption of the sum m1+m2
and the encryption of the product m1×m2using the above encryption scheme. Also, decrypt the
results to obtain the plaintext values.
Solution 11.
a) To find the encryption of the sum m1+m2, we first calculate the sum modulo 17:
m1+m2= 4 + 11 = 15
Next, we calculate the encryption using the encryption function E:
E(15) = 152mod 17 = 225 mod 17 = 4
Therefore, the encryption of the sum m1+m2is 4.
b) To find the encryption of the product m1×m2, we first calculate the product modulo 17:
m1×m2= 4 ×11 = 44
Next, we calculate the encryption using the encryption function E:
E(44) = 442mod 17 = 1936 mod 17 = 16
Therefore, the encryption of the product m1×m2is 16.
c) To decrypt the results, we use the decryption function D:
For the encrypted sum 4:
D(4) = √4 mod 17 = 2
Thus, the decrypted plaintext value for the sum is 2.
For the encrypted product 16:
D(16) = √16 mod 17 = 4
Therefore, the decrypted plaintext value for the product is 4.
13 12. COMPLEXITY IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 12. Consider a homomorphic encryption scheme where the encryption function is
defined as E(m) = m2mod 13.
a) Encrypt the message m= 5.
b) Perform the homomorphic addition of two ciphertexts encrypted with the values m1= 3 and
m2= 4.
c) Decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13.
Solution 12.
a) We are given the encryption function E(m) = m2mod 13. To encrypt the message m= 5,
we substitute m= 5 into the encryption function:
E(5) = 52mod 13 = 25 mod 13 = 12.
Therefore, the encrypted ciphertext for the message m= 5 is 12.
b) To perform homomorphic addition, we calculate the sum of the ciphertexts created by en-
crypting m1= 3 and m2= 4:
E(3) = 32mod 13 = 9 mod 13 = 9
E(4) = 42mod 13 = 16 mod 13 = 3
Now, we add the ciphertexts: 9 + 3 = 12.
Therefore, the homomorphically added ciphertext is 12.
c) To decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13, we substitute c= 12 into the decryption function:
D(12) = √12 mod 13 ≈3.4641 mod 13 ≈3
Therefore, the decrypted message corresponding to the ciphertext 12 is 3.
14 13. PRIVACY RISKS OF HOMOMORPHIC ENCRYPTION
Problem 13. Consider a scenario where a company wants to use homomorphic encryption to
compute the sum of salaries of its employees without decrypting the individual salaries to ensure
privacy. The encryption scheme being used is a fully homomorphic encryption scheme that sup-
ports addition and multiplication operations. The company has encrypted the salaries using the
homomorphic encryption scheme, with each salary encoded as an integer.
The encrypted salaries are as follows: e1= 24,e2= 37,e3= 19, and e4= 42, where each eiis
the encrypted salary of employee i.
a) Compute the encrypted sum of the salaries, Enc(24 + 37 + 19 + 42).
b) The company also wants to compute the encrypted product of the salaries. Find Enc(24 ×
37 ×19 ×42).
c) If the company decrypts the sum of the encrypted salaries, will it reveal any information about
the individual salaries? Justify your answer.
Solution 13.
a) To compute the encrypted sum of the salaries, we can directly add the encrypted salaries:
Enc(24 + 37 + 19 + 42) = e1+e2+e3+e4= 24 + 37 + 19 + 42 = 122.
Therefore, the encrypted sum of the salaries is Enc(24 + 37 + 19 + 42) = 122.
b) To compute the encrypted product of the salaries, we can multiply the encrypted salaries:
Enc(24 ×37 ×19 ×42) = e1×e2×e3×e4= 24 ×37 ×19 ×42 = 387216.
Therefore, the encrypted product of the salaries is Enc(24 ×37 ×19 ×42) = 387216.
c) Homomorphic encryption provides the ability to perform computations on encrypted data
without decrypting it. When the company decrypts only the sum of the encrypted salaries, it will
not reveal any information about the individual salaries. This is because the encryption scheme
used is secure and ensures that the individual encrypted values remain confidential even after the
computation.
15 14. HOMOMORPHIC ENCRYPTION IN REAL-WORLD APPLICATIONS
Problem 14. Consider a scenario where a data processing company wants to outsource the
computation of the average salary of its employees to a cloud server using homomorphic encryp-
tion. The employees’ salaries are encrypted using a partially homomorphic encryption scheme that
supports addition and multiplication operations. Each employee’s salary is encrypted as follows:
E(s) = s2mod 11, where sis the plaintext salary.
a) If the company has four employees with salaries s1= 3,s2= 5,s3= 4, and s4= 6, calculate
the encrypted values for each of their salaries.
b) Compute the sum of the encrypted salaries.
c) Using homomorphic properties, decrypt the result to obtain the average salary of the em-
ployees.
Solution 14. a) To calculate the encrypted values for each employee’s salary:
Given E(s) = s2mod 11,
For s1= 3:E(3) = 32mod 11 = 9 mod 11 = 9
For s2= 5:E(5) = 52mod 11 = 25 mod 11 = 3
For s3= 4:E(4) = 42mod 11 = 16 mod 11 = 5
For s4= 6:E(6) = 62mod 11 = 36 mod 11 = 3
Therefore, the encrypted values for the employees’ salaries are: 9, 3, 5, 3.
b) To compute the sum of the encrypted salaries:
Sum of encrypted salaries = 9 + 3 + 5 + 3 = 20.
c) Since the encryption scheme supports multiplication and addition homomorphically, we can
decrypt the result of the sum by computing the inverse operation of squaring modulo 11, which is
finding the square root modulo 11.
20 ≡x2mod 11
Calculating the square root modulo 11:
x≡ ±√20 mod 11
x≡ ±4 mod 11
Hence, the possible decrypted values are 4 and 7. Since 4 is the correct average salary of the
employees, the decrypted average salary is 4.
16 Cryptographic Applications of Homomorphic Encryption
Problem: Using a fully homomorphic encryption scheme, Alice wants to perform the following
computation: E(m1)·E(m2) + E(m3)−E(m4), where Edenotes the encryption function and
m1= 5,m2= 3,m3= 7, and m4= 2. The encryption function transforms each message to their
encrypted form using the public key.
Assume the following encrypted values are obtained: E(m1) = 10,E(m2) = 8,E(m3) = 15,
and E(m4) = 5. Alice wishes to calculate the result of the above computation without decrypting
any values.
Solution:
Given: E(m1) = 10,E(m2)=8,E(m3) = 15, and E(m4) = 5.
a) Calculate the result of the computation E(m1)·E(m2).
b) Calculate the result of the computation E(m1)·E(m2) + E(m3).
c) Calculate the final result of the original computation.
Solution:
a) E(m1)·E(m2) = 10 ·8 = 80.
b) E(m1)·E(m2) + E(m3) = 80 + 15 = 95.
c) Finally, the original computation E(m1)·E(m2) + E(m3)−E(m4)becomes 95 −5 = 90.
Therefore, the final result of the computation without decrypting any values is 90.
17 16. USABILITY CHALLENGES OF HOMOMORPHIC ENCRYPTION
Problem 16. Consider a homomorphic encryption scheme where the encryption function is
E(x) = x2mod 13. Encrypt the message m= 3 using this scheme.
Solution 16. To encrypt the message m= 3, we substitute x= 3 into the encryption function
E(x) = x2mod 13.
Therefore, the encrypted message is:
E(3) = 32mod 13 = 9 mod 13 = 9
So, the encrypted message for m= 3 is 9.
18 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to securely outsource a computation to a cloud server using fully homo-
morphic encryption. She encrypts her input data xusing the homomorphic encryption scheme, and
sends it to the server. The server performs some computation on the encrypted data and returns
the result yto Alice. If the encryption scheme is fully homomorphic with the following properties:
- Addition: E(a) + E(b) = E(a+b)- Multiplication: E(a)×E(b) = E(a×b)
and the server computes E(3x+ 2), what will be the decrypted result that Alice receives?
Solution 1. Given that E(3x+2) = E(3)×E(x)+E(2), we expand this using the homomorphic
properties:
=E(3) ×E(x) + E(2)
=E(3) ×E(x) + E(2 ×1)
=E(3) ×E(x) + E(2) = E(3) ×E(x+ 1)
=E(3) ×E(x+x) + E(2) = E(3) ×E(2x) + E(2)
=E(3) ×E(x×2) + E(2) = E(6) ×E(x) + E(2)
=E(6) ×E(x) + E(2) = E(6x) + E(2)
Therefore, the decrypted result that Alice receives is 6x+ 2.
Problem 2. Bob wants to perform the computation 4x2−2x+ 5 on his encrypted data using
a partially homomorphic encryption scheme that supports addition but not multiplication. If he
encrypts xas E(x) = x2+3x−1, calculate the result that Bob will receive after the server performs
the computation using this homomorphic property.
Solution 2. Given that E(4x2−2x+ 5) = E(4x2) + E(−2x) + E(5), we use the homomorphic
property of addition:
=E(4) ×E(x2) + E(−2) ×E(x) + E(5)
=E(4) ×(x2+ 3x−1) + E(−2) ×x2+E(5)
=E(4x2+ 12x−4) + E(−2x2) + E(5)
=E(2x2+ 12x+ 1)
Therefore, the result that Bob will receive after the server performs the computation is 2x2+
12x+ 1.
19 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to send sensitive medical data to Bob using homomorphic encryp-
tion. She encrypts the data with a homomorphic scheme that supports addition and multiplication
operations. The plaintext data is x= 7, and the encryption function is defined as:
E(x) = x+rmod q
where ris a random number from the range [0,10] and q= 13. Calculate the encryption of xand
determine what operations Bob can perform on the encrypted data.
Solution 1. Given: x= 7,q= 13,r∈[0,10]
First, we randomly select a value of rfrom the range [0,10]. Let’s choose r= 3.
The encryption of xis then:
E(x) = x+rmod q= 7 + 3 mod 13 = 10
Therefore, the encryption of xis 10. Bob can now perform additions and multiplications on the
encrypted data without decrypting it.
20 19. HOMOMORPHIC ENCRYPTION IN FINANCIAL TRANSACTIONS
Problem 19. A bank wants to use homomorphic encryption to securely calculate the total
balance of its customers without knowing the individual balances. The bank assigns encrypted
values to represent the balances of three customers as follows: Customer A’s balance is encrypted
as 10, Customer B’s balance is encrypted as 15, and Customer C’s balance is encrypted as 8.
The bank uses the homomorphic property to perform secure calculations without decrypting the
balances.
a) If the bank wants to calculate the sum of the balances of Customer A and Customer B using
homomorphic addition, what encrypted value represents this sum?
b) If the bank wants to calculate the product of the balances of Customer A and Customer C
using homomorphic multiplication, what encrypted value represents this product?
c) Using the result from part a, if the bank also wants to subtract the balance of Customer B from
the sum of Customer A and B, what encrypted value represents this subtraction using homomorphic
subtraction?
Solution 19.
a) To calculate the sum of the balances of Customer A and Customer B using homomorphic
addition, we simply add their encrypted values:
Encrypted sum = Encrypted value of A + Encrypted value of B = 10 + 15 = 25.
Therefore, the encrypted value representing the sum of the balances of Customer A and Cus-
tomer B is 25.
b) To calculate the product of the balances of Customer A and Customer C using homomorphic
multiplication, we multiply their encrypted values:
Encrypted product = Encrypted value of A ×Encrypted value of C = 10 ×8 = 80.
Therefore, the encrypted value representing the product of the balances of Customer A and
Customer C is 80.
c) Using the result from part a, we have the encrypted value representing the sum of the bal-
ances of Customer A and B as 25. To subtract the balance of Customer B (15) from this sum using
homomorphic subtraction, we perform:
Encrypted subtraction = Encrypted sum - Encrypted value of B = 25 −15 = 10.
Therefore, the encrypted value representing the subtraction of the balance of Customer B from
the sum of Customer A and B is 10.
21 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where Alice wants to perform a homomorphic encryption
operation using the Paillier cryptosystem. She has two plaintext values m1= 7 and m2= 5, and
random parameters p= 17,q= 11,n=p·q,g=n+ 1. Assume that the public key is (n, g).
a) Encrypt both plaintext values m1and m2using the Paillier cryptosystem. b) Compute the
homomorphic sum of the ciphertexts corresponding to m1and m2. c) Decrypt the result of the
homomorphic sum to obtain the plaintext value.
Solution 1. a) To encrypt a plaintext value min the Paillier cryptosystem, we use the encryption
function E(m) = gm·rnmod n2, where ris a random number.
For m1= 7:E(7) = g7·rnmod n2= (287·r187 mod 1872)
For m2= 5:E(5) = g5·rnmod n2= (285·r187 mod 1872)
b) To compute the homomorphic sum of two ciphertexts in the Paillier cryptosystem, we multiply
the ciphertexts together. Therefore, the homomorphic sum of m1and m2would be: E(m1)×
E(m2) = (287·r187 mod 1872)×(285·r187 mod 1872)
c) To decrypt the result of the homomorphic sum, we use the decryption function D(c) = L(cλ
mod n2)·µmod n, where L(x) = x−1
n,λ=lcm(p−1, q −1), and µ=L(gλmod n2)−1mod n.
First, we compute the homomorphic sum: E(m1)×E(m2) = [step to multiply the ciphertexts]
Then, we decrypt the result as follows: D(E(m1)×E(m2)) = [steps to decrypt and obtain the
plaintext value]
22 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where a data scientist wants to securely compute the average
of a list of numbers using homomorphic encryption. The data scientist encrypts the numbers using
a homomorphic encryption scheme and performs the necessary computation. If the list of numbers
to be averaged is encrypted as follows:
- Number 1: E(5) = 15 - Number 2: E(8) = 26 - Number 3: E(3) = 13 - Number 4: E(10) = 34
Determine the encrypted result after computing the average and decrypt it to obtain the final
result.
Solution 1.
a) To compute the average homomorphically, we need to sum all the encrypted numbers and
divide the result by the total count of numbers.
The sum of the encrypted numbers:
E(5) + E(8) + E(3) + E(10) = 15 + 26 + 13 + 34 = 88
b) Now, we need to divide the encrypted sum by the total count of numbers, which is 4:
E(average) = 88
4= 22
Thus, the encrypted result after computing the average is 22.
c) To obtain the final result, we need to decrypt the encrypted average using the homomorphic
encryption scheme’s decryption function.
Decryption:
D(22) = 22
2= 11
Therefore, the final result of averaging the list of numbers is 11.
23 22. HOMOMORPHIC ENCRYPTION IN DATA ANALYTICS
Problem 22. Consider a scenario where a data scientist wants to perform statistical analysis on
encrypted data using homomorphic encryption. The data scientist has two integer values encrypted
using a homomorphic encryption scheme: a=Enc(3) and b=Enc(5).
a) Compute the encrypted value of a+b.
b) Compute the encrypted value of 2a−b.
Solution 22.
a) To compute the encrypted value of a+b, we need to use the properties of homomorphic
encryption. In a partially homomorphic encryption scheme, we can perform addition on encrypted
values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of a+bis Enc(3) + Enc(5) = Enc(3 + 5) = Enc(8).
Therefore, the encrypted value of a+bis Enc(8).
b) To compute the encrypted value of 2a−b, we again utilize the properties of homomorphic
encryption. We can perform scalar multiplication and subtraction on encrypted values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of 2a−bis 2×Enc(3) −Enc(5) = Enc(2 ×3−5) = Enc(1).
Therefore, the encrypted value of 2a−bis Enc(1).
24 23. HOMOMORPHIC ENCRYPTION IN MACHINE LEARNING
Problem 23. Consider a machine learning model that uses homomorphic encryption for privacy-
preserving computations. The model receives encrypted features X={x1, x2, x3}and encrypted
labels Y={y1, y2, y3}. After performing the necessary computations, the encrypted predictions
are Z={z1, z2, z3}. Assume the computations follow the equation: zi=w×xi+b, where wis the
weight, bis the bias, and xi,yi, and ziare encrypted values.
Given: x1= 5,y1= 7,z1= 42 (all values encrypted) x2= 3,y2= 5, and z2= 24 (all values
encrypted)
a) Calculate the weight w.
b) Calculate the bias b.
Solution 23.
a) To find the weight w, we can use the formula zi=w×xi+b.
For i= 1:
z1=w×x1+b
42 = w×5 + b
For i= 2:
z2=w×x2+b
24 = w×3 + b
Solving these two equations simultaneously, we get:
w=z1−z2
x1−x2
=42 −24
5−3=18
2= 9
Therefore, the weight w= 9.
b) To find the bias b, we can substitue w= 9 into one of the equations. Let’s use the first
equation when i= 1:
42 = 9 ×5 + b
42 = 45 + b
b= 42 −45 = −3
Therefore, the bias b=−3.
25 Cryptographic Applications of Homomorphic Encryption
Problem 1. In an e-voting system that uses homomorphic encryption, the votes for candidates
A,B, and Care encrypted as follows: a= 6,b= 8, and c= 4, respectively. The encryption scheme
uses additive homomorphic properties. The result of multiplying the ciphertexts for candidates A
and Bis calculated as a×b= 30. Find out the encrypted vote for candidate C.
Solution 1. Given that the encryption scheme is additive homomorphic, we can calculate the
encrypted vote for candidate Cusing the properties of homomorphic encryption.
We know that a×brepresents the product of ciphertexts for candidates Aand B. Thus, a×b=
30.
Now, to find the encrypted vote for candidate C, we can utilize the additive homomorphic prop-
erty, which states that multiplying ciphertexts corresponds to adding plaintexts. Therefore, the
encrypted vote for candidate Cwill be:
a×b+c= 30 + c
Given a= 6,b= 8, and c= 4, substituting these values:
30 + 4 = 34
Therefore, the encrypted vote for candidate Cis 34.
26 25. HOMOMORPHIC ENCRYPTION IN SECURE COMMUNICATION PROTOCOLS
Problem 25. Alice wants to perform a secure computation on encrypted data using a homo-
morphic encryption scheme. She has two encrypted values c1and c2, where c1=Encpk(7) and
c2=Encpk(5), encrypted under a public key pk. She wants to calculate the sum and product of
the decrypted values without revealing the encryption key. Assume the homomorphic encryption
scheme supports both addition and multiplication operations homomorphically.
Solution 25. a) To calculate the sum of the decrypted values, Alice can perform homomorphic
addition on the encrypted values c1and c2. Let csum =c1⊕c2.
The decryption of csum will give the sum of the decrypted values:
Decsk(csum) = Decsk(c1⊕c2)
=Decsk(Encpk(7) ⊕Encpk (5))
=Decsk(Encpk(7 + 5))
=Decsk(Encpk(12))
= 12
Therefore, the sum of the decrypted values is 12.
b) To calculate the product of the decrypted values, Alice can perform homomorphic multipli-
cation on the encrypted values c1and c2. Let cprod =c1⊗c2.
The decryption of cprod will give the product of the decrypted values:
Decsk(cprod) = Decsk(c1⊗c2)
=Decsk(Encpk(7) ⊗Encpk (5))
=Decsk(Encpk(7 ×5))
=Decsk(Encpk(35))
= 35
Therefore, the product of the decrypted values is 35.
3 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to perform a homomorphic encryption on a message m= 7 using a fully
homomorphic encryption scheme. The public key for this scheme is n= 13 and the encryption
function is defined as E(x) = x2mod n. Calculate the encrypted message.
Solution 1. To encrypt the message using the homomorphic encryption scheme, we need to
compute E(m):
E(m) = E(7) = 72mod 13 = 49 mod 13 = 10
Therefore, the encrypted message is 10.
4 Cryptographic Applications of Homomorphic Encryption
Problem 2. Bob wants to perform a homomorphic addition on two encrypted messages. The
encrypted messages are c1= 8 and c2= 12, and the public key for the homomorphic encryption
scheme is n= 17. If the encryption function is defined as E(x) = x2mod n, calculate the result
of adding the two encrypted messages together.
Solution 2. To perform homomorphic addition on the encrypted messages, we first need to
decrypt the messages, add them together, and then re-encrypt the sum:
Step 1: Decrypt the messages
C1=c
n+1
4
1mod n= 85mod 17 = 8
C2=c
n+1
4
2mod n= 125mod 17 = 12
Step 2: Add the decrypted messages
D=C1+C2= 8 + 12 = 20
Step 3: Re-encrypt the sum
E(D) = D2mod 17 = 202mod 17 = 400 mod 17 = 11
Therefore, the result of adding the two encrypted messages together is 11.
5 4. LIMITATIONS OF HOMOMORPHIC ENCRYPTION
Problem 4. Consider a fully homomorphic encryption scheme where the ciphertext space is
integers modulo N= 29. Alice wants to perform the following computations:
a) Encrypt the integer 9 using the encryption function.
b) Add two encrypted integers, the encryption of 5 and 12.
c) Multiply an encrypted integer, the encryption of 3, by an encrypted integer, the encryption of
7.
Solution 4.
a) To encrypt the integer 9, we first need to choose a public key (N, q, h)for the encryption
scheme. Let q= 31 and h= 6. Then the encryption function is defined as follows:
Encrypt(m) = mh + 2rmod N
where m= 9, and ris a random integer modulo N. Let’s choose r= 7. Thus, the encryption
of 9 is:
Encrypt(9) = 9∗6+2∗7 mod 29 = 54 + 14 mod 29 = 68 mod 29 = 10
Therefore, the encryption of 9 is 10.
b) To add two encrypted integers, we simply add them modulo N. Let’s consider the encryption
of 5 and 12:
Encrypt(5) = 5∗6+2∗7 mod 29 = 32 mod 29 = 3
Encrypt(12) = 12 ∗6+2∗7 mod 29 = 74 mod 29 = 16
Adding the two encrypted integers:
Encrypt(5) +Encrypt(12) = 3 + 16 mod 29 = 19
Therefore, the sum of the encrypted integers 5 and 12 is 19.
c) For multiplication of two encrypted integers, we multiply the two ciphertexts modulo N. Let’s
multiply the encryption of 3 and 7:
Encrypt(3) = 3∗6+2∗7 mod 29 = 20
Encrypt(7) = 7∗6+2∗7 mod 29 = 49 mod 29 = 20
Multiplying the two encrypted integers:
Encrypt(3) ·Encrypt(7) = 20 ∗20 mod 29 = 400 mod 29 = 16
Therefore, the product of the encrypted integers 3 and 7 is 16.
6 Cryptographic Applications of Homomorphic Encryption
Problem: Suppose we have two ciphertexts c1and c2encrypted under the same homomorphic
encryption scheme, and we want to compute the product of the plaintexts they represent. Let the
decryption function be Dec(·).
Given that Dec(c1) = 7 and Dec(c2) = 4, and we know that the homomorphic encryption
scheme supports homomorphic multiplication, calculate the decryption of the product of the plain-
texts represented by c1and c2, i.e., find Dec(c1×c2).
Solution: Since the homomorphic encryption scheme supports homomorphic multiplication,
we can calculate the product of the plaintexts without decrypting c1and c2individually.
Let’s assume that the product of the plaintexts represented by c1and c2is denoted as m1×m2.
Since Dec(c1) = 7 and Dec(c2)=4, we have m1= 7 and m2= 4.
Now, to find Dec(c1×c2), we calculate the product of the plaintexts represented by c1and c2,
which is m1×m2= 7 ×4 = 28.
Therefore, Dec(c1×c2) = 28.
7 6. SCALABILITY PROBLEMS IN HOMOMORPHIC ENCRYPTION
Problem 6. Consider a homomorphic encryption scheme where the ciphertext size grows
linearly with the plaintext size. Suppose we have a plaintext vector p= [3,1,4,1,5] encrypted
using this scheme and a homomorphic operation that requires adding two ciphertexts together. If
the size of each ciphertext is 4 bytes, what is the total ciphertext size required for this operation?
Solution 6. a) Given that the plaintext vector p= [3,1,4,1,5] is encrypted using a homomorphic
encryption scheme with a ciphertext size of 4 bytes each, the total ciphertext size required for a
homomorphic addition operation can be calculated as follows:
b) Since the ciphertext size grows linearly with the plaintext size, the total ciphertext size re-
quired for encrypting the plaintext vector pis determined by multiplying the number of plaintext
elements by the size of each ciphertext. For a plaintext vector of length n, the total ciphertext size
is given by:
Total ciphertext size =n×Size of each ciphertext
In this case, n= 5 (as there are 5 elements in the plaintext vector) and the size of each ciphertext
is 4 bytes. Substituting these values into the formula:
Total ciphertext size = 5 ×4 = 20 bytes
Thus, the total ciphertext size required for a homomorphic addition operation on the given plain-
text vector using a 4-byte ciphertext scheme would be 20 bytes.
8 Cryptographic Applications of Homomorphic Encryption
Problem: Consider a fully homomorphic encryption scheme where the public key is (n= 5, q =
7) and the secret key is (a= 3).
a) Encrypt the plaintext message m= 4.
b) Perform a homomorphic addition on the ciphertexts corresponding to m1= 4 and m2= 3.
c) Perform a homomorphic multiplication on the ciphertext corresponding to m3= 2.
Solution:
a) To encrypt the plaintext message m= 4, we use the encryption function:
c= (a·r+ 2m) mod q
where ris a random integer. Plugging in m= 4,a= 3,q= 7, and choosing r= 2 for
demonstration purposes:
c= (3 ·2+2·4) mod 7 = (6 + 8) mod 7 = 14 mod 7 = 0
Therefore, the encrypted ciphertext for m= 4 is c= 0.
b) For homomorphic addition on two ciphertexts c1and c2corresponding to m1= 4 and m2= 3,
we can simply add the ciphertexts together modulo q:
cadd = (c1+c2) mod q
Given c1= 0 and c2= (3 ·2+2·3) mod 7 = 12 mod 7 = 5, we have:
cadd = (0 + 5) mod 7 = 5
Therefore, the resulting ciphertext after homomorphic addition is cadd = 5.
c) For homomorphic multiplication on the ciphertext corresponding to m3= 2, we perform the
multiplication modulo q:
cmul = (c·ma
3) mod q
Given c= 0 and m3= 2, we have:
cmul = (0 ·23) mod 7 = 0
Therefore, the resulting ciphertext after homomorphic multiplication is cmul = 0.
9 8. ERROR RATES IN HOMOMORPHIC ENCRYPTION
Problem 8. In a homomorphic encryption scheme, the probability of an error occurring during
the encryption process is 0.05. If a computation involves 20 homomorphic operations, what is the
probability that at least one error occurs during the computation?
Solution 8. Let’s denote the probability of an error occurring during a single homomorphic
operation as p= 0.05. The probability of no error occurring during a single operation is 1−p= 0.95.
The probability that at least one error occurs during the 20 computations can be calculated
using the complement rule (the probability of the event happening is 1 minus the probability of the
event not happening).
The probability of no error occurring during all 20 computations is (0.95)20.
Therefore, the probability of at least one error occurring is:
P(at least one error) = 1 −P(no error in 20 computations)
= 1 −(0.95)20
≈1−0.358485
≈0.641515 (approximately)
So, the probability that at least one error occurs during the computation involving 20 homomor-
phic operations is approximately 0.641515, or 64.15
10 9. KEY MANAGEMENT CHALLENGES IN HOMOMORPHIC ENCRYPTION
Problem 9. Consider a homomorphic encryption scheme where the public key is (n, e)and the
private key is (n, d), where n= 187,e= 7, and d= 23. Given a plaintext message m= 42, encrypt
the message using the public key and then decrypt the ciphertext using the private key.
Solution 9. a) To encrypt the message m= 42 using the public key (n, e), we compute the
ciphertext cusing the encryption function: c≡me(mod n).
Substitute m= 42,e= 7, and n= 187 into the encryption function:
c≡427(mod 187)
Calculating 427(mod 187):
427= 1406408618242
1406408618242 ≡29 (mod 187)
Therefore, the ciphertext cis 29.
b) To decrypt the ciphertext c= 29 using the private key (n, d), we compute the decrypted
message musing the decryption function: m≡cd(mod n).
Substitute c= 29,d= 23, and n= 187 into the decryption function:
m≡2923 (mod 187)
Calculating 2923 (mod 187):
2923 = 49298393010889
49298393010889 ≡42 (mod 187)
Therefore, the decrypted message mis 42, which matches the original plaintext message.
11 10. RELIABILITY CONCERNS IN HOMOMORPHIC ENCRYPTION
Problem 10. Consider a homomorphic encryption scheme where the key generation process
has a 5% chance of generating an incorrect key. Suppose a ciphertext is encrypted using such an
incorrect key.
a) What is the effect on the decryption process if the key is incorrect?
b) Calculate the probability that at least one out of five ciphertexts is decrypted incorrectly due
to a wrong key.
Solution 10.
a) If a ciphertext is encrypted using an incorrect key in a homomorphic encryption scheme,
the decryption process will result in an incorrect plaintext. This is because the decryption process
relies on the correctness of the key to properly recover the original plaintext from the ciphertext.
b) In this case, the probability of a key being incorrect is 5%, so the probability of a key being
correct is 95%, or 0.95. Since there are five ciphertexts, the probability of at least one being
decrypted incorrectly is equal to 1 minus the probability that all five are decrypted correctly.
Let pbe the probability that a ciphertext is decrypted correctly using the correct key. Therefore,
the probability that a ciphertext is decrypted incorrectly using the incorrect key is 1−p.
The probability that all five ciphertexts are decrypted correctly is p5, and the probability that at
least one is decrypted incorrectly is 1−p5.
Substitute p= 0.95 into the formula:
Probability of at least one incorrect decryption = 1 −(0.95)5
= 1 −0.77378
= 0.22622
Therefore, the probability that at least one out of five ciphertexts is decrypted incorrectly due to
a wrong key is approximately 0.22622 (or 22.622%).
12 11. TRUSTWORTHINESS OF HOMOMORPHIC ENCRYPTION
Problem 11. Consider a homomorphic encryption scheme where the encryption function E
and the decryption function Dare defined as follows:
E(x) = x2mod 17
D(y) = √ymod 17
Suppose we want to perform homomorphic addition and multiplication on two plaintext values.
Specifically, given the plaintext values m1= 4 and m2= 11, find the encryption of the sum m1+m2
and the encryption of the product m1×m2using the above encryption scheme. Also, decrypt the
results to obtain the plaintext values.
Solution 11.
a) To find the encryption of the sum m1+m2, we first calculate the sum modulo 17:
m1+m2= 4 + 11 = 15
Next, we calculate the encryption using the encryption function E:
E(15) = 152mod 17 = 225 mod 17 = 4
Therefore, the encryption of the sum m1+m2is 4.
b) To find the encryption of the product m1×m2, we first calculate the product modulo 17:
m1×m2= 4 ×11 = 44
Next, we calculate the encryption using the encryption function E:
E(44) = 442mod 17 = 1936 mod 17 = 16
Therefore, the encryption of the product m1×m2is 16.
c) To decrypt the results, we use the decryption function D:
For the encrypted sum 4:
D(4) = √4 mod 17 = 2
Thus, the decrypted plaintext value for the sum is 2.
For the encrypted product 16:
D(16) = √16 mod 17 = 4
Therefore, the decrypted plaintext value for the product is 4.
13 12. COMPLEXITY IN IMPLEMENTING HOMOMORPHIC ENCRYPTION
Problem 12. Consider a homomorphic encryption scheme where the encryption function is
defined as E(m) = m2mod 13.
a) Encrypt the message m= 5.
b) Perform the homomorphic addition of two ciphertexts encrypted with the values m1= 3 and
m2= 4.
c) Decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13.
Solution 12.
a) We are given the encryption function E(m) = m2mod 13. To encrypt the message m= 5,
we substitute m= 5 into the encryption function:
E(5) = 52mod 13 = 25 mod 13 = 12.
Therefore, the encrypted ciphertext for the message m= 5 is 12.
b) To perform homomorphic addition, we calculate the sum of the ciphertexts created by en-
crypting m1= 3 and m2= 4:
E(3) = 32mod 13 = 9 mod 13 = 9
E(4) = 42mod 13 = 16 mod 13 = 3
Now, we add the ciphertexts: 9 + 3 = 12.
Therefore, the homomorphically added ciphertext is 12.
c) To decrypt the resulting ciphertext from part (b) using the decryption function D(c) = √c
mod 13, we substitute c= 12 into the decryption function:
D(12) = √12 mod 13 ≈3.4641 mod 13 ≈3
Therefore, the decrypted message corresponding to the ciphertext 12 is 3.
14 13. PRIVACY RISKS OF HOMOMORPHIC ENCRYPTION
Problem 13. Consider a scenario where a company wants to use homomorphic encryption to
compute the sum of salaries of its employees without decrypting the individual salaries to ensure
privacy. The encryption scheme being used is a fully homomorphic encryption scheme that sup-
ports addition and multiplication operations. The company has encrypted the salaries using the
homomorphic encryption scheme, with each salary encoded as an integer.
The encrypted salaries are as follows: e1= 24,e2= 37,e3= 19, and e4= 42, where each eiis
the encrypted salary of employee i.
a) Compute the encrypted sum of the salaries, Enc(24 + 37 + 19 + 42).
b) The company also wants to compute the encrypted product of the salaries. Find Enc(24 ×
37 ×19 ×42).
c) If the company decrypts the sum of the encrypted salaries, will it reveal any information about
the individual salaries? Justify your answer.
Solution 13.
a) To compute the encrypted sum of the salaries, we can directly add the encrypted salaries:
Enc(24 + 37 + 19 + 42) = e1+e2+e3+e4= 24 + 37 + 19 + 42 = 122.
Therefore, the encrypted sum of the salaries is Enc(24 + 37 + 19 + 42) = 122.
b) To compute the encrypted product of the salaries, we can multiply the encrypted salaries:
Enc(24 ×37 ×19 ×42) = e1×e2×e3×e4= 24 ×37 ×19 ×42 = 387216.
Therefore, the encrypted product of the salaries is Enc(24 ×37 ×19 ×42) = 387216.
c) Homomorphic encryption provides the ability to perform computations on encrypted data
without decrypting it. When the company decrypts only the sum of the encrypted salaries, it will
not reveal any information about the individual salaries. This is because the encryption scheme
used is secure and ensures that the individual encrypted values remain confidential even after the
computation.
15 14. HOMOMORPHIC ENCRYPTION IN REAL-WORLD APPLICATIONS
Problem 14. Consider a scenario where a data processing company wants to outsource the
computation of the average salary of its employees to a cloud server using homomorphic encryp-
tion. The employees’ salaries are encrypted using a partially homomorphic encryption scheme that
supports addition and multiplication operations. Each employee’s salary is encrypted as follows:
E(s) = s2mod 11, where sis the plaintext salary.
a) If the company has four employees with salaries s1= 3,s2= 5,s3= 4, and s4= 6, calculate
the encrypted values for each of their salaries.
b) Compute the sum of the encrypted salaries.
c) Using homomorphic properties, decrypt the result to obtain the average salary of the em-
ployees.
Solution 14. a) To calculate the encrypted values for each employee’s salary:
Given E(s) = s2mod 11,
For s1= 3:E(3) = 32mod 11 = 9 mod 11 = 9
For s2= 5:E(5) = 52mod 11 = 25 mod 11 = 3
For s3= 4:E(4) = 42mod 11 = 16 mod 11 = 5
For s4= 6:E(6) = 62mod 11 = 36 mod 11 = 3
Therefore, the encrypted values for the employees’ salaries are: 9, 3, 5, 3.
b) To compute the sum of the encrypted salaries:
Sum of encrypted salaries = 9 + 3 + 5 + 3 = 20.
c) Since the encryption scheme supports multiplication and addition homomorphically, we can
decrypt the result of the sum by computing the inverse operation of squaring modulo 11, which is
finding the square root modulo 11.
20 ≡x2mod 11
Calculating the square root modulo 11:
x≡ ±√20 mod 11
x≡ ±4 mod 11
Hence, the possible decrypted values are 4 and 7. Since 4 is the correct average salary of the
employees, the decrypted average salary is 4.
16 Cryptographic Applications of Homomorphic Encryption
Problem: Using a fully homomorphic encryption scheme, Alice wants to perform the following
computation: E(m1)·E(m2) + E(m3)−E(m4), where Edenotes the encryption function and
m1= 5,m2= 3,m3= 7, and m4= 2. The encryption function transforms each message to their
encrypted form using the public key.
Assume the following encrypted values are obtained: E(m1) = 10,E(m2) = 8,E(m3) = 15,
and E(m4) = 5. Alice wishes to calculate the result of the above computation without decrypting
any values.
Solution:
Given: E(m1) = 10,E(m2)=8,E(m3) = 15, and E(m4) = 5.
a) Calculate the result of the computation E(m1)·E(m2).
b) Calculate the result of the computation E(m1)·E(m2) + E(m3).
c) Calculate the final result of the original computation.
Solution:
a) E(m1)·E(m2) = 10 ·8 = 80.
b) E(m1)·E(m2) + E(m3) = 80 + 15 = 95.
c) Finally, the original computation E(m1)·E(m2) + E(m3)−E(m4)becomes 95 −5 = 90.
Therefore, the final result of the computation without decrypting any values is 90.
17 16. USABILITY CHALLENGES OF HOMOMORPHIC ENCRYPTION
Problem 16. Consider a homomorphic encryption scheme where the encryption function is
E(x) = x2mod 13. Encrypt the message m= 3 using this scheme.
Solution 16. To encrypt the message m= 3, we substitute x= 3 into the encryption function
E(x) = x2mod 13.
Therefore, the encrypted message is:
E(3) = 32mod 13 = 9 mod 13 = 9
So, the encrypted message for m= 3 is 9.
18 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to securely outsource a computation to a cloud server using fully homo-
morphic encryption. She encrypts her input data xusing the homomorphic encryption scheme, and
sends it to the server. The server performs some computation on the encrypted data and returns
the result yto Alice. If the encryption scheme is fully homomorphic with the following properties:
- Addition: E(a) + E(b) = E(a+b)- Multiplication: E(a)×E(b) = E(a×b)
and the server computes E(3x+ 2), what will be the decrypted result that Alice receives?
Solution 1. Given that E(3x+2) = E(3)×E(x)+E(2), we expand this using the homomorphic
properties:
=E(3) ×E(x) + E(2)
=E(3) ×E(x) + E(2 ×1)
=E(3) ×E(x) + E(2) = E(3) ×E(x+ 1)
=E(3) ×E(x+x) + E(2) = E(3) ×E(2x) + E(2)
=E(3) ×E(x×2) + E(2) = E(6) ×E(x) + E(2)
=E(6) ×E(x) + E(2) = E(6x) + E(2)
Therefore, the decrypted result that Alice receives is 6x+ 2.
Problem 2. Bob wants to perform the computation 4x2−2x+ 5 on his encrypted data using
a partially homomorphic encryption scheme that supports addition but not multiplication. If he
encrypts xas E(x) = x2+3x−1, calculate the result that Bob will receive after the server performs
the computation using this homomorphic property.
Solution 2. Given that E(4x2−2x+ 5) = E(4x2) + E(−2x) + E(5), we use the homomorphic
property of addition:
=E(4) ×E(x2) + E(−2) ×E(x) + E(5)
=E(4) ×(x2+ 3x−1) + E(−2) ×x2+E(5)
=E(4x2+ 12x−4) + E(−2x2) + E(5)
=E(2x2+ 12x+ 1)
Therefore, the result that Bob will receive after the server performs the computation is 2x2+
12x+ 1.
19 Cryptographic Applications of Homomorphic Encryption
Problem 1. Alice wants to send sensitive medical data to Bob using homomorphic encryp-
tion. She encrypts the data with a homomorphic scheme that supports addition and multiplication
operations. The plaintext data is x= 7, and the encryption function is defined as:
E(x) = x+rmod q
where ris a random number from the range [0,10] and q= 13. Calculate the encryption of xand
determine what operations Bob can perform on the encrypted data.
Solution 1. Given: x= 7,q= 13,r∈[0,10]
First, we randomly select a value of rfrom the range [0,10]. Let’s choose r= 3.
The encryption of xis then:
E(x) = x+rmod q= 7 + 3 mod 13 = 10
Therefore, the encryption of xis 10. Bob can now perform additions and multiplications on the
encrypted data without decrypting it.
20 19. HOMOMORPHIC ENCRYPTION IN FINANCIAL TRANSACTIONS
Problem 19. A bank wants to use homomorphic encryption to securely calculate the total
balance of its customers without knowing the individual balances. The bank assigns encrypted
values to represent the balances of three customers as follows: Customer A’s balance is encrypted
as 10, Customer B’s balance is encrypted as 15, and Customer C’s balance is encrypted as 8.
The bank uses the homomorphic property to perform secure calculations without decrypting the
balances.
a) If the bank wants to calculate the sum of the balances of Customer A and Customer B using
homomorphic addition, what encrypted value represents this sum?
b) If the bank wants to calculate the product of the balances of Customer A and Customer C
using homomorphic multiplication, what encrypted value represents this product?
c) Using the result from part a, if the bank also wants to subtract the balance of Customer B from
the sum of Customer A and B, what encrypted value represents this subtraction using homomorphic
subtraction?
Solution 19.
a) To calculate the sum of the balances of Customer A and Customer B using homomorphic
addition, we simply add their encrypted values:
Encrypted sum = Encrypted value of A + Encrypted value of B = 10 + 15 = 25.
Therefore, the encrypted value representing the sum of the balances of Customer A and Cus-
tomer B is 25.
b) To calculate the product of the balances of Customer A and Customer C using homomorphic
multiplication, we multiply their encrypted values:
Encrypted product = Encrypted value of A ×Encrypted value of C = 10 ×8 = 80.
Therefore, the encrypted value representing the product of the balances of Customer A and
Customer C is 80.
c) Using the result from part a, we have the encrypted value representing the sum of the bal-
ances of Customer A and B as 25. To subtract the balance of Customer B (15) from this sum using
homomorphic subtraction, we perform:
Encrypted subtraction = Encrypted sum - Encrypted value of B = 25 −15 = 10.
Therefore, the encrypted value representing the subtraction of the balance of Customer B from
the sum of Customer A and B is 10.
21 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where Alice wants to perform a homomorphic encryption
operation using the Paillier cryptosystem. She has two plaintext values m1= 7 and m2= 5, and
random parameters p= 17,q= 11,n=p·q,g=n+ 1. Assume that the public key is (n, g).
a) Encrypt both plaintext values m1and m2using the Paillier cryptosystem. b) Compute the
homomorphic sum of the ciphertexts corresponding to m1and m2. c) Decrypt the result of the
homomorphic sum to obtain the plaintext value.
Solution 1. a) To encrypt a plaintext value min the Paillier cryptosystem, we use the encryption
function E(m) = gm·rnmod n2, where ris a random number.
For m1= 7:E(7) = g7·rnmod n2= (287·r187 mod 1872)
For m2= 5:E(5) = g5·rnmod n2= (285·r187 mod 1872)
b) To compute the homomorphic sum of two ciphertexts in the Paillier cryptosystem, we multiply
the ciphertexts together. Therefore, the homomorphic sum of m1and m2would be: E(m1)×
E(m2) = (287·r187 mod 1872)×(285·r187 mod 1872)
c) To decrypt the result of the homomorphic sum, we use the decryption function D(c) = L(cλ
mod n2)·µmod n, where L(x) = x−1
n,λ=lcm(p−1, q −1), and µ=L(gλmod n2)−1mod n.
First, we compute the homomorphic sum: E(m1)×E(m2) = [step to multiply the ciphertexts]
Then, we decrypt the result as follows: D(E(m1)×E(m2)) = [steps to decrypt and obtain the
plaintext value]
22 Cryptographic Applications of Homomorphic Encryption
Problem 1. Consider a scenario where a data scientist wants to securely compute the average
of a list of numbers using homomorphic encryption. The data scientist encrypts the numbers using
a homomorphic encryption scheme and performs the necessary computation. If the list of numbers
to be averaged is encrypted as follows:
- Number 1: E(5) = 15 - Number 2: E(8) = 26 - Number 3: E(3) = 13 - Number 4: E(10) = 34
Determine the encrypted result after computing the average and decrypt it to obtain the final
result.
Solution 1.
a) To compute the average homomorphically, we need to sum all the encrypted numbers and
divide the result by the total count of numbers.
The sum of the encrypted numbers:
E(5) + E(8) + E(3) + E(10) = 15 + 26 + 13 + 34 = 88
b) Now, we need to divide the encrypted sum by the total count of numbers, which is 4:
E(average) = 88
4= 22
Thus, the encrypted result after computing the average is 22.
c) To obtain the final result, we need to decrypt the encrypted average using the homomorphic
encryption scheme’s decryption function.
Decryption:
D(22) = 22
2= 11
Therefore, the final result of averaging the list of numbers is 11.
23 22. HOMOMORPHIC ENCRYPTION IN DATA ANALYTICS
Problem 22. Consider a scenario where a data scientist wants to perform statistical analysis on
encrypted data using homomorphic encryption. The data scientist has two integer values encrypted
using a homomorphic encryption scheme: a=Enc(3) and b=Enc(5).
a) Compute the encrypted value of a+b.
b) Compute the encrypted value of 2a−b.
Solution 22.
a) To compute the encrypted value of a+b, we need to use the properties of homomorphic
encryption. In a partially homomorphic encryption scheme, we can perform addition on encrypted
values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of a+bis Enc(3) + Enc(5) = Enc(3 + 5) = Enc(8).
Therefore, the encrypted value of a+bis Enc(8).
b) To compute the encrypted value of 2a−b, we again utilize the properties of homomorphic
encryption. We can perform scalar multiplication and subtraction on encrypted values.
Given: a=Enc(3) and b=Enc(5).
The encrypted value of 2a−bis 2×Enc(3) −Enc(5) = Enc(2 ×3−5) = Enc(1).
Therefore, the encrypted value of 2a−bis Enc(1).
24 23. HOMOMORPHIC ENCRYPTION IN MACHINE LEARNING
Problem 23. Consider a machine learning model that uses homomorphic encryption for privacy-
preserving computations. The model receives encrypted features X={x1, x2, x3}and encrypted
labels Y={y1, y2, y3}. After performing the necessary computations, the encrypted predictions
are Z={z1, z2, z3}. Assume the computations follow the equation: zi=w×xi+b, where wis the
weight, bis the bias, and xi,yi, and ziare encrypted values.
Given: x1= 5,y1= 7,z1= 42 (all values encrypted) x2= 3,y2= 5, and z2= 24 (all values
encrypted)
a) Calculate the weight w.
b) Calculate the bias b.
Solution 23.
a) To find the weight w, we can use the formula zi=w×xi+b.
For i= 1:
z1=w×x1+b
42 = w×5 + b
For i= 2:
z2=w×x2+b
24 = w×3 + b
Solving these two equations simultaneously, we get:
w=z1−z2
x1−x2
=42 −24
5−3=18
2= 9
Therefore, the weight w= 9.
b) To find the bias b, we can substitue w= 9 into one of the equations. Let’s use the first
equation when i= 1:
42 = 9 ×5 + b
42 = 45 + b
b= 42 −45 = −3
Therefore, the bias b=−3.
25 Cryptographic Applications of Homomorphic Encryption
Problem 1. In an e-voting system that uses homomorphic encryption, the votes for candidates
A,B, and Care encrypted as follows: a= 6,b= 8, and c= 4, respectively. The encryption scheme
uses additive homomorphic properties. The result of multiplying the ciphertexts for candidates A
and Bis calculated as a×b= 30. Find out the encrypted vote for candidate C.
Solution 1. Given that the encryption scheme is additive homomorphic, we can calculate the
encrypted vote for candidate Cusing the properties of homomorphic encryption.
We know that a×brepresents the product of ciphertexts for candidates Aand B. Thus, a×b=
30.
Now, to find the encrypted vote for candidate C, we can utilize the additive homomorphic prop-
erty, which states that multiplying ciphertexts corresponds to adding plaintexts. Therefore, the
encrypted vote for candidate Cwill be:
a×b+c= 30 + c
Given a= 6,b= 8, and c= 4, substituting these values:
30 + 4 = 34
Therefore, the encrypted vote for candidate Cis 34.
26 25. HOMOMORPHIC ENCRYPTION IN SECURE COMMUNICATION PROTOCOLS
Problem 25. Alice wants to perform a secure computation on encrypted data using a homo-
morphic encryption scheme. She has two encrypted values c1and c2, where c1=Encpk(7) and
c2=Encpk(5), encrypted under a public key pk. She wants to calculate the sum and product of
the decrypted values without revealing the encryption key. Assume the homomorphic encryption
scheme supports both addition and multiplication operations homomorphically.
Solution 25. a) To calculate the sum of the decrypted values, Alice can perform homomorphic
addition on the encrypted values c1and c2. Let csum =c1⊕c2.
The decryption of csum will give the sum of the decrypted values:
Decsk(csum) = Decsk(c1⊕c2)
=Decsk(Encpk(7) ⊕Encpk (5))
=Decsk(Encpk(7 + 5))
=Decsk(Encpk(12))
= 12
Therefore, the sum of the decrypted values is 12.
b) To calculate the product of the decrypted values, Alice can perform homomorphic multipli-
cation on the encrypted values c1and c2. Let cprod =c1⊗c2.
The decryption of cprod will give the product of the decrypted values:
Decsk(cprod) = Decsk(c1⊗c2)
=Decsk(Encpk(7) ⊗Encpk (5))
=Decsk(Encpk(7 ×5))
=Decsk(Encpk(35))
= 35
Therefore, the product of the decrypted values is 35.
