CSE208: Advanced Cryptography
CSE208:AdvancedCryptographyCSE208: Advanced CryptographyDanieleMicciancioIntroductionDefining FHEBootstrappingDaniele MicciancioUCSDLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTFall 2020
uctionDefining FHESection 1BootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTIntroduction
CSE208: Advanced iancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTGraduate Level Advanced CryptographyPrerequisites:CSE207 or equivalentSolid theoretical background, cryptographic definitions, etc.Some programming
CSE208: Advanced iancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTGraduate Level Advanced CryptographyPrerequisites:CSE207 or equivalentSolid theoretical background, cryptographic definitions, etc.Some programmingPast topics: Zero Knowledge, Functional Encryption,Secure Computation, etc.Not required: CSE206A (Lattice Algorithms)
CSE208: Advanced iancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingGraduate Level Advanced CryptographyPrerequisites:CSE207 or equivalentSolid theoretical background, cryptographic definitions, etc.Some programmingPast topics: Zero Knowledge, Functional Encryption,Secure Computation, etc.Not required: CSE206A (Lattice Algorithms)MultiplicationFHE!!Project InfoRing LWEANTReading:no textbookmostly research paperssee course webpage, canvas, etc.
Fall 2020 ntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTFully Homomorphic Encryption:Encryption schemes that supports the evaluation ofarbitrary programs on encrypted inputsApplications:secure outsourced computingbuilding block for MPC and more
Brief History of Homomorphic ncioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANT1978: Rivest, Adleman & Dertouzos posed the problem2009: Gentry 2009 proposed the first candidate solution2010-2020: Work towards more efficient solutions based onstandard complexity assumptions (Brakerski,Vaikuntanathan, Gentry, Halevi, Smart, . . . )
Software cioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTIBM HElib (Halevi & Shoup)Microsoft SEALNJIT/Duality PALISADE (Rohloff, Cousins & Polyakov)Functional Lattice Cryptography LoL (Crockett & Peikert)Fastest FHE of the West FHEW (Ducas & Micciancio)FHE over the Torus TFHE (Chillotti, Gama, Georgieva &Izabachene)Approximate FHE HEAAN (Cheon, Kim, Kim & Song)
Software cioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTIBM HElib (Halevi & Shoup)Microsoft SEALNJIT/Duality PALISADE (Rohloff, Cousins & Polyakov)Functional Lattice Cryptography LoL (Crockett & Peikert)Fastest FHE of the West FHEW (Ducas & Micciancio)FHE over the Torus TFHE (Chillotti, Gama, Georgieva &Izabachene)Approximate FHE HEAAN (Cheon, Kim, Kim & Song)In the News:February 21, 2019: Microsoft SEAL open sourcehomomorphic encryption library gets even better for .NETdevelopers!June 4, 2020: IBM releases FHE toolkit for MacOS andiOS; Linux and Android Coming Soon
Homework and ncioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTHomework assignments:3 assignments, due within one week from assignment dateCover theoretical/mathematical topics
Homework and ncioIntroductionDefining FHEHomework assignments:3 assignments, due within one week from assignment dateCover theoretical/mathematical topicsBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTSmall Project:Goal: Try to use one of the many HE librariesNot much coding, but you will have to write and compile afew lines of codeEvaluated primarily based on written report
cciancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTCourse webpage: http://cseweb.ucsd.edu/classes/fa20/general course informationpointers to papers and other reading materialCanvas:recording of lectureshomework distribution/collectiongradesdiscussion board
Course Schedule ancioIntroductionDefining FHEWeek 1: Introduction and DefinitionFHE DefinitionGentry’s Boostrapping theoremHomework 1 outBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTWeek 2-4: Fundamental techniques based on general latticesLWE encryptionLinear Homomorphic computationsKey Switching and Proxy re-encryptionNested encryption and homomorphic multiplicationCiphertext Tensoring and homomorphic multiplicationHomomorphic Decryption and Bootstrapping algorithmsHomework 2 out
uctionDefining FHEBootstrappingLWEWeek 5: Algebraic Number TheoryI really hope you like math!Homework 3 outWeek 6-10: Efficient FHE from Ring LWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTMessage packing techniquesLinear transformations on structured matricesOther FHE schemes: GHS, BFV,FHEW, AP13, TFHE,CKKS . . .
uctionDefining FHESection 2BootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTDefining FHE
Public Key ncioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTPKE ( Gen , Enc , Dec )Gen : () ( pk , sk )Enc : ( pk , m ) cDec : ( sk , c ) m
Correctness of roductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTFor every (sk,pk) Gen() and m [M], r [R]:Dec ( sk , Enc ( pk , m ; r ) ) m
Chosen Plaintext Attack (CPA) ioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTCiphertext Indistinguishability under Chosen PlaintextAttackExperiment:INDCPAgame ( b :{0 ,1})( sk , pk ) Gen ()A ( pk ) (m0 ,m1 )b ' A ( Enc ( pk ,mb ) )return b ':{0 ,1}
Chosen Plaintext Attack (CPA) ioIntroductionDefining FHEBootstrappingLWECiphertext Indistinguishability under Chosen PlaintextAttackExperiment:INDCPAgame ( b :{0 ,1})( sk , pk ) Gen ()A ( pk ) (m0 ,m1 )b ' A ( Enc ( pk ,mb ) )return b ':{0 ,1}LinearityKey SwitchingDefinitionMultiplicationFHE!!Adv ( A ) Pr ( Game (0) 1) - Pr ( Game (1) 1) Project InfoRing LWEANTDefinitionAn encryption scheme (Gen,Enc,Dec) is IND-CPA secure if anypolynomial time A has advantage Adv(A) 0
Significance of CPA ioIntroductionAdversary can choose messages m0 , m1No assumption about input distributionAdversary may have partial information about messagesAdversary may influence the choice of messagesDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTCiphertext c Enc(pk,mb ) is computed honestlyAdversary cannot tamper with ciphertextsAdversary models a passive attacker
Definition of CCA ioDefinitionAn encryption scheme (Gen,Enc,Dec) is IND-CCA secure if anypolynomial time A has advantage Adv(A) 0 in the followinggame.IntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationGame ( b :{0 ,1})( sk , pk ) Gen ()A [ D ]( pk ) (m0 ,m1 )c Enc ( pk ,mb )b ' A [D ']( c )return b ':{0 ,1}FHE!!Project InfoRing LWEANTA[D] is an adversary with oracle access toD ( x ) Dec ( sk , x )A[D'] uses a modified oracle (next slide)
IND-CCA1 vs ioIntroductionDefining FHEBootstrappingLWEThere are two variants of CCA security, depending on the typeof oracle given to the adversary after receiving the challengeciphertext:IND-CCA1 security: No decryption oracle after receivingthe challengeD '( x ) NilLinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTIND-CCA2 security: decrypt any ciphertext, except thechallenge cD '( x ) ?if ( x c )then Nilelse Dec ( sk , x )
Significance of CCA ioIntroductionGoal: model active attacks, where adversary can tamperwith ciphertextsStandard notion for regular encryption schemesDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTIND-CCA2 theoretically equivalent to non-malleableencryptionAny attempt to modify a ciphertext should be detected
Significance of CCA ioIntroductionGoal: model active attacks, where adversary can tamperwith ciphertextsStandard notion for regular encryption schemesDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationIND-CCA2 theoretically equivalent to non-malleableencryptionAny attempt to modify a ciphertext should be detectedSeems incompatible with homomorphic encryptionFHE!!Project InfoRing LWEAbility to modify ciphertexts can be a useful featureHomomorphic encryption is perfectly malleableANTWe will not consider CCA security
Homomorphic Encryption: first oIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTAssume f: M Mf ( Enc ( pk , m ) ) Enc ( pk , f ( m ) )Eval ( pk ,f , Enc ( pk , m ) ) Enc ( pk , f ( m ) )
Homomorphic Encryption: second oIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTDec ( sk , Eval ( pk ,f , Enc ( pk , m ) ) ) f(m)
Multi-input cioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTMany inputs are encrypted independentlyc1 Enc ( pk ,m1 ).ck Enc ( pk ,mk )
Multi-input cioIntroductionMany inputs are encrypted independentlyc1 Enc ( pk ,m1 ).ck Enc ( pk ,mk )Defining FHEBootstrappingk-ary function f: (m1 ,.,mk ) mLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTEval ( pk , f , c1 ,. ,ck ) ) Enc ( pk , f (m1 ,. ,mk ) ) ?Dec ( sk , Eval ( pk , f , c1 ,.ck ) ) f (m1 ,. ,mk )
Multi-key Homomorphic ncioIntroductionDefining FHEBootstrappingAssume multiple users: P1 , P2 , .Each user has a key (pair): Pi : (pki , ski )Data is encrypted and sent to different usersc1 Enc (pk1 ,m1 ).ct Enc (pkt ,mt )LWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTUsers pool data together to perform a joint computation onc1 , ., ct
Multi-key Homomorphic ncioIntroductionDefining FHEBootstrappingAssume multiple users: P1 , P2 , .Each user has a key (pair): Pi : (pki , ski )Data is encrypted and sent to different usersc1 Enc (pk1 ,m1 ).ct Enc (pkt ,mt )LWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTUsers pool data together to perform a joint computation onc1 , ., ctFinal result is an encryption of f (m1 , ., mt ) under whatkey?Eval (? , f ,c1 ,. ,ct ) ) Enc (? , f (m1 ,. ,mt ) )
Restricting Homomorphic ncioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTFHE is a useful and challenging problem already in thesingle key setting
Restricting Homomorphic ncioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTFHE is a useful and challenging problem already in thesingle key settingIn order to appropach the problem we will further restrict itby parametrizing by a set of allowedcomputations/functions Func {f: .} where eachf: (M,.,M) M may take a different number of arguments
Restricting Homomorphic ncioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTFHE is a useful and challenging problem already in thesingle key settingIn order to appropach the problem we will further restrict itby parametrizing by a set of allowedcomputations/functions Func {f: .} where eachf: (M,.,M) M may take a different number of argumentsMore generally, one many consider functionsf:(M1 , ., Mk ) M taking inputs from different sets (types),e.g., ifThenElse: (Bool,Int,Int) Int
Examples and Function ancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANT(M, , 0): abelian group, e.g., “fixed size” integers(modulo N)Addition: f (x1 , .xt ) x1 . xtScalar multiplication: ga (x ) a · xPLinear combinations: h(x1 , .xt ) i 2i 1 xi
Examples and Function ancioIntroductionDefining FHEBootstrappingLWELinearityKey Switching(M, , 0): abelian group, e.g., “fixed size” integers(modulo N)Addition: f (x1 , .xt ) x1 . xtScalar multiplication: ga (x ) a · xPLinear combinations: h(x1 , .xt ) i 2i 1 xi1-hop, n-hop, multi-hop: can functions f be composed?MultiplicationFHE!!Project InfoRing LWEANTh(x1 , ., xt ) f (g1 (x1 ), ., g2t 1 (xt ))
Correctness of Function ancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTLet x , y , z M be messages and f , g : M M twofunctions such that y f (x ) and z g(y ) (g f )(x )Assume (Gen,Enc,Dec,Eval) can evaluate f and g correctly:Dec ( sk , Eval ( pk ,f , Enc ( pk , x ) ) ) f ( x )Dec ( sk , Eval ( pk ,g , Enc ( pk , y ) ) ) g ( y )
Correctness of Function ancioIntroductionDefining FHEBootstrappingLet x , y , z M be messages and f , g : M M twofunctions such that y f (x ) and z g(y ) (g f )(x )Assume (Gen,Enc,Dec,Eval) can evaluate f and g correctly:Dec ( sk , Eval ( pk ,f , Enc ( pk , x ) ) ) f ( x )Dec ( sk , Eval ( pk ,g , Enc ( pk , y ) ) ) g ( y )LWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTQuestionDoes it follow thatctX Enc ( pk , x )ctY Eval ( pk ,f , ctX )ctZ Eval ( pk ,g , ctY )?Dec ( sk , ctZ ) z
Formalizing Restricted ancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTRestrict scheme to a set F of strongly typed functions:f : M1 . . . Mk M0Enc,Dec,Eval are given type information
Formalizing Restricted ancioIntroductionDefining FHEBootstrappingRestrict scheme to a set F of strongly typed functions:f : M1 . . . Mk M0Enc,Dec,Eval are given type informationWe can use types to bound computation depth:LWELinearityKey SwitchingMultiplicationStart from f : M MDefine Mi M for i 1, ., nDefine fi : Mi Mi 1 , where fi (x ) f (x )FHE!!Project InfoRing LWEANTF {f } allows arbitrary compositionF {f0 }: no compositionF {f0 , f1 , ., fn }: bounded depth composition
(Multi-hop) Correctness troductionDefining FHEBootstrappingState: (initially empty) list L of message-ciphertext pairsCorrectFHEgame () ( sk , pk ) Gen ()L []A [E , F ]( pk )(m , c ) last ( L )return ( Dec ( sk , c ) 6 m )LWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTE ( m ) c Enc ( pk , m )L L ;( m , c )return cF (f , I ) ( ms , cs ) unzip L [ I]m f ( ms )c Eval ( pk ,f , cs )L L ;( m , c )return c
ancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTReading papers, you will find references toFully Homomorphic EncryptionSomewhat Homomorphic EncryptionLeveled Fully Homomorphic Encryptionetc.
ancioIntroductionDefining FHEBootstrappingReading papers, you will find references toFully Homomorphic EncryptionSomewhat Homomorphic EncryptionLeveled Fully Homomorphic Encryptionetc.LWELinearityWe will use FHE as a catchall termKey SwitchingMultiplicationFHE!!Project InfoRing LWEDefinition is parametrized by a set of functions FFunctions in F can be composed only if their types matchF is closed under compositionCan use “phantom” types to limit compositionANTWe will rarely define F formally, but it is a useful exercise
Security of Homomorphic ncioIntroductionINDCPAgame ( b :{0 ,1})( sk , pk ) Gen ()A ( pk ) (m0 ,m1 )return A ( Enc ( pk ,mb ) ) : {0 ,1}Defining FHEBootstrappingLWELinearityKey SwitchingRemarkThe IND-CPA security definition depends only on Gen and Enc,but not on Dec (or Eval)MultiplicationFHE!!Project InfoRing LWEANTQuestionCan the IND-CPA security definition be applied as it is to FHEschemes (Gen,Enc,Dec,Eval)?
A trivial FHE IntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTConsider the following FHE scheme:Let (Gen,Enc,Dec) be IND-CPA secureDefine TrivialFHE (Gen,Enc',Dec',Eval)Enc '( pk , m ) ( Enc ( pk , m ) ,[])Dec '( sk ,( ct ,[]) ) Dec ( sk , ct )Dec '( sk ,( ct ,[ f ; fs ]) ) f ( Dec '( sk ,( ct , fs ) ) )Eval ( pk ,f ,( ct ,[ fs ]) ) ( ct ,[ f ; fs ])QuestionIs TrivialFHE a correct FHE scheme?Is TrivialFHE a secure FHE scheme?What makes the above scheme “trivial”?
ancioThe TrivialFHE scheme is both correct and secureThe problem with TrivialFHE is that it is not efficient:IntroductionDefining FHEBootstrappingLWELinearityKey SwitchingComputation is performed by Dec, not Eval!DefinitionA FHE scheme is compact if the size of ciphertextct Eval(pk,f,Enc(pk,m)) is independent of Size(f)MultiplicationFHE!!Project InfoRing LWEANTWeaker forms of compactness:Ciphertext size may grow logarithmic with Size(f)Ciphertext size may depend on Depth(f)
Function oIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTf0 (x , y ) x yf1 (x , y ) y xGame [ A ]( b : {0 ,1})( sk , pk ) Gen ()ctX Enc ( pk , x )ctY Enc ( pk , y )ct Eval ( pk ,fb ,ctX , ctY )return A ( ct )QuestionAssume (Gen,Enc,Dec,Eval) is a secure FHE scheme. Can anefficient adversary A recover the bit b Game[A](b) ?
Passive Attacks to roductionDefining FHEGame [ A ]( b : {0 ,1})( sk , pk ) Gen ()State []b ' A [E ,D , F ]( pk )return b 'BootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTAdversary has access to three stateful oracles:Encryption oracle: E(m0 ,m1 )Function Evaluation oracle: F(f0 ,f1 ,I)Decryption oracle: D(i)Joint State: List of message-message-ciphertext triplets(m0 ,m1 ,ct)
Passive Attack cioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingE (m0 ,m1 ) ct Enc ( pk ,mb )State ( State ;(m0 ,m1 , ct ) )return ctF (f0 ,f1 ,I ) (ms0 ,ms1 , cts ) unzip State [ I ]ct Eval ( pk ,fb , cts )m0 f0 (ms0 )m1 f1 (ms1 )State State ;(m0 ,m1 , ct )return ctMultiplicationFHE!!Project InfoRing LWEANTD ( i ) : (m0 ,m1 , ct ) State [ i ]if (m0 m1 )then return Dec ( sk , ct )else return Nil
Passive Attack with/without function oIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTThe game we just described guarantees function privacyA similar definition without function privacy can beobtained by requiring f0 f1 in the function evaluationqueriesF '( f , I ) : (ms0 ,ms1 , cts ) unzip State [ I ]ct Eval ( pk ,f , cts )m0 f (ms0 )m1 f (ms1 )State ( State ;(m0 ,m1 , ct ) )return ct
Example: Circuit oIntroductionDefining FHEBootstrappingLWELinearityAssume messages are single bits m: {0,1}Let FHE (Gen,Enc,Dec,Eval) a function private FHEscheme supporting NAND(x,y) not (x && y)EvalC(pk,C,.): evaluates boolean circuitC: {0, 1}n {0,1} one gate at a time usingEval(pk,NAND,.)Let C0 , C1 : NAND circuits with the same number ofinputs and NAND gatesKey Switching(sk,ps) Gen()MultiplicationLet xs0 , xs1 be input bits such that C0 (xs0 ) C1 (xs1 )FHE!!Project InfoRing LWEANTQuestionAre the following two distributions indistinguishable?( pk , EvalC ( pk , C0 , Enc ( pk ,xs0 ) ))( pk , EvalC ( pk , C1 , Enc ( pk ,xs1 ) ))
uctionDefining FHESection 3BootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTBootstrapping
ciancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTFor simplicity: fix message space to {0, 1}HE (Gen,Enc,Dec,Eval)Homomorphic functions: Func { nand }Supports only bounded computations: Depth(C) D
ciancioIntroductionDefining FHEBootstrappingFor simplicity: fix message space to {0, 1}HE (Gen,Enc,Dec,Eval)Homomorphic functions: Func { nand }Supports only bounded computations: Depth(C) DLWELinearityKey SwitchingMultiplicationQuestionCan we use HE to build a FHE scheme supporting arbitrarycircuits/functions?FHE!!Project InfoRing LWEANTThe process of building FHE from HE is called“bootstrapping”
Decryption as a boolean ioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTEverything is a sequence of bitsSecret key sk: {0, 1}kCiphertext ct: {0, 1}lDec(sk,ct): {0,1}
Decryption as a boolean ioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTEverything is a sequence of bitsSecret key sk: {0, 1}kCiphertext ct: {0, 1}lDec(sk,ct): {0,1}Usually we think of Dec as a functiondescribed by secret key skmapping ciphertext ct to message bit Dec(sk,ct): {0,1}
Decryption as a boolean ioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationEverything is a sequence of bitsSecret key sk: {0, 1}kCiphertext ct: {0, 1}lDec(sk,ct): {0,1}Usually we think of Dec as a functiondescribed by secret key skmapping ciphertext ct to message bit Dec(sk,ct): {0,1}FHE!!Project InfoRing LWEANTBut we can also think of Dec as a functiondescribed by ciphertext ctmapping secret key sk to message bit Dec(sk,ct): {0,1}
Homomorphic ncioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTFix a ciphertext cDefine fc : sk 7 Dec(sk, c)Assume Size(fc ) S, Depth(fc ) DLet bk[1.k] Enc(pk,sk[1.k])QuestionWhat is the result of the following computation?EvalC ( pk ,fc , bk [1. k ])
Proxy ciancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTPrimary key: (pk,sk)Secondary key: (pk1,sk1)Re-encryption key: rk Enc(pk1,sk[1.k])Input ciphertext c Enc(pk,m)Decryption function fc (sk) Dec(sk,c)QuestionWhat is the result of the following computation?EvalC ( pk1 ,fc , rk )
Decrypt and compute oIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTHomomorphic Encryption (Gen,Enc,Dec,Eval)Assume Func { fc c: CipherText } wherefc ( sk ) not ( Dec ( sk , c ) )
Decrypt and compute oHomomorphic Encryption (Gen,Enc,Dec,Eval)Assume Func { fc c: CipherText } wherefc ( sk ) not ( Dec ( sk , c ) )IntroductionDefining FHEBootstrappingLWE( pk , sk ) Gen ()ek Enc ( pk , sk )c Enc ( pk , m )LinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTQuestionWhat is the result of the following computation?EvalC ( pk ,fc , ek )
Decrypt and compute ioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTHomomorphic Encryption (Gen,Enc,Dec,Eval)Assume Func { fc,c 0 c,c': CipherText } wherefc,c 0 ( sk ) Dec ( sk , c ) nand Dec ( sk ,c ')
Decrypt and compute ioHomomorphic Encryption (Gen,Enc,Dec,Eval)Assume Func { fc,c 0 c,c': CipherText } wherefc,c 0 ( sk ) Dec ( sk , c ) nand Dec ( sk ,c ')IntroductionDefining FHEBootstrappingLWELinearity( pk , sk ) Gen ()ek Enc ( pk , sk )c Enc ( pk , m )c ' Enc ( pk ,m ')Key SwitchingMultiplicationFHE!!Project InfoRing LWEANTQuestionWhat is the result of the following computation?EvalC ( pk ,fc,c 0 , ek )
ciancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTGiven (1-hop) (Gen,Enc,Dec,Eval) supporting functionsfc,c 0 ( sk ) Dec ( sk , c ) nand Dec ( sk ,c ')
ciancioGiven (1-hop) (Gen,Enc,Dec,Eval) supporting functionsfc,c 0 ( sk ) Dec ( sk , c ) nand Dec ( sk ,c ')IntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTDefine (multi-hop) FHE scheme with Func { nand }Gen '() ( sk , pk ) Gen ()ek Enc ( pk , sk )return ( sk ,( pk , ek ) )Enc '(( pk , ek ) ,m ) Enc ( pk , m )Eval '(( pk , ek ) ,nand ,c ,c ') EvalC ( pk ,fc,c 0 , ek )
ancioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTLet (Gen',Enc',Dec,Eval') be the new encryption schemeTheoremIf Dec(sk,c) m and Dec(sk,c') m', thenDec ( sk , Eval '(( pk , ek ) ,nand ,c ,c ') m nand m '
ancioIntroductionDefining FHEBootstrappingLet (Gen',Enc',Dec,Eval') be the new encryption schemeTheoremIf Dec(sk,c) m and Dec(sk,c') m', thenDec ( sk , Eval '(( pk , ek ) ,nand ,c ,c ') m nand m 'LWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTStrong correctness property:Dec ( sk , Eval '(( pk , ek ) ,nand ,c ,c ') Dec ( sk , c ) nand Dec ( sk ,c ')for any ciphertexts c,c' !
ioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTAssume FHE (Gen,Enc,Dec,Eval) is IND-CPA secureBuild new scheme FHE':Gen '() ( sk , pk ) Gen ()ek Enc ( pk , sk )return ( sk ,( pk , ek ) )Enc '(( pk , ek ) ,m ) Enc ( pk , m )Is FHE' IND-CPA secure?
Leveled Homomorphic ncioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTGoal: build a FHE supporting NAND circuits of depth upto L, for any given LKey generation procedure takes L as input:
Leveled Homomorphic ncioIntroductionDefining FHEBootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTGoal: build a FHE supporting NAND circuits of depth upto L, for any given LKey generation procedure takes L as input:Gen '( L ) for ( i 0. L )( sk [ i ] , pk [ i ]) Gen ()for ( i 1. L )ek [ i ] Enc ( pk [ i ] , sk [i -1])sk ' sk [0. L ]pk ' pk [0. L ] , ek [1. L ]return ( sk ' , pk ')Enc '( pk ', m ) Enc ( pk [0] , m )
FHE ntroductionDefining FHEState of the artWe can build leveled FHE from standard LWE assumptionBuilt using bootstrappingInefficient, but better than nothingBootstrappingLWELinearityKey SwitchingOpen problemBuild (non-leveled) FHE from standard LWEIn practice, one can apply bootstrapping withMultiplicationek Enc(pk,sk)FHE!!Much smaller key than leveled FHENo known attacks to circular securityStill, it is not known how to prove securityProject InfoRing LWEANT
uctionDefining FHESection 4BootstrappingLWELinearityKey SwitchingMultiplicationFHE!!Project InfoRing LWEANTLWE
Linear cioIntroductionq: integer modulusZq : integers modulo qA Zn m: matrixqnb ZqDefining FHEBootstrappingLWEProblemGiven A, b, find x Zm such that Ax b (mod q)LinearityKey SwitchingMultiplicationFHE!!ProblemGiven A, b, find x {0, 1}m such that Ax b (mod q)Project InfoRing LWEANTQuestio
Cryptography Daniele Micciancio Introduction DefiningFHE Bootstrapping LWE Linearity KeySwitching Multiplication FHE!! ProjectInfo RingLWE ANT CSE208: AdvancedCryptography DanieleMicciancio UCSD Fall2020. CSE208: Advanced Cryptography Daniele Micciancio Introduction DefiningFH
of public-key cryptography; providing hands-on experience with some of the most common encryption algorithms that are used on the internet today. Modern Cryptography Introduction Outline 1 Introduction 2 Historical Cryptography Caesar Cipher 3 Public{Key Cryptography
Cryptography with DNA binary strands and so on. In terms of DNA algorithms, there are such results as A DNA-based, bimolecular cryptography design, Public-key system using DNA as a one-way function for key distribution, DNASC cryptography system and so on. However, DNA cryptography is an
Cryptography and Java Java provides cryptographic functionality using two APIs: JCA - Java Cryptography Architecture - security framework integrated with the core Java API JCE - Java Cryptography Extension - Extensions for strong encryption (exported after 2000 US export policy)
sensitive information. Even though both cryptography and steganography has its own advantages and disadvantages, we can combine both the techniques together. This paper presents a comparative study of both cryptography and steganography. KEYWORDS: Cryptography, Steganography, Encryptio
integrating together cryptography and Steganography through image processing. In particular, we present a system able to perform Steganography and cryptography at the same time. In this paper, both Cryptography and Steganography methods are used for data security over the network. IRIS i
Cryptography in Java The Java Cryptography Architecture (JCA) is a set of APIs to implement concepts of modern cryptography such as digital signatures, message digests, certificates, encryption, key generation and management, and secure random number generation, etc. Using JCA, developers c
Most of cryptography is currently well grounded in mathematics and it can be debated whether there’sstill an “art” aspectto it. Cryptography. 3 Cryptography can be used at different levels Algorithms: encry
ORGANIZATIONAL BEHAVIOR AND HUMAN PERFORMANCE 18, 131--145 (1977) Hierarchical Level and Leadership Style ARTHUR G. JAGO AND VICTOR H. VROOM School of Organization and Management, Yale University This research investigates the relationship between the hierarchical level of managerial personnel and individual differences in their leadership styles, specifically the degree to which they are .
