Homomorphic Encryption Assignment

Tasks
Q1: Homomorphic Encryption (10 points) Elgamal encryption is an asymmetric key
encryption algorithm for public-key cryptography which is based on the Diffie–Hellman
key exchange. It consists of three components: key generation, encryption and decryption.
• Key generation: Alice generates a key pair as follows:
– Generate an efficient description of a cyclic group G of order q, with generator g.
– Let e represent the unit element of G.
– Choose an integer x randomly from {1, . . . , q − 1}.
– Compute h := g
x
.
– The public key consists of the values (G, q, g, h). Alice publishes this public
key and retains x as her private key, which must be kept secret.
• Encryption: Bob encrypts a message M to Alice using her public key (G, q, g, h)
as follows:
– Map the message M to an element m of G using a reversible mapping
function.
– Choose an integer y randomly from {1, . . . , q − 1}
– Compute s := h
y
. This is called the shared secret.
– Compute c1 := g
y
.
– Compute c2 := m · s.
– Bob sends the ciphertext (c1, c2) to Alice
• Decryption: Alice decrypts a ciphertext (c1, c2) with her private key x as follows:
1
– Compute s := c
x
1
. Since c1 = g
y
, c
x
1 = g
xy = h
y and thus it is the same
shared secret that was used by Bob in encryption.
– Compute s
−1
, the inverse of s in the group G. This can be computed
in one of several ways. If G is a subgroup of a multiplicative group of
integers modulo n, the modular multiplicative inverse can be computed
using the Extended Euclidean Algorithm. An alternative is to compute
s
−1 as c
q−x
1
. This is the inverse of s because of Lagrange’s theorem, since
s · c
q−x
1 = g
xy
· g
(q−x)y = (g
q
)
y = e
y = e.
– m := c2 · s
−1
. This calculation produces the original message m, because
c2 = m · s; hence c2 · s
−1 = (m · s) · s
−1 = m · e = m.
– Map m back to the plaintext message M.
Answer the following questions.
(a) (5 points) Show that the above Elgamal encryption scheme is homomorphic
with respect to multiplication.
(b) (5 points) Show that the above Elgamal encryption scheme is not homomorphic
with respect to addition.
Q2: Homomorphic-Based Yao Millionaire Problem (15 points)
(a) (5 points) Explain why does the Homomorphic based protcol for Yao’s millionaire problem (in Lecture 11 slides 22-23) fail when using using unpadded RSA?
(b) (10 points) Design a protocol that uses unpadded RSA. Verify that your protocol works by implementing your proposed protocol using the notebook file
(”Yao RSA.ipnyb”).
Q3: Oblivious Transfer (OT) (10 pts)
(a) (10 points) Design a simple protocol for 1-out-of-n OT starting from 1-out-of-2
OT. Assume that both Alice and Bob are honest-but-curious. i.e., they follow the
protocol but from time to time they collect extra information looking for exposing
private data about each other. In your protocol, Alice and Bob can access the
1-out-of-2 functionality n times. Explain your protocol n details (Hint: Think of
how to extend 1-out-of-2 to 1-out-of-3 and then generalize it to 1-out-of-n)
(b) (Bonus 10 points) Implement the 1-out-of-n OT protocol in ”OT 1 n.ipynb” using
Socket Programming.
2

Get professional assignment help cheaply

Are you busy and do not have time to handle your assignment? Are you scared that your paper will not make the grade? Do you have responsibilities that may hinder you from turning in your assignment on time? Are you tired and can barely handle your assignment? Are your grades inconsistent?

Whichever your reason may is, it is valid! You can get professional academic help from our service at affordable rates. We have a team of professional academic writers who can handle all your assignments.

Our essay writers are graduates with diplomas, bachelor, masters, Ph.D., and doctorate degrees in various subjects. The minimum requirement to be an essay writer with our essay writing service is to have a college diploma. When assigning your order, we match the paper subject with the area of specialization of the writer.

Why choose our academic writing service?

  • Plagiarism free papers
  • Timely delivery
  • Any deadline
  • Skilled, Experienced Native English Writers
  • Subject-relevant academic writer
  • Adherence to paper instructions
  • Ability to tackle bulk assignments
  • Reasonable prices
  • 24/7 Customer Support
  • Get superb grades consistently

 

 


Get Professional Assignment Help Cheaply

fast coursework help

Are you busy and do not have time to handle your assignment? Are you scared that your paper will not make the grade? Do you have responsibilities that may hinder you from turning in your assignment on time? Are you tired and can barely handle your assignment? Are your grades inconsistent?

Whichever your reason may is, it is valid! You can get professional academic help from our service at affordable rates. We have a team of professional academic writers who can handle all your assignments.

Our essay writers are graduates with diplomas, bachelor's, masters, Ph.D., and doctorate degrees in various subjects. The minimum requirement to be an essay writer with our essay writing service is to have a college diploma. When assigning your order, we match the paper subject with the area of specialization of the writer.

Why Choose Our Academic Writing Service?

  • Plagiarism free papers
  • Timely delivery
  • Any deadline
  • Skilled, Experienced Native English Writers
  • Subject-relevant academic writer
  • Adherence to paper instructions
  • Ability to tackle bulk assignments
  • Reasonable prices
  • 24/7 Customer Support
  • Get superb grades consistently

How It Works

1.      Place an order

You fill all the paper instructions in the order form. Make sure you include all the helpful materials so that our academic writers can deliver the perfect paper. It will also help to eliminate unnecessary revisions.

2.      Pay for the order

Proceed to pay for the paper so that it can be assigned to one of our expert academic writers. The paper subject is matched with the writer’s area of specialization.

3.      Track the progress

You communicate with the writer and know about the progress of the paper. The client can ask the writer for drafts of the paper. The client can upload extra material and include additional instructions from the lecturer. Receive a paper.

4.      Download the paper

The paper is sent to your email and uploaded to your personal account. You also get a plagiarism report attached to your paper.

smile and order essaysmile and order essayPLACE THIS ORDER OR A SIMILAR ORDER WITH 24/7 ESSAY WRITERS TODAY AND GET AN AMAZING DISCOUNT

order custom essay paper  

smile and order essaysmile and order essayPLACE THIS ORDER OR A SIMILAR ORDER WITH ORDER YOUR ESSAY TODAY AND GET AN AMAZING DISCOUNT

order custom essay paper