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.
