Research On Several Applications Of The Negative Representation Of Information

Negative representation of information is a new method for information representation, and it uses the complementary set instead of an original dataset to achieve privacy preservation and data security. Negative database is a form of negative representation of information for storing data, and it has become a new privacy-preserving and data security technique. Reversing the negative database to recover original data has been proven to be an NP-hard problem. The negative database has some promising properties, e.g., it can directly support some database operators and computations, and it is worth studying the negative database and exploiting its properties. Currently, the research on the negative representation of information is in the beginning stage. The theoretical basis of negative representation of information needs to be improved, and the properties of negative databases are not fully explored. The negative database is expected to be applied to more real-world applications.This dissertation focuses on studying the generation algorithm of negative databases, constructing privacy-preserving models based on negative databases, and applying negative databases to real-world applications. Specifically, the contributions are listed as follows.(1) The K-hidden algorithm is proposed, and it can control the hardness (against the local search strategy) of reversing the generated negative database in a fine-grained manner. The k-hidden algorithm uses K-1 probability parameters to generate negative databases that are "equivalent" to K-SKT instances, and this kind of negative databases are called K-NDBs. The K-1 probability parameters are used to control the distribution of different types of entries in a negative database in a fine-grained manner, and thus, to control the hardness of reversing this negative database (by the local search strategy). Theoretical analyses and experimental results show that, compared with the typical q-hidden algorithm and p-hidden algorithm, the K-hidden algorithm could generate more hard-to-reverse negative databases (with regard to the local search strategy).(2) A one-time password authentication scheme based on the negative database is proposed. In the proposed scheme, users and the server use different random numbers to generate different negative databases for different login requests, the negative databases are regarded as "dynamic" negative authentication data. In the enrollment phase, the user will share his secret data (e.g. password and the seed for random numbers) with the server, and they will synchronize their data with each other in the login phase and authentication phase based on these secret data. Thus, the server can effectively authenticate the user. Then, the security and efficiency of the proposed scheme are analyzed. It is demonstrated that the proposed scheme is robust to the message blocking, and it can be extended to resist the man-in-the-middle attack. Next, a solution for applying the proposed scheme to the business management is proposed to demonstrate its potential utility.(3) A private set intersection protocol based on the negative database is proposed. First, the semi-homomorphism property of negative databases is proposed. Based on the semi-homomorphism property, a two-party private set intersection protocol is constructed, and thus, its security and efficiency are analyzed. Next, the two-party protocol is extended to a multi-party private set intersection protocol based on the negative database. This study demonstrates that negative databases can be used for secure multi-party computation.(4) The negative iris recognition is proposed. Negative iris recognition is a secure iris recognition scheme based on the negative database. It exploits the property that negative databases can directly support Hamming distance estimation. The server converts enrolled iris data to negative databases, and it recognizes real-time iris data based on the Hamming distance estimation. Thus, negative iris recognition is able to achieve reasonable performance while preserving the privacy of iris data. Then, it is demonstrated that negative iris recognition can support two important strategies, i.e., shifting and masking, to enhance its performance. Next, the security and efficiency of negative iris recognition are analyzed, and it is demonstrated that negative iris recognition satisfies the irreversibility, revocability and renewability, and unlinkability. Experimental results show that negative iris recognition could achieve a great performance on the typical iris database CASIA-V3.0-Interval.(5) An algorithm for generating real-valued negative databases is proposed, and the real-valued negative database could be easier to be used in applications with real-valued representation than the binary negative databases. First, the real-valued domains are converted to a set of intervals, and thus the intervals are encoded to binary strings. Next, a real-valued positive database can be encoded to a binary positive database, and a binary negative database generation algorithm can be employed to generate a binary negative database. Then, the generated binary negative database can be decoded to a real-valued negative database. It is demonstrated that reversing the real-valued negative database to recover the original data is an NP-hard problem. Finally, an example of applying the real-valued negative database to privacy-preserving data publication is given.