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.

Lattice-based cryptography has generated considerable interest in the last two decades due toattractive features, including conjectured security against quantum attacks, strong securityguarantees from worst-case hardness assumptions and constructions of fully homomorphicencryption schemes. On the other hand, even though it is a crucial part of many lattice-basedschemes, Gaussian sampling is still lagging and continues to limit the effectiveness of this newcryptography. The first goal of this thesis is to improve the efficiency of Gaussian sampling forlattice-based hash-and-sign signature schemes. We propose a non-centered algorithm, with aflexible time-memory tradeoff, as fast as its centered variant for practicable size of precomputedtables. We also use the Rényi divergence to bound the precision requirement to the standarddouble precision. Our second objective is to construct Falcon, a new hash-and-sign signaturescheme, based on the theoretical framework of Gentry, Peikert and Vaikuntanathan for latticebasedsignatures. We instantiate that framework over NTRU lattices with a new trapdoor sampler.

" In the last decade, cloud computing became popular among companies for outsourcing some of their services. Companies use cloud services to store crucial information such as financial and client data. Cloud services are not only cost effective but also easier to manage since the companies avoid maintenance of servers. Although cloud has its advantages, maintaining the security is a big concern. Cloud services might not have any malicious intent, but attacks targeting cloud systems could easily steal vital data belong to the companies. The only protection that assures the security of the information is a strong encryption. However, these schemes only protects the information but prevent you to do any computation on the data. This was an open problem for more than 30 years and it has been solved recently by the introduction of the first fully homomorphic encryption (FHE) scheme by Gentry. The FHE schemes allow you to do arbitrary computation on an encrypted data by still preserving the encryption. Namely, the message is not revealed (decrypted) at any given time while computing the arbitrary circuit. However, the first FHE scheme is not practical for any practical application. Later, numerous research work has been published aiming at making fully homomorphic encryption practical for daily use, but still they were too inefficient to be used in everyday practical applications. In this dissertation we tackle the efficiency problems of fully homomorphic encryption (FHE) schemes. We propose two new FHE schemes that improve the storage requirement and runtime performance. The first scheme (Doröz, Hu and Sunar) reduces the size of the evaluation keys in existing NTRU based FHE schemes. In the second scheme (F-NTRU) we designed an NTRU based FHE scheme which is not only free of costly evaluation keys but also competitive in runtime performance. We further proposed two hardware accelerators to increase the performance of arithmetic operations underlying the schemes. The first accelerator is a custom hardware architecture for realizing the Gentry-Halevi fully homomorphic encryption scheme. This contribution presents the first full realization of FHE in hardware. The architecture features an optimized multi-million bit multiplier based on the Schönhage-Strassen multiplication algorithm. Moreover, a number of optimizations including spectral techniques as well as a precomputation strategy is used to significantly improve the performance of the overall design. The other accelerator is optimized for a class of reconfigurable logic for somewhat homomorphic encryption (SWHE) based schemes. Our design works as a co-processor: the most compute-heavy operations are offloaded to this specialized hardware. The core of our design is an efficient polynomial multiplier as it is the most compute-heavy operation of our target scheme. The presented architecture can compute the product of very-large polynomials more efficiently than software implementations on CPUs. Finally, to assess the performance of proposed schemes and hardware accelerators we homomorphically evaluate the AES and the Prince block ciphers. We introduce various optimizations including a storage-runtime trade-off. Our benchmarking results show significant speedups over other existing instantiations. Also, we present a private information retrieval (PIR) scheme based on a modified version of Doröz, Hu and Sunar’s homomorphic scheme. The scheme is capable of privately retrieving data from a database containing 4 billion entries. We achieve asymptotically lower bandwidth cost compared to other PIR schemes which makes it more practical. "

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.

Security is always a big problem in IoT (internet of things),when it comes to IoT, there must have cloud computing because many devices in IoT are small embedded devices and they don’t always have enough power to finish some complex calculations. Then, they need to take advantage of a third party system especially cloud at present to finish some operations, but the cloud is not safe enough now, in which some important and private information may be leaked, then people introduce homomorphic encryption which can do calculation on encrypted data. To meet the modern needs for random calculations in which the operation can have random times’ addition and multiplication, researchers are trying to make fully homomorphic encryption practical. So in my thesis, I would choose one fully homomorphic encryption scheme to implement a detailed IoT scenario using some IoT devices such as laptop and raspberry pi. Then I would use performance measurements such as response time calculations to do the performance evaluation such as effectiveness and scalability for this technique. Finally, I find some relationship between different parameters and response time, and also effectiveness, scalability in results and conclusion part.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第20511号 / 情博第639号 / 新制||情||111(附属図書館) / 京都大学大学院情報学研究科社会情報学専攻 / (主査)教授 石田 亨, 教授 中村 佳正, 教授 岡部 寿男, 岡本 龍明 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Title: Homomorphic encryption and coding theory Author: Veronika Půlpánová Department: Department of algebra Supervisor: RNDr. Michal Hojsík, Ph.D., Department of algebra Abstract: The current mainstream in fully homomorphic encryption is the appro- ach that uses the theory of lattices. The thesis explores alternative approaches to homomorphic encryption. First we present a code-based homomorphic encrypti- on scheme by Armknecht et. al. and study its properties. Then we describe the family of cryptosystems commonly known as Polly Cracker and identify its pro- blematic aspects. The main contribution of this thesis is the design of a new fully homomorphic symmetric encryption scheme based on Polly Cracker. It proposes a new approach to overcoming the complexity of the simple Polly Cracker - based cryptosystems. It uses Gröbner bases to generate zero-dimensional ideals of po- lynomial rings over finite fields whose factor rings are then used as the rings of ciphertexts. Gröbner bases equip these rings with a multiplicative structure that is easily algorithmized, thus providing an environment for a fully homomorphic cryptosystem. Keywords: Fully homomorphic encryption, Polly Cracker, coding theory, zero- dimensional ideals

With the monetization of user data, data breaches have become very common these days. In the past five years, there were more than 7000 data breaches involving theft of personal information of billions of people. In the year 2020 alone, the global average cost per data breach was $3.86 million, and this number rose to $4.24 million in 2021. Therefore, the need for maintaining data security and privacy is becoming increasingly critical. Over the years, various data encryption schemes including RSA, ECC, and AES are being used to enable data security and privacy. However, these schemes are deemed vulnerable to quantum computers with their enormous processing power. As quantum computers are expected to become main stream in the near future, post-quantum secure encryption schemes are required. To this end, through NIST’s standardization efforts, code-based and lattice-based encryption schemes have emerged as one of the plausible way forward. Both code-based and lattice-based encryption schemes enable public key cryptosystems, key exchange mechanisms, and digital signatures. In addition, lattice-based encryption schemes support fully homomorphic encryption (FHE) that enables computation on encrypted data. Over the years, there have been several efforts to design efficient FPGA-based and ASIC-based solutions for accelerating the code-based and lattice-based encryption schemes. The conventional code-based McEliece cryptosystem uses binary Goppa code, which has good code rate and error correction capability, but suffers from high encoding and decoding complexity. Moreover, the size of the generated public key is in several MBs, leading to cryptosystem designs that cannot be accommodated on low-end FPGAs. In lattice-based encryption schemes, large polynomial ring operations form the core compute kernel and remain a key challenge for many hardware designers. To extend support for large modular arithmetic operations on an FPGA, while incurring low latency and hardware resource utilization requires substantial design efforts. Moreover, prior FPGA solutions for lattice-based FHE include hardware acceleration of basic FHE primitives for impractical parameter sets without the support for bootstrapping operation that is critical to building real-time privacy-preserving applications. Similarly, prior ASIC proposals of FHE that include bootstrapping are heavily memory bound, leading to large execution times, underutilized compute resources, and cost millions of dollars. To respond to these challenges, in this dissertation, we focus on the design of efficient hardware accelerators for code-based and lattice-based public key cryptosystems (PKC). For code-based PKC, we propose the design of a fully-parameterized en/decryption co-processor based on a new variant of McEliece cryptosystem. This co-processor takes advantage of the non-binary Orthogonal Latin Square Code (OLSC) to achieve a lower computational complexity along with smaller key size than that of the binary Goppa code. Our FPGA-based implementation of the co-processor is ∼3.5× faster than an existing classic McEliece cryptosystem implementation. For lattice-based PKC, we propose the design of a co-processor that implements large polynomial ring operations. It uses a fully-pipelined NTT polynomial multiplier to perform fast polynomial multiplications. We also propose the design of a highly-optimized Gaussian noise sampler, capable of sampling millions of high-precision samples per second. Through an FPGA-based implementation of this lattice-based PKC co-processor, we achieve a speedup of 6.5× while utilizing 5× less hardware resources as compared to state-of-the-art implementations. Leveraging our work on lattice-based PKC implementation, we explore the design of hardware accelerators that perform FHE operations using Cheon-Kim-Kim-Song (CKKS) scheme. Here, we first perform an in-depth architectural analysis of various FHE operations in the CKKS scheme so as to explore ways to accelerate an end-to-end FHE application. For this analysis, we develop a custom architecture modeling tool, SimFHE, to measure the compute and memory bandwidth requirements of hardware-accelerated CKKS. Our analysis using SimFHE reveals that, without a prohibitively large cache, all FHE operations exhibit low arithmetic intensity (<1 Op/byte). To address the memory bottleneck resulting from the low arithmetic intensity, we propose several memory-aware design (MAD) techniques, including caching and algorithmic optimizations, to reduce the memory requirements of CKKS-based application execution. We show that the use of our MAD techniques can yield an ASIC design that is at least 5-10× cheaper than the large-cache proposals, but only ∼2-3× slower. We also design FAB, an FPGA-based accelerator for bootstrappable FHE. FAB, for the first time ever, accelerates bootstrapping (along with basic FHE primitives) on an FPGA for a secure and practical parameter set. FAB tackles the memory-bounded nature of bootstrappable FHE through judicious datapath modification, smart operation scheduling, and on-chip memory management techniques to maximize the overall FHE-based compute throughput. FAB outperforms all prior CPU/GPU works by 9.5× to 456× and provides a practical performance for our target application: secure training of logistic regression models. / 2025-01-16T00:00:00Z

Les schémas de Chiffrement Complètement Homomorphe (FHE) permettent de manipuler des données chiffrées avec grande flexibilité : ils rendent possible l'évaluation de fonctions à travers les couches de chiffrement. Depuis la découverte du premier schéma FHE en 2009 par Craig Gentry, maintes recherches ont été effectuées pour améliorer l'efficacité, atteindre des nouveaux niveaux de sécurité, et trouver des applications et liens avec d'autres domaines de la cryptographie. Dans cette thèse, nous avons étudié en détail ce type de schémas. Nos contributions font état d'une nouvelle attaque de récuperation des clés au premier schéma FHE, et d'une nouvelle notion de sécurité en structures hierarchiques, évitant une forme de trahison entre les usagers tout en gardant la flexibilité FHE. Enfin, on décrit aussi des implémentations informatiques. Cette recherche a été effectuée au sein du Laboratoire de Mathématiques de Versailles avec le Prof. Louis Goubin. / Fully Homomorphic Encryption schemes allow public processing of encrypted data. Since the groundbreaking discovery of the first FHE scheme in 2009 by Craig Gentry, an impressive amount of research has been conducted to improve efficiency, achieve new levels of security, and describe real applications and connections to other areas of cryptography. In this Dissertation, we first give a detailed account on research these past years. Our contributions include a key-recovery attack on the ideal lattices FHE scheme and a new conception of hierarchic encryption, avoiding at some extent betrayal between users while maintaining the flexibility of FHE. We also describe some implementations. This research was done in the Laboratoire de Mathématiques de Versailles, under supervision of Prof. Louis Goubin.