Dissertations, Theses, and Capstone Projects

Date of Degree

6-2021

Document Type

Dissertation

Degree Name

Ph.D.

Program

Computer Science

Advisor

Rosario Gennaro

Committee Members

William E. Skeith

Nelly Fazio

Markus Jakobsson

Subject Categories

Other Computer Engineering

Keywords

Secure Multi-Party Computation, Homomorphic Secret Sharing, Publicly Evaluatable Perceptual Hashing

Abstract

Secure Multi-Party Computation (MPC) allows a group of parties to compute a join function on their inputs without revealing any information beyond the result of the computation. We demonstrate secure function evaluation protocols for branching programs, where the communication complexity is linear in the size of the inputs, and polynomial in the security parameter. Our result is based on the circular security of the Paillier's encryption scheme. Our work followed the breakthrough results by Boyle et al. [9; 11]. They presented a Homomorphic Secret Sharing scheme which allows the non-interactive computation of Branching Programs over shares of the secret inputs. Their protocol is based on the Decisional Diffie-Hellman Assumption. Additionally, we offer a verification technique to directly check correctness of the actual computation, rather than the absence of a potential error as in [9]. This results in fewer repetitions of the overall computation for a given error bound. We also use Paillier’s encryption as the underlying scheme of publicly perceptual hashing. Perceptual hashing allows the computation of a robust fingerprint of media files, such that the fingerprint can be used to detect the same object even if it has been modified in per- ceptually non-significant ways (e.g., compression). The robustness of such functions relies on the use of secret keys both during the computation and the detection phase. We present examples of publicly evaluatable perceptual hash functions which allow a user to compute the perceptual hash of an image using a public key, while only the detection algorithm will use the secret key. Our technique can be used to encourage users to submit intimate images to blacklist databases to stop those images from ever being posted online – indeed using a publicly evaluatable perceptual hash function the user can privately submit the fingerprint, without ever revealing the image. We present formal definitions for the security of perceptual hash, a general theoretical result that uses Fully Homomorphic Encryption, and a specific construction using Paillier’s encryption. For the latter we show via extensive implementation tests that the cryptographic overhead can be made minimal, resulting in a very efficient construction.

Download

Share

COinS