Homework 3 Solved

Description

0. Secure Multiparty Computation (30 points)

⃗		10	) while Bob holds
Alice holds a private Boolean vector A with 10 Boolean entries ({0, 1}
⃗				10	). Design and
another private Boolean vector B with another 10 Boolean entries ({0, 1}
implement a protocol using the Fairplay					⃗ ⃗
	to securely compute the scalar product A · B

without sharing their inputs to each other.

• The scalar product computation should be converted to garbled circuits using SFDL.

• Fairplay secure function evaluation: https://www.cs.huji.ac.il/project/Fairplay/.

• Readme file for runningFairplay SFE: https://www.cs.huji.ac.il/project/Fairplay/Fairplay/Readme.txt

Tasks:

⃗

(a) Alice generates random Boolean entries for A while Bob generates random Boolean

⃗

entries for B. (3 points)

(b) Write the SFDL program for Alice and Bob. (12 points)

3. Compile it for Alice and Bob, and run the protocol (communication is integrated in Fairplay). (5 points)

(d) Report the input Boolean vectors, the SFDL program, SHDL circuit, and output results

⃗ _· ⃗

A B (for two parties). (10 points)

Submission Part I: (1) a report including the protocol design, implementation details, input matrices and output results, (2) screenshots of the major steps of each task and your answers (you can explain your findings with tables or figures), and (3) source code files – all named with the prefix “hw3-1-” (e.g., hw3-1-report.pdf, and hw3-1-matrix.txt).

Illinois Institute of Technology – CS528 Data Privacy and Security

2. Application of Homomorphic Encryption (40 points)

Alice holds a private matrix A (nonnegative integer entries) with size 5 × 8 while Bob holds a private matrix B (nonnegative integer entries) with size 8 × 4. Design and implement a two-party protocol to securely compute the product A×B. Hint: Homomorphic Encryption (e.g., Paillier Cryptosystem which is a public key-based scheme) can be used to design the protocol.

• Paillier in Python: https://python-paillier.readthedocs.io/en/develop/ https://github.com/mikeivanov/paillier

• Paillier in Java:

https://www.csee.umbc.edu/ kunliu1/research/Paillier.html

Tasks:

1. Alice generates random nonnegative integer entries for A while Bob generates random nonnegative integer entries for B. (5 points)

2. Design the cryptographic protocol between Alice and Bob to perform secure computa-tion. (10 points)

1. 3. Write the programs for Alice and Bob: computation and communication. Note that communication should be established to exchange encrypted messages, e.g., using Socket programming or establishing other distributed computing systems. (20 points)

1. 3. • Socket Programming in Python: https://realpython.com/python-sockets/

1. 3. • Socket Programming in Java: https://www.tutorialspoint.com/java/java networking.htm

If you have difficulties on distributed computing systems, you can write a single program to simulate the procedures of Alice and Bob. In that case, you should mark all the steps (computation by which party; message sent from which party to which party) in the source codes.

4. Report the input matrices, the last ciphertext (right before the decryption) and the decrypted product A ×B using two different key sizes 512-bit and 1024-bit. (5 points)

Submission Part II: (1) a report including the protocol design, implementation details, input matrices, last ciphertext, and decrypted result, and (2) source code files – all named with the prefix “hw3-2-” (e.g., hw3-2-report.pdf, and hw3-2-alice.java).

3. SMC Protocol Design (30 points + 20 bonus points)

Four different parties (Alice, Bob, Chris, and David) locally hold four different vectors, respectively (10 integers in each vector).

Illinois Institute of Technology – CS528 Data Privacy and Security

•	⃗	, . . . , a10].
	Alice holds: Va = [a1
•	⃗
	Bob holds: Vb = [b1, . . . , b10].
•	⃗	, . . . , c10].
	Chris holds: Vc = [c1
•	⃗
	David holds: Vd = [d1, . . . , d10].

Design a cryptographic protocol to securely sum all the four vectors:

⃗⃗⃗⃗⃗

V = V_a + V_b + V_c + V_d

⃗

and find the maximum value (out of the 10 entries) in V .

Hints:

• You can use the combination of Homomorphic Encryption (e.g., Paillier’s Cryptosys-tem), Garbled Circuit (e.g., Fairplay) and Permutation to solve this problem.

•	⃗	⃗	will be the
	Sum V	should not be disclosed to any party. The maximum value in V

only output.

• If necessary, two-party Fairplay can also be used to securely compare multiple values by executing multiple comparisons.

• Only using Garbled Circuit (e.g., Fairplay) may not be computationally practical.

• Try to reduce the information leakage in the protocol as much as possible.

Tasks:

1. Protocol Design (write the pseudocode in the report). (30 points: partial credits will be given to different functions and building blocks)

2. Implementation of the Protocol (similar to the setting). (20 bonus points)

Submission Part III: (1) a report including the protocol design, (2) implementation and testing details in the report (bonus), and (3) source code files (bonus) – all named with the prefix “hw3-3-” (e.g., hw3-3-report.pdf, and hw3-3-alice.java).

3