In this dissertation, we explore different approaches to practical homomorphic encryption schemes. For partial homomorphic encryption schemes, we observe that the versatility is the main bottleneck. To solve this problem, we propose general approaches to improve versatility of them by either extending the range of supported circuits or extending the message space. These general approaches can be applied to a wide range of partial HE schemes and greatly increase the number of applications that they support. For fully homomorphic encryption schemes, the slow running speed and the large ciphertext are the main challenges. Therefore, we propose efficient implementations as well as methods to compress the ciphertext. In detail, the Gentry Halevi FHE scheme and the LTV FHE scheme are implemented and the resulting performance shows significant improvement over previous works. For ciphertext compression, the concept of scheme conversion is proposed. Given a scheme converter, we can convert between schemes with compact ciphertext for communication and homomorphic schemes for computation.

Imagine an encryption scheme where it is possible to add and multiply numbers without any knowledge of the numbers. Instead one could manipulate encryptions of the numbers and then the decryption of the result would give the result of the arithmetic on the original numbers. Encryption algorithms with this property are called homomorphic and have various applications in cloud computing. Homomorphic encryption schemes exist but are generally so inefficient that they are not practical. This report introduces a toy cryptosystem called Bubbles: a somewhat homomorphic encryption scheme created by Professor Martin and Professor Sunar at Worcester Polytechnic Institute. We will show that the original scheme is insecure and may be efficiently "popped". We will then examine two variations of the scheme that introduce noise to increase security and show that Bubbles is still vulnerable except when parameters are carefully chosen. However these safe parameter choices make Bubbles more inefficient than other recent homomorphic schemes.

The research paper Fully Homomorphic Encryption over the Integers by van Dijk, Gentry, Halevi, and Vaikuntanathan [31] explores the construction of an encryption scheme over the integers that is fully homomorphic, using modular arithmetic. The plaintext messages in this encryption are single bits and the ciphertexts are large integers. The homomorphic property means that the algebraic operations on the plaintexts can be carried out analogously on the ciphertexts. We analyze in detail the parameter constraints required to make the scheme functional and secure, prove auxiliary results about noise accumulation, and generate a toy example to concretely illustrate parts of the scheme.

Electromyographic (EMG) signals contain both neural and muscle information. Consequently, EMG signals can be modelled as the composition of two component signals, one of these being a low frequency neural input, the other a relatively high frequency, constant spectrally shaped, stationary, unitary muscle response. Utilizing this model and homomorphic processing estimates of the two component signals can be obtained. These estimates contain neural and muscle information respectively. This thesis establishes the basis for the use of this multiplicative model. It also outlines the application of multiplicative homomorphic processing to EMG signals. The results of this processing are shown to be valid and to contain useful information. The thesis concludes that the model is both appropriate and useful. It also points out that the use of this model and homomorphic processing allows the simultaneous extraction of both neural and muscle information from the EMG signal,a result which is not possible with other currently used processing techniques. / Thesis / Master of Engineering (ME)

Fully homomorphic encryption (FHE) allows for computation of arbitrary func- tions on encrypted data by a third party, while keeping the contents of the encrypted data secure. This area of research has exploded in recent years following Gentry’s seminal work. However, the early realizations of FHE, while very interesting from a theoretical and proof-of-concept perspective, are unfortunately far too inefficient to provide any use in practice. The bootstrapping step is the main bottleneck in current FHE schemes. This step refreshes the noise level present in the ciphertexts by homomorphically evaluating the scheme’s decryption function over encryptions of the secret key. Bootstrapping is necessary in all known FHE schemes in order to allow an unlimited amount of computation, as without bootstrapping, the noise in the ciphertexts eventually grows to a point where decryption is no longer guaranteed to be correct. In this work, we present two new bootstrapping algorithms for FHE schemes. The first works on packed ciphertexts, which encrypt many bits at a time, while the second works on unpacked ciphertexts, which encrypt a single bit at a time. Our algorithms lie at the heart of the fastest currently existing implementations of fully homomorphic encryption for packed ciphertexts and for single-bit encryptions, respectively, running hundreds of times as fast for practical parameters as the previous best implementations.

Homomorphic encryption has progressed rapidly in both efficiency and versatility since its emergence in 2009. Meanwhile, a multitude of pressing privacy needs --- ranging from cloud computing to healthcare management to the handling of shared databases such as those containing genomics data --- call for immediate solutions that apply fully homomorpic encryption (FHE) and somewhat homomorphic encryption (SHE) technologies. Recent rapid progress in fully homomorphic encryption has catalyzed renewed efforts to develop efficient privacy preserving protocols. Several works have already appeared in the literature that provide solutions to these problems by employing leveled or somewhat homomorphic encryption techniques. Here, we propose efficient ways of adapting the most fundamental programming problems; boolean algebra, arithmetic in binary and higher radix representation, sorting, and search to the fully homomorphic encryption domain by focusing on the multiplicative depth of the circuits alongside the more traditional metrics. The reduced depth allows much reduced noise growth and thereby makes it possible to select smaller parameter sizes in leveled FHE instantiations resulting in greater efficiency savings. We begin by exploring already existing solutions to these programming problems, and analyze them in terms of homomorphic evaluation and memory costs. Most of these algorithms appear to be not the best candidates for FHE solutions, hence we propose new methods and improvements over the existing algorithms to optimize performance.

In the past decade, one of the major breakthroughs in computer science theory is the first construction of fully homomorphic encryption (FHE) scheme introduced by Gentry. Using a FHE one may perform an arbitrary numbers of computations directly on the encrypted data without revealing of the secret key. Therefore, a practical FHE provides an invaluable security application for emerging technologies such as cloud computing and cloud-based storage. However, FHE is far from real life deployment due to serious efficiency impediments. The main part of this dissertation focuses on accelerating the existing FHE schemes using GPU and hardware design to make them more efficient and practical towards real-life applications. Another part of this dissertation is for the hardware design of the large key-size RSA cryptosystem. As the Moore law continues driving the computer technology, the key size of the Rivest-Shamir-Adelman (RSA) encryption is necessary to be upgraded to 2048, 4096 or even 8192 bits to provide higher level security. In this dissertation, the FFT multiplication is employed for the large-size RSA hardware design instead of using the traditional interleaved Montgomery multiplication to show the feasibility of the FFT multiplication for large-size RSA design.

In this thesis we have presented original homomorphic images of permutations and monomial progenitors. In some cases we have used the double coset enumeration tech- nique to construct the images and for all of the homomorphic images that we have discovered, the isomorphism type of each group is given. The homomorphic images discovered include Linear groups, Alternating groups, and two sporadic simple groups J1 and J2X2 where J1 is the smallest Janko group and J2 is the second Janko sporadic group.

Over the last decade, the demand for privacy and data confidentiality in communication and storage processes have increased exponentially. Cryptography can be the solution for this demand. However, the critical issue occurs when there is a need for computing publicly on sensitive information or delegating computation to untrusted machines. This must be done in such a way that preserves the information privacy and accessibility. For this reason, we need an encryption algorithm that allows computation on information without revealing details about them. In 1978 Rivest, Adleman and Dertouzos raised a crucial question: can we use a special privacy homomorphism to encrypt the data and do an unlimited computations on it while it remains encrypted without the necessity of decrypting it? Researchers made extensive efforts to achieve such encryption algorithm. In this paper, we introduce the implementation of the CRT-based somewhat homomorphic encryption over the integers scheme. The main goal is to provide a proof of concept of this new and promising encryption algorithm. / Graduate

L'annonce de l'essor du chiffrement des données se heurte à celle de l'avènement du "big data". Il n'est maintenant plus suffisant d'envoyer et de recevoir des données, il faut pouvoir les analyser, les exploiter ou encore les partager à grande échelle. Or, les données à protéger sont de plus en plus nombreuses, notamment avec la prise de conscience de l'impact qu'ont les nouvelles technologies (smartphones, internet of things, cloud,...) sur la vie privée des utilisateurs. En rendant ces données inaccessibles, le chiffrement bloque a priori les fonctionnalités auxquelles les utilisateurs et les fournisseurs de service sont habitués. Pour rétablir ces fonctionnalités, il est nécessaire de savoir calculer des fonctions de données chiffrées, et cette thèse explore plusieurs pistes dans ce sens. Dans une première partie, nous nous intéressons au chiffrement totalement homomorphe qui permet de réaliser des calculs arbitraires sur les données chiffrées. Ce type de chiffrement est cependant particulièrement coûteux, notamment à cause de l'appel souvent nécessaire à une procédure très coûteuse : le réamorçage. Nous prouvons ici que minimiser le nombre de réamorçages est un problème NP-complet et donnons une méthode pratique pour approximer ce minimum. Dans une seconde partie, nous étudions des schémas dédiés à une fonctionnalité donnée. Le premier cas d'usage considéré est celui de la déduplication vérifiable de données chiffrées. Il s'agit pour un serveur de stockage externe d'être assuré qu'il ne conserve qu'un seul exemplaire de chaque fichier, même si ceux-ci sont chiffrés, ce qui lui permet d'optimiser l'usage de ses ressources mémoires. Ensuite, nous proposons un schéma de chiffrement cherchable permettant de détecter des intrusions dans un réseau de télécommunications chiffrés. En effet, le travail d'inspection du réseau par des moteurs d'analyse est actuellement entravé par la croissance du trafic chiffré. Les résultats obtenus permettent ainsi d'assurer la confidentialité des échanges tout en garantissant l'absence d'intrusions malveillantes dans le trafic / Nowadays, encryption and services issued of ``big data" are at odds. Indeed, encryption is about protecting users privacy, while big data is about analyzing users data. Being increasingly concerned about security, users tend to encrypt their sensitive data that are subject to be accessed by other parties, including service providers. This hinders the execution of services requiring some kind of computation on users data, which makes users under obligation to choose between these services or their private life. We address this challenge in this thesis by following two directions.In the first part of this thesis, we study fully homomorphic encryption that makes possible to perform arbitrary computation on encrypted data. However, this kind of encryption is still inefficient, and this is due in part to the frequent execution of a costly procedure throughout evaluation, namely the bootstrapping. Thus, efficiency is inversely proportional to the number of bootstrappings needed to evaluate functions on encrypted data. In this thesis, we prove that finding such a minimum is NP-complete. In addition, we design a new method that efficiently finds a good approximation of it. In the second part, we design schemes that allow a precise functionality. The first one is verifiable deduplication on encrypted data, which allows a server to be sure that it keeps only one copy of each file uploaded, even if the files are encrypted, resulting in an optimization of the storage resources. The second one is intrusion detection over encrypted traffic. Current encryption techniques blinds intrusion detection services, putting the final user at risks. Our results permit to reconcile users' right to privacy and their need of keeping their network clear of all intrusion