Homomorphic Encryption For Secure Data Computations
AIN SHAMS UNIVERSITYFACULTY OF ENGINEERINGComputer and Systems EngineeringHomomorphic Encryption for Secure Data ComputationsA Thesis submitted in partial fulfillment of the requirements ofMaster of Science in Electrical Engineering(Computer and Systems Engineering)byMohamed Tarek Ibn Ziad Mohamed HassanBachelor of Science in Electrical Engineering(Computer and Systems Engineering)Faculty of Engineering, Ain Shams University, 2014Supervised ByDr. Hassan Mohamed Shehata BedourDr. Yousra Mohsen Ali AlkabaniCairo, 2017
AIN SHAMS UNIVERSITYFACULTY OF ENGINEERINGComputer and Systems EngineeringExaminers’ CommitteeName: Mohamed Tarek Ibn Ziad Mohamed HassanThesis: Homomorphic Encryption for Secure Data ComputationsDegree: Master of Science in Electrical Engineering (Computer and Systems Engineering)Name and affiliationProf. Dr. Hossam Aly Hassan FahmyProf. at Electronics and Communications Engineering Dept.Signature.Faculty of Engineering, Cairo University.Prof. Dr. Mohamed Watheq Ali Kamel El-KharashiProf. at Computer and Systems Engineering Dept.Faculty of Engineering, Ain shams University.Dr. Hassan Mohamed Shehata BedourAssociative Prof. at Computer and Systems Engineering Dept.Faculty of Engineering, Ain shams University.Date: June 2017
StatementThis Thesis is submitted as a partial fulfillment of Master of Science inElectrical Engineering, Faculty of Engineering, Ain shams University.The author carried out the work included in this Thesis, and no part of ithas been submitted for a degree or a qualification at any other scientificentity.Mohamed Tarek Ibn Ziad Mohamed HassanSignature.Date: 01 June 2017
Researcher DataName: Mohamed Tarek Ibn Ziad Mohamed HassanDate of Birth: 25/06/1992Place of Birth: Cairo, EgyptLast academic degree: Bachelor of ScienceField of specialization: Electrical EngineeringUniversity issued the degree : Ain Shams UniversityDate of issued degree : 07/2014Current job : Teaching Assistant at the Faculty of Engineering, Ain Shams University
AbstractThe tremendously increasing amount of the available data nowadays opens the door to usingthird parties to handle data storage and processing. This raises many concerns regarding endusers’ privacy and whether the targeted third parties are trusted or not. On the one hand, endusers, either clients or organizations, cannot afford the cost and complexity of processing theirown data by their local trusted components. On the other hand, depending only on third parties,such as cloud computing services, with no security guarantee in mind, will be more like buildingcastles out of mud. One possible solution for the former issue is using homomorphic encryption(HE) techniques. These techniques allow third party services to compute over data while thedata itself remains encrypted. Thus, one can make use of the great computational power offeredby third parties without sacrificing his/her own privacy.HE could be categorized into two main categories; partially homomorphic encryption (PHE),and fully homomorphic encryption (FHE). While FHE can help solve privacy issues completely,it introduces high performance overhead. To avoid such overhead, PHE can be used. Thus, themain goal of this Thesis is to “explore the efficiency of using PHE techniques in solving realworld problems, in which computing over encrypted data is a must”.The contributions of this Thesis are multi-fold. We selected three different domains of applications; securing electronic voting (e-voting) systems, defeating Hardware Trojans (HTs) inFPGA-based designs, and operating blindly over encrypted images. The common part of allthe above different domains is the availability of secure data that needs to be processed by thirdparties without being revealed.In the context of securing e-voting systems, we implement an FPGA-based e-voting system,which uses a VGA screen and a Xilinx Spartan 3E FPGA board as a voting site and a remoteserver to collect results. We launch a couple of attacks on the system by injecting an HT inour e-voting machine to tamper with the voting results. We show the role of HE in securingour design via the usage of ElGamal cryptosystem. Protection techniques are proposed andimplemented. Then, they are evaluated by showing their delay, power, and area overheads. Thereported power overhead is negligible, the delay overhead does not exceed 10%, and the deviceresources overhead does not exceed 4%.In the context of defeating HTs in FPGA-based designs, we implement two designs that supportPHE (multiplicative only and additive only) based on ElGamal encryption/decryption scheme.Furthermore, we integrate the two designs together and introduce a dual-circuit design thatachieves a higher improvement in area and power than a regular design that combines the twooriginal separated designs. Our architectures are implemented on a Spartan-6 FPGA board fromXilinx. The area reduction reached 30% and savings in power consumption were 20% for encryption and 12% for decryption.
xIn the context of operating blindly over encrypted images, we introduce CryptoImg, a library ofmodular privacy preserving image processing operations over encrypted images using the homomorphic properties of Paillier cryptosystem. Secure operations, such as image adjustment, spatial filtering, edge sharpening, edge detection, morphological operations, and histogram equalization, are safely outsourced to third-party servers with no privacy issues. We present howthese operations can be implemented with much less time overhead, and a single communication round. CryptoImg can be used from either mobile or desktop clients with low client-sideoverheads. Experiments show the efficiency of our proposed library. For instance, the imagenegation operation in the encrypted domain requires less than one minute with zero error using1024-bit key size.To conclude, the Thesis successfully managed to show the efficiency of using PHE techniques,such as ElGamal and Paillier, as a replacement of FHE ones in three different real-world problems, which require computing over encrypted data. The overheads accompanied by using suchtechniques are reasonable compared to the huge overheads of the FHE techniques reported inthe literature.
SummaryEncryption is the art of converting text messages into a secret code using a certain encryptionkey. Hundreds of years ago, people used to propose new encryption algorithms to secure theirown data and protect their privacy. Unfortunately, once the data is encrypted, it would remainin its secret-useless form till a certain key is used to decrypt it. Homomorphic encryption is thekind of encryption that permits one to perform useful computations on encrypted data withoutdecrypting them. The results of these computations are equivalent to the results of the similarcomputations done over the plain data. By this way, one could safely allow third parties to makeuseful computations over his own data without scarifying his privacy.Building on the above description, the Thesis aims at exploring the efficiency of using homomorphic encryption techniques in solving real-world problems, in which computing over encrypteddata is a must. Although homomorphic encryption includes two different categories; the fullyhomomorphic encryption techniques, and the partially homomorphic encryption ones, the Thesis focuses on the second category only. The reason behind this research direction is to avoidthe high overheads associated with the usage of fully homomorphic encryption methods.The Thesis is divided into six chapters, along with the table of contents, list of figures, list oftables, abbreviations, symbols, and the references.The Thesis contents are presented hereafter.Chapter 1 presents the introduction to the Thesis. It mainly highlights the motivation behind theproposed work. It also states the Thesis contributions, which span through three different applications. Each contribution/application is illustrated in a separate chapter with its experimentalsetup and numerical results.Chapter 2 describes the needed background about homomorphism and surveys existing fully andpartially homomorphic encryption schemes. It mainly focuses on the two partially homomorphiccryptosystems, used in this work; ElGamal and Paillier.Chapter 3 illustrates the first Thesis contribution, which is using homomorphism in E-votingsystems. It introduces a couple of possible attacks and countermeasures to an FPGA-based voting machine. The full hardware implementation is described and the countermeasures overheadsare highlighted.Chapter 4 introduces the second contribution, which is securing FPGA-based designs fromHardware Trojans using homomorphism. The Thesis implements two partially homomorphicencryption designs based on ElGamal encryption/decryption scheme. The first design is a multiplicative homomorphic, whereas the second one is an additive homomorphic. The designrealization on a low-cost FPGA is described and the area/timing results are reported.
xiiChapter 5 describes the third contribution, which is a cloud-based library, CryptoImg, whichallows performing image processing operations over encrypted images. New algorithms areintroduced and the communication/computation overhead are stated using various test cases.Chapter 6 concludes the work, states the list of contributions, and discusses some possible futurework directions.KeywordsElectronic voting, ElGamal Encryption, Fully homomorphic encryption, Hardware Trojans, Homomorphism, Image Processing, Paillier Encryption, Partially homomorphicencryption, Secure computations.
AcknowledgmentAll praise is due to Allah, Most Merciful, the Lord of the Worlds, Who taught man whathe knew out. I would like to thank God almighty for bestowing upon me the chance,strength and ability to complete this work.I always struggle writing acknowledgments because words cannot do justice to my gratitude. However, I will do my best. I wish to express my deep gratitude to my advisors,Dr. Hassan Mohamed Shehata Bedour and Dr. Yousra Mohsen Ali Alkabani for theirguidance and important remarks on the developed results and the written manuscript.I was greatly inspired by their excitement, vision, and creativity. I would also like tothank Prof. Mohamed Watheq Ali Kamel El-Kharashi for his constant and enthusiasticsupport.I would also like to thank the following researchers from University of California LosAngeles (UCLA ), Amr Alanwar, Moustafa Alzantot, and Mani Srivastava, for theirhelp on the development and review of CryptoImg, discussed in Chapter 5.I am always thankful to my parents for their unfailing help along my life and for theirefforts during the Thesis development. I am also thankful to my wonderful friends whomake me enjoy a lot of aspects of life outside of work.Mohamed Tarek Ibn Ziad Mohamed HassanComputer and Systems Engineering DepartmentFaculty of EngineeringAin Shams UniversityCairo, EgyptJune 2017
ContentsAbstractixSummaryxiAcknowledgmentxiiiTable of ContentsxivList of FiguresxixList of TablesxxiList of AbbreviationsxxiiiList of Symbolsxxv1Introduction1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2 Main Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . .2Background2.1 Fully Homomorphic Encryption (FHE) . . .2.2 Partially Homomorphic Encryption (PHE) .2.2.1 ElGamal Scheme . . . . . . . . . .2.2.2 CRT-based ElGamal (CEG) Scheme2.2.3 Paillier Cryptosystem . . . . . . . .2.3 Hardware Trojan . . . . . . . . . . . . . .2.4 Hardware Trojan Taxonomy . . . . . . . .2.4.1 Phase of Insertion . . . . . . . . . .2.4.2 Level of Abstraction . . . . . . . .2.4.3 Methods of Activation . . . . . . .2.4.4 Effects . . . . . . . . . . . . . . .2.4.5 Location . . . . . . . . . . . . . .3E-voting Attacks and Countermeasuresxv.11235578991111111415161617
xviTable of Contents3.13.23.33.43.53.63.73.845Motivation . . . . . . . . . . . . . . . . . . . .Related Work . . . . . . . . . . . . . . . . . .E-voting System Overview . . . . . . . . . . .Scenario for a Possible Attack . . . . . . . . .Protection Against Proposed Attack . . . . . .Other Attacks and Countermeasures . . . . . .3.6.1 Sequence Cheat Code Attack . . . . . .3.6.2 Used Bits Attack . . . . . . . . . . . .Evaluation . . . . . . . . . . . . . . . . . . . .3.7.1 Experimental Setup . . . . . . . . . . .3.7.2 E-voting Protection Results . . . . . .3.7.2.1 Resetting Unused Bits . . . .3.7.2.2 Using Enhanced SB MethodConclusion . . . . . . . . . . . . . . . . . . .Homomorphic Data Isolation for Protection against Hardware Trojans4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.3 HT Protection using PHE Overview . . . . . . . . . . . . . . . . . .4.4 HT Protection using PHE Methods . . . . . . . . . . . . . . . . . . .4.4.1 Sufficient PHE Support . . . . . . . . . . . . . . . . . . . . .4.4.1.1 ElGamal Scheme Implementation . . . . . . . . . .4.4.1.2 CEG Scheme Implementation . . . . . . . . . . . .4.4.2 Dual-Circuit Design . . . . . . . . . . . . . . . . . . . . . .4.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.5.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . .4.5.2 PHE Methods Results . . . . . . . . . . . . . . . . . . . . .4.5.3 Dual-Circuit Design Results . . . . . . . . . . . . . . . . . .4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .CryptoImg: Privacy Preserving Processing over Encrypted Images5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . .5.3 CryptoImg System Overview . . . . . . . . . . . . . . . . . . .5.4 Secure Operations in Encrypted Domain . . . . . . . . . . . . .5.4.1 Secure Image Adjustment . . . . . . . . . . . . . . . .5.4.2 Secure Noise Reduction . . . . . . . . . . . . . . . . .5.4.3 Secure Edge Detection and Sharpening . . . . . . . . .5.4.4 Secure Morphological Operations . . . . . . . . . . . .5.4.5 Secure Histogram Equalization . . . . . . . . . . . . . .5.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.5.1 Experimental Setup . . . . . . . . . . . . . . . . . . . .5.5.2 Visual Output Results . . . . . . . . . . . . . . . . . .5.5.3 Computation Time Results . . . . . . . . . . . . . . . .5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 41424245.474849505252535455565656575961
xviiTable of Contents6Conclusion and Future Work6.1 Conclusion . . . . . . . . . . . . .6.2 Contributions . . . . . . . . . . . .6.2.1 Secure E-voting . . . . . . .6.2.2 Secure FPGA-based Designs6.2.3 Secure Image Processing . .6.3 Future Work . . . . . . . . . . . . .6.3.1 Secure E-voting . . . . . . .6.3.2 Secure FPGA-based Designs6.3.3 Secure Image Processing . .Bibliography.6363636464646565656567
List of Figures2.12.2Possible stages for launching Hardware Trojan attacks by third parties. .Hardware Trojan taxonomy. . . . . . . . . . . . . . . . . . . . . . . .1213E-voting versus regular voting. . . . . . . . . . . . . . . . . . . . . . .The e-voting process. . . . . . . . . . . . . . . . . . . . . . . . . . . .Abstract view of our proposed e-voting machine. . . . . . . . . . . . .MicroBlaze block diagram. . . . . . . . . . . . . . . . . . . . . . . . .Block diagram of using a malicious secret core within an untrusted evoting machine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.6 Simple obfuscating function depending on data xoring. . . . . . . . . .3.7 Inverse obfuscating function in order to retrieve data. . . . . . . . . . .3.8 E-voting protection against proposed attack. . . . . . . . . . . . . . . .3.9 Experimental setup for the e-voting system. . . . . . . . . . . . . . . .3.10 The Xilinx Spartan 3E starter kit overview. . . . . . . . . . . . . . . . 5252829Homomorphic encryption to protect from Hardware Trojans. . . . . . .Block diagram for ElGamal encryption/decryption scheme. . . . . . . .Block diagram for the CRT-based ElGamal (CEG) encryption/decryption scheme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3738System Architecture of CryptoImg. . . . . . . . . . . . . . . . . . . .The different edge detection operators supported by CryptoImg. . . . .Visual output evaluation for the first operations set applied in PD and ED.Visual output evaluation for the second operations set applied in PD andED. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .515457xix4058
List of Tables3.13.23.33.4Device utilization comparison for resetting unused bits method. . . . .Power comparison for resetting unused bits method. . . . . . . . . . .Device utilization comparison for enhanced Simple Blockage method.Power comparison for enhanced Simple Blockage method. . . . . . .303031314.14.24.3Resource utilization of ElGamal and CEG schemes. . . . . . . . . . . .Timing performance of ElGamal and CEG schemes. . . . . . . . . . . .Power consumption (mW) of ElGamal and CEG encryption/decryptionschemes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Area reduction of our dual ElGamal design over the regular ElGamaldesign. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Timing comparisons between our dual ElGamal design and the regularElGamal design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Power consumption (mW) of our dual ElGamal design and the regularElGamal design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4242Precision effect on the introduced CryptoImg error. . . . . . . . . . . .Execution Time (sec) of the Paillier encryption/decryption of an image.Execution Time (sec) of the proposed CryptoImg operations on different clients. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59604.44.54.65.15.25.3xxi4343444460
List of AbbreviationsAESAdvanced Encryption StandardASICApplication Specific Integrated CircuitCBIRContent-Based Image RetrievalCEGCRT-based ElGamalCRCCyclic Redundancy CheckCRTChinese Remainder TheoremDCRDecisional Composite ResiduosityDLPDiscrete Logarithm ProblemDoSDenial of ServiceEDEncrypted DomainEDAElectronic Design AutomationEMEstimation MaximizationENEncoding FunctionE-votingElectronic votingEVMElectronic Voting MachineFHEFully Homomorphic EncryptionFPFloating PointFSMFinite State MachineFSLFast Simplex LinkHTHardware TrojanIPIntellectual PropertyISEIntegrated Synthesis EnvironmentJTAGJoint Test Action GroupLPFLow Pass FilterLWELearning With Errorsxxiii
xxivList of AbbreviationsMobMobile deviceNLMNon-Local MeansOSOperating SystemPCPersonal ComputerPDPlaintext DomainPHEPartially Homomorphic EncryptionPCBPrinted Circuit BoardRORing OscillatorsRISCReduced Instruction Set ComputerRLWERing Learning With ErrorsRNSResidue-Number SystemRSARivest-Shamir-AdlemanRTLRegister Transfer LevelSaaSSoftware-as-a-ServiceSBSimple BlockageSIFTScale-Invariant Feature TransformSMCSecure Multi-party ComputationSRAMStatic Read Access MemoryS
the above different domains is the availability of secure data that needs to be processed by third parties without being revealed. In the context of securing e-voting systems, we implement an FPGA-based e-voting system, which uses a VGA screen and a Xilinx Spartan 3E FPGA board as a voting site and a remote server to collect results.
unauthorized users. This paper defines endpoint encryption, describes the differences between disk encryption and file encryption, details how disk encryption and removable media encryption work, and addresses recovery mechanisms. What is Endpoint Encryption? When it comes to encrypting data, there are various encryption strategies.
Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original
Poseidon. It implements all the basic operations of the CKKS-alike FHE algorithm, including homomorphic addition, homomorphic mulitplication, rescale, rotation, keyswitch, modup/down and even the expensive bootstrapping. Widely supported operations enable Poseidon applicable for more complex FHE applications that require a larger multiplicative
Encryption Email Encryption The McAfee Email Gateway includes several encryption methodologies: Server-to-server encryption Secure Web Mail Pull delivery Push delivery The encryption features can be set up to provide encryption services to the other scanning features, or can be set up as an encryption-only server used just
algorithm based on secure multi-party com-putation and homomorphic encryption. Their neural networks are composed of a succession of scalar products which are secured on the basis of homomorphic encryption and activa-tion functions (threshold or sigmoid) secured with protocols based on secure
Nov 26, 2001 · 1. Name of Standard. Advanced Encryption Standard (AES) (FIPS PUB 197). 2. Category of Standard. Computer Security Standard, Cryptography. 3. Explanation. The Advanced Encryption Standard (AES) specifies a FIPS-approved cryptographic algorithm that can be used to protect electronic data. The AES algorithm is aFile Size: 1MBPage Count: 51Explore furtherAdvanced Encryption Standard (AES) NISTwww.nist.govAdvanced Encryption Standard - Wikipediaen.wikipedia.orgAdvanced Encryption Standard - Tutorialspointwww.tutorialspoint.comWhat is Data Encryption Standard?searchsecurity.techtarget.comRecommended to you b
Full disk encryption (FDE), file/folder encryption, USB encryption and email encryption are all supported features. FULLY VALIDATED ESET Endpoint Encryption is FIPS 140-2 validated with 256-bit AES encryption. ALGORITHMS & STANDARDS AES 256 bit, AES 128 bit, SHA 256 bit, SHA1 160 bit, RSA 1024 bit, Triple DES 112 bit, Blowfish 128 bit. OS SUPPORT Support for Microsoft Windows 10, 8, 8.1 .
2.5.4 Chaos-Based Image Encryption Algorithm 47 2.5.5 Analysis and Comparison of Image Encryption Algorithms 48 2.5.6 Image Encryption Using Fractional Fourier Transform and 3d Jigsaw Transform 48 2.5.7 Image Encryption for Secure Internet Multimedia Applications 49 2.5.8 Image and Video Encryption Using Scan Patterns 50 2.5.9 A New Chaotic .
