On encrypted-domain signal processing

Abstract

In this big data era, often a person (say Bob) needs another person (say Alice) to perform processing on his data. But both Alice and Bob do not know each other and do not trust each other. It would be desirable for Bob to send his data in encrypted form to Alice and for Alice to perform all the processing of Bob's data in the encrypted domain such that Bob would be able to decrypt the processed data sent by Alice to obtain the desired results. This kind of processing is called signal processing in the encrypted domain (SPED). Some simple operations such as integer addition and multiplication have been known to be possible for some cryptosystems. In this thesis, we focus on two SPED problems: (1) the feasibility of performing bitwise operations in the encrypted domain and (2) solving a system of linear equations, Ax = b, in the encrypted domain. For (1), we examine the basic bitwise operations and pose the question of whether these can be perform in the encrypted domain. We show that such bitwise operations are not possible for some cryptosystems. For (2), we focus on a common iterative method called the Gauss-Seidel method to solve Ax = b that is computationally feasible even when the dimension of A is large. The motivation is that the Gauss-Seidel requires only addition and multiplication and thus should be possible to be performed in the encrypted domain. However, problems occur when A, x or b contain non-integer numbers as the encrypted domain cannot handle non-integers. In this thesis, we propose some integer approximation for the problem and show that it can solve the problem with high accuracy.

Date of Award	2013
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology