辅导案例-ICSI-426/526

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top



DEPARTMENT OF COMPUTER SCIENCE

ICSI-426/526 Cryptography – Spring 2020

Homework 3

Give out date: March 26, 2020
Due date/time: April 15, 2020, 11:59 p.m. Total marks: 10

Late submissions would have penalty 10% every day up to five days.
Objective
The purpose of this assignment is to solidify concepts of Shamir Secret Sharing (SSS) Scheme and
Homomorphic Encryption.
For Question 1 and 2, you can use pen and paper, take a clean picture (or type) and submit it. Question 3
is a programming-based question.
Question 1
Prove than (3, n)-(SSS) scheme is information theoretically secure.
[2 marks]

Question 2 [1 + 1 = 2 Marks]
This assignment must be completed in group of two students. Using (2, n) SSS scheme, shares of two
secret values have been created under modulo prime number (p = 31). You will receive one pair of shares,
i.e. share of each of the two secret values, and the other pair of shares will be given to your partner.
Information about your partner and shares will be forwarded to you via email.
You are required to do the following (show your work using pen and paper):
1. Calculate the Average of respective shares of two secret values provided to you and your partner.
You are required to submit the reconstructed average value of both the shares. If it is not possible
to calculate the Average using given shares, provide the justification. You will be taking the
following steps:
a. You are given: (x1, fS1(x1)) and (x1, fS2(x1)); and your partner is given: (x2, fS1(x2)) and (x2,
fS2(x2)), where fS1(x1) and fS1(x2) are the shares of secret S1 at x1 and x2, respectively, and
similarly, fS2(x1) and fS2(x2) are the shares of secret S2 at x1 and x2, respectively.
b. You will compute the average (in encrypted form) (say fS’(x1)) of fS1(x1) and fS2(x1) under
mod p, and your partner will compute the average (fS’(x2)) of fS1(x2) and fS2(x2) under mod
p.
c. In the next step, you and your partner will collaborate with your two averaged shares, (x1,
fS’(x1)) and (x2, fS’(x2)), and apply Lagrange interpolation formula to reconstruct the
average (in plaintext form) of the two secret values.


2. Calculate the Multiplication of respective shares of two secret values provided to you and your
partner. You are required to submit the reconstructed multiplied value of both the shares. If it is
not possible to calculate the multiplication using given shares, provide the justification. You will
be taking the following steps:
a. Same as Que 2(a).
b. You will compute the multiplication (in encrypted form) (say fS’’(x1)) of fS1(x1) and fS2(x1)
under mod p, and your partner will compute the multiplication (fS’’(x2)) of fS1(x2) and
fS2(x2) under mod p.
c. In the next step, you and your partner will collaborate with your two multiplied shares,
(x1, fS’’(x1)) and (x2, fS’’(x2)), and apply Lagrange interpolation formula to reconstruct the
multiplication (in plaintext form) of the two secret values.
Hints:
1) Not all the arithmetic homomorphic operations are supported by the SSS scheme.
2) All the calculations must be under modulo prime number (p = 31).

Question 3
(a) Implement (2, 3) Shamir’s Secret Sharing (SSS) scheme (both share preparation and
reconstruction) for images. You need to show the working of your program by creating shares of
an image and show the image shares and the reconstructed image as output. You need to operate
on image data, leaving the header intact. You can use any BMP image of your choice. Note that
the header length in BMP file format is 54 bytes.
[3 marks]

(b) Next, you are required to demonstrate the homomorphic properties of SSS scheme using the
image downscaling operation. In a homomorphic encryption scheme, computations performed on
encrypted data, when decrypted, generates the same value as when the same computations are
performed on the plaintext.

The downscaling operation takes an input image and produces an image whose width and height
are less than the input image. You need to implement downscaling by a factor of 2. This means
that both the width and height of your output image will be exactly half of the input image.

You are required to do the following steps;

1) Take an input image I of certain resolution and use the downscale method on this image to
obtain the downscaled image Io. In the downscale method, each pixel of Io is the average of
four pixels of I. For example, pixel (0,0) of Io is the average of pixels (0,0), (0,1), (1,0), (1,1)
of I; pixel (1,0) of Io is the average of (2,0), (2,1), (3,0), (3,1) of image I. As a result, the
resolution of Io will be half of I in both x and y dimensions.
2) Create 3 shares (denoted by I1, I2, I3) of I using the SSS scheme.
3) Perform the downscale method on all the three shares and obtain the downscaled shares
(denoted by Is1, Is2, Is3).
4) Pick any 2 downscaled shares, i.e. from Is1, Is2, Is3, and reconstruct the downscaled plaintext
image (denoted by Is).
5) Compute the mean average error between the two images, Io and Is, using the following
equation:

MAE = j = 1 to w×h (|Io(j) – Is(j)|)


where w and h are image width and height.
6) Show the output of each step and report your observations.

[3 marks]
Submission
You must submit the following via UAlbany Blackboard:
(a) Source code along with the instructions to run it for Question 3.
(b) A pdf file containing your code for Question 3.
(c) A pdf file containing answers to Questions 1, 2, and 3.
(d) A video link (of max 5 minutes) that shows the working of your program.
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468