第1页 / 共140页
第2页 / 共140页
第3页 / 共140页
第4页 / 共140页
第5页 / 共140页
第6页 / 共140页
第7页 / 共140页
第8页 / 共140页
Fully Homomorphic Encryption in Real World Applications.pdf
Contents
1 Introduction
1.1 Homomorphic Encryption in Real Applications: Few Case Studies
1.2 Summary of This Book
References
2 Literature Survey
2.1 FHE in Cloud Computing
2.2 Mathematical Background
2.2.1 Somewhat Homomorphic Encryption
2.3 Few Related Works
2.4 FHE in Practical Algorithms
2.5 Conclusion
References
3 Sorting on Encrypted Data
3.1 FHE Comparison Based Sort
3.1.1 Homomorphic Form of Sorting
3.2 Sorting and Security
3.2.1 The CPA Indistinguishability Experiment
3.2.2 Why Comparison Based Sorting is Secured?
3.3 Partition Based Sorting with Index Encryption
3.3.1 Encrypted Array with Encrypted Index
3.3.2 Problems of Recursion on Encrypted Data
3.3.3 Quick Sort Using Encrypted Stack
3.3.4 Encrypted Quick Sort Implementation
3.4 Timing Requirement for Sorting Schemes on Encrypted Data
3.4.1 Performance Analysis of Different Operations
3.4.2 Further Reduction of Recrypt to Introduce Error
3.4.3 Encrypted Insertion Sort
3.5 Conclusion
References
4 Translating Algorithms to Handle Fully Homomorphic Encrypted Data
4.1 Challenges of Executing Encrypted Programs
4.2 Encrypted Variants of Basic Operators
4.3 Encrypted Bitwise and Assignment Operators
4.4 Encrypted Arithmetic Operators
4.4.1 Encrypted Addition and Subtraction
4.4.2 Encrypted Multiplication
4.4.3 Encrypted Division
4.5 Encrypted Relational Operators
4.5.1 Encrypted Comparison Operation
4.5.2 Encrypted Less Than/Greater Than Operator (FHE_Grt and FHE_Less)
4.6 Loop Handling on Encrypted Operations
4.7 Encrypted Program Termination Using Interrupt
4.8 Recursion Handling with Encrypted Operations
4.8.1 Design of Encrypted Stack
4.9 Design of Encrypted Queue
4.10 Design of Encrypted Linked List
4.11 Conclusion
References
5 Secure Database Handling
5.1 Security Issues in Cloud
5.2 Sate of the Art
5.3 Basic Operations for Database Handling and Their Encrypted Variants
5.3.1 INSERT and SELECT Operation
5.3.2 TOP
5.3.3 LIKE
5.3.4 ORDER BY
5.3.5 GROUP BY
5.4 Advanced SQL: Encrypted JOIN
5.5 SQL Injection on Encrypted Database
5.6 Conclusion
References
6 FURISC: FHE Encrypted URISC Design
6.1 Existing Encrypted Processors
6.1.1 Heroic: Partial Homomorphic Encrypted Processor
6.2 Implementing Fully Homomorphic Encrypted Processor Using a Ultimate RISC Instruction
6.2.1 Justification of Encrypted Processor Along with Encrypted Data
6.2.2 Why URISC Architecture in Connection to FHE
6.2.3 Performance Based Challenge
6.3 Design Basics of FURISC
6.3.1 Design of FURISC
6.3.2 Encrypted Memory Module
6.3.3 Encrypted ALU Module
6.3.4 Overall Architecture
6.4 Comparison with MOVE Based URISC
6.4.1 Performance Evaluation: SBN Versus Move FURISC
6.5 FURISC Applied to Realize Encrypted Programs
6.6 Results
6.6.1 Drawback of FURISc
6.7 FHE Processor Implementation Challenges
6.8 Utilizing Compression Technique for FHE Architecture
6.8.1 Run Length Encoding
6.8.2 Proposed Encoding Module
6.8.3 Different Choices of Subsequence Length to Store in RAM
6.9 Conclusion
References
7 Conclusion and Future Work
References
A Lattice Based Cryptography
B LWE Based FHE
B.1 Basics of LWE Based Cryptosystem
B.2 Important LWE Based FHE Schemes
C GSW Based FHE Approach
C.1 Brief Details of Scheme Supporting Bit-Wise Homomorphy
D FHE Based Libraries in Literature
E Attacks on SWHE and FHE
E.1 Passive Attacks Against HE
E.2 Active Attacks Against HE
F Examples of Homomorphic Real World Applications
Bibliography
Computer Architecture and Design Methodologies
Ayantika Chatterjee
Khin Mi Mi Aung
Fully
Homomorphic
Encryption in Real
World Applications
Computer Architecture and Design
Methodologies
Series Editors
Anupam Chattopadhyay, Nanyang Technological University, Singapore, Singapore
Soumitra Kumar Nandy, Indian Institute of Science, Bangalore, India
Jürgen Teich, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU),
Erlangen, Germany
Debdeep Mukhopadhyay, Indian Institute of Technology Kharagpur, Kharagpur,
West Bengal, India
Twilight zone of Moore’s law is affecting computer architecture design like never
before. The strongest impact on computer architecture is perhaps the move from
unicore to multicore architectures, represented by commodity architectures like
general purpose graphics processing units (gpgpus). Besides that, deep impact of
application-specific constraints from emerging embedded applications is presenting
designers with new, energy-efficient architectures like heterogeneous multi-core,
accelerator-rich System-on-Chip (SoC). These effects together with the security,
reliability, thermal and manufacturability challenges of nanoscale technologies are
forcing computing platforms to move towards innovative solutions. Finally, the
emergence of technologies beyond conventional charge-based computing has led to
a series of radical new architectures and design methodologies.
The aim of this book series is to capture these diverse, emerging architectural
innovations as well as the corresponding design methodologies. The scope covers
the following.
Heterogeneous multi-core SoC and their design methodology
Domain-specific architectures and their design methodology
Novel technology constraints, such as security, fault-tolerance and their impact
on architecture design
Novel technologies, such as resistive memory, and their impact on architecture
design
Extremely parallel architectures
More information about this series at http://www.springer.com/series/15213
Ayantika Chatterjee Khin Mi Mi Aung
Fully Homomorphic
Encryption in Real World
Applications
123
Ayantika Chatterjee
Indian Institute of Technology Kharagpur
Kharagpur, India
Khin Mi Mi Aung
Institute for Infocomm Research
A*STAR
Singapore, Singapore
ISSN 2367-3478
Computer Architecture and Design Methodologies
ISBN 978-981-13-6392-4
https://doi.org/10.1007/978-981-13-6393-1
ISSN 2367-3486
(electronic)
ISBN 978-981-13-6393-1
(eBook)
Library of Congress Control Number: 2019930570
© Springer Nature Singapore Pte Ltd. 2019
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part
of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations,
recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission
or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar
methodology now known or hereafter developed.
The use of general descriptive names, registered names,
in this
publication does not imply, even in the absence of a specific statement, that such names are exempt from
the relevant protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in this
book are believed to be true and accurate at the date of publication. Neither the publisher nor the
authors or the editors give a warranty, express or implied, with respect to the material contained herein or
for any errors or omissions that may have been made. The publisher remains neutral with regard to
jurisdictional claims in published maps and institutional affiliations.
trademarks, service marks, etc.
This Springer imprint is published by the registered company Springer Nature Singapore Pte Ltd.
The registered company address is: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721,
Singapore
Contents
1
2
3
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Homomorphic Encryption in Real Applications:
Few Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Summary of This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Literature Survey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1 FHE in Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Mathematical Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Somewhat Homomorphic Encryption . . . . . . . . . . . . . . .
2.3 Few Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 FHE in Practical Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sorting on Encrypted Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 FHE Comparison Based Sort . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Homomorphic Form of Sorting . . . . . . . . . . . . . . . . . . . .
3.2 Sorting and Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 The CPA Indistinguishability Experiment . . . . . . . . . . . .
3.2.2 Why Comparison Based Sorting is Secured? . . . . . . . . . .
3.3 Partition Based Sorting with Index Encryption . . . . . . . . . . . . . .
3.3.1 Encrypted Array with Encrypted Index . . . . . . . . . . . . . .
3.3.2 Problems of Recursion on Encrypted Data . . . . . . . . . . .
3.3.3 Quick Sort Using Encrypted Stack . . . . . . . . . . . . . . . . .
3.3.4 Encrypted Quick Sort Implementation . . . . . . . . . . . . . . .
3.4 Timing Requirement for Sorting Schemes on Encrypted
Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Performance Analysis of Different Operations . . . . . . . . .
3.4.2 Further Reduction of Recrypt to Introduce Error . . . . . . .
1
3
6
7
9
9
10
12
16
18
18
19
23
25
27
28
28
30
31
32
32
34
36
37
38
39
v
vi
4
5
Contents
3.4.3 Encrypted Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Translating Algorithms to Handle Fully Homomorphic
Encrypted Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1 Challenges of Executing Encrypted Programs . . . . . . . . . . . . . . .
4.2 Encrypted Variants of Basic Operators . . . . . . . . . . . . . . . . . . . .
4.3 Encrypted Bitwise and Assignment Operators . . . . . . . . . . . . . . .
4.4 Encrypted Arithmetic Operators . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 Encrypted Addition and Subtraction . . . . . . . . . . . . . . . .
4.4.2 Encrypted Multiplication . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3 Encrypted Division . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Encrypted Relational Operators . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1 Encrypted Comparison Operation . . . . . . . . . . . . . . . . . .
4.5.2 Encrypted Less Than/Greater Than Operator
(FHE_Grt and FHE_Less) . . . . . . . . . . . . . . . . . . . . . . .
4.6 Loop Handling on Encrypted Operations . . . . . . . . . . . . . . . . . .
4.7 Encrypted Program Termination Using Interrupt . . . . . . . . . . . . .
4.8 Recursion Handling with Encrypted Operations . . . . . . . . . . . . .
4.8.1 Design of Encrypted Stack . . . . . . . . . . . . . . . . . . . . . . .
4.9 Design of Encrypted Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.10 Design of Encrypted Linked List . . . . . . . . . . . . . . . . . . . . . . . .
4.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Secure Database Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1 Security Issues in Cloud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Sate of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Basic Operations for Database Handling and Their Encrypted
Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 INSERT and SELECT Operation . . . . . . . . . . . . . . . . . .
5.3.2 TOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.3 LIKE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.4 ORDER BY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.5 GROUP BY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Advanced SQL: Encrypted JOIN . . . . . . . . . . . . . . . . . . . . . . . .
5.5 SQL Injection on Encrypted Database . . . . . . . . . . . . . . . . . . . .
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
45
46
49
50
50
52
52
52
53
53
55
55
57
58
62
64
65
65
65
69
70
71
72
72
76
77
80
82
82
82
83
84
85
85
Contents
6
FURISC: FHE Encrypted URISC Design . . . . . . . . . . . . . . . . . . . .
6.1 Existing Encrypted Processors . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Heroic: Partial Homomorphic Encrypted Processor . . . . .
6.2 Implementing Fully Homomorphic Encrypted Processor
Using a Ultimate RISC Instruction . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Justification of Encrypted Processor Along with
Encrypted Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.2 Why URISC Architecture in Connection to FHE . . . . . . .
6.2.3 Performance Based Challenge . . . . . . . . . . . . . . . . . . . . .
6.3 Design Basics of FURISC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.1 Design of FURISC . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.2 Encrypted Memory Module . . . . . . . . . . . . . . . . . . . . . .
6.3.3 Encrypted ALU Module . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.4 Overall Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4 Comparison with MOVE Based URISC . . . . . . . . . . . . . . . . . . .
6.4.1 Performance Evaluation: SBN Versus Move
vii
87
87
88
90
91
91
92
94
95
96
97
98
99
FURISC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.5 FURISC Applied to Realize Encrypted Programs . . . . . . . . . . . . 101
6.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.6.1 Drawback of FURISc . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.7 FHE Processor Implementation Challenges . . . . . . . . . . . . . . . . . 107
6.8 Utilizing Compression Technique for FHE Architecture . . . . . . . 108
6.8.1 Run Length Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.8.2 Proposed Encoding Module . . . . . . . . . . . . . . . . . . . . . . 108
6.8.3 Different Choices of Subsequence Length
to Store in RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7
Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Appendix A: Lattice Based Cryptography . . . . . . . . . . . . . . . . . . . . . . . . 119
Appendix B: LWE Based FHE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Appendix C: GSW Based FHE Approach. . . . . . . . . . . . . . . . . . . . . . . . . 127
Appendix D: FHE Based Libraries in Literature . . . . . . . . . . . . . . . . . . . 131
Appendix E: Attacks on SWHE and FHE . . . . . . . . . . . . . . . . . . . . . . . . 135
Appendix F: Examples of Homomorphic Real World Applications . . . . 139
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
