Electronic Thesis and Dissertation Repository


Master of Engineering Science


Electrical and Computer Engineering


Dr. Aleksander Essex


Secure multi party computation allows two or more parties to jointly compute a function under encryption without leaking information about their private inputs. These secure computations are vital in many fields including law enforcement, secure voting and bioinformatics because the privacy of the information is of paramount importance.

One common reference problem for secure multi party computation is the Millionaires' problem which was first introduced by Turing Award winner Yao in his paper "Protocols for secure computation". The Millionaires' problem considers two millionaires who want to know who is richer without disclosing their actual worth.

There are public-key cryptosystems that currently solve this problem, however they use bitwise decomposition and Boolean algebra on encrypted bits. This type of solution is costly as it requires each bit requires its own encryption and decryption.

Our solution to the Millionaires' problem and secure integer comparison looks at a new approach which doesn't use the decomposition method and instead encrypts the full length of the message in one encryption (within scope). This method also extends in a linear fashion, so larger integers remain efficient to compare.

In this thesis, we present a new cryptosystem with a novel homomorphic property used for secure integer comparison, as well as a protocol implementing the cryptosystem and a simulation security proof for the protocol. Finally, we implemented the system and compared it to systems that are being used today.