Explore a groundbreaking talk on faster fully homomorphic encryption, focusing on bootstrapping in less than 0.1 seconds. Delve into advanced cryptographic concepts including boolean circuit evaluation, homomorphic encryption, and concrete lattice parameters. Learn about TLWE linear morphisms, supporting polynomials, and non-linear operations. Examine unusual facts about GSW and the external product semantics. Discover techniques for speeding up encryption processes, choosing base gates, and mapping binary decision diagrams. Investigate FHE compilation for TGSW, leveled overall bootstrapping, and the NAND operation. Analyze the ACCUM protocol, bootstrapping algorithm, and overall improvements in this award-winning presentation from Asiacrypt 2016.
Faster Fully Homomorphic Encryption - Bootstrapping in Less Than 0.1 Seconds
Overview
Syllabus
Intro
BOOLEAN CIRCUIT EVALUATION
HOMOMORPHIC CIRCUIT EVALUATION
HOMOMORPHIC ENCRYPTION
CONCRETE LATTICE PARAMETERS THE DEVELOPER'S NIGHTMARE
PARAMETERS: USER POINT OF VIEW
TLWE CONCRETE INSTANTIATION
SECURITY CURVE
A FEW PRECISIONS
TLWE LINEAR MORPHISM
SUPPORTING POLYNOMIALS
SUPPORTING NON-LINEAR OPERATIONS
UNUSUAL FACTS ABOUT GSW
THE EXTERNAL PRODUCT SEMANTIC
SPEEDUP
CHOOSE BASE GATES
MAP BINARY DECISION DIAGRAMS
FHE COMPILATION FOR TGSW
LEVELED OVERALL
BOOTSTRAPPING: (GENTRY2009)
NAND: ADD AND SELECT (DM15/BR15)
THE ACCUM PROTOCOL (REVISITED)
BOOTSTRAPPING ALGORITHM
OVERALL IMPROVEMENTS
CONCLUSION
Taught by
TheIACR
