Report

Dual System Encryption: Concept, History and Recent works Jongkil Kim Introduction • Strategy of Security Proof • Partitioning Technique • Dual System Encryption – Semi-functionality – Nominally Semi-functionality • Encodings • References Strategy of Security Proof • Claim: Mathematical problem is hard Our Construction is secure under a security model • Proof by contradiction Assume that Our Construction is not secure under a security model Mathematical Problem is not hard Strategy of Security Proof Assume that Our Construction is not secure under a security model Assume there exists an adversary to harm our security model Mathematical Problem is not hard Show that our security model equals to mathematical hard problem. We can break mathematical hard problem using the adversary Strategy of Security Proof • “Harms the security model”? – An adversary having non-negligible advantage to win security games. • Notation and Definition – X: a decryption, Y: a predicate , R: Function Between X and Y • R(X,Y) = 1, then a key can decrypt the ciphertext. Otherwise (R(X,Y) = 0), it does not. • Example, in IBE, R(IDA, IDA) = 1, but R(IDA, IDB) = 0 – Public key encryption system consists of four radnomized algorithms: Setup, KeyGen, Enc, Dec Adaptive security model (CPA Security) Selective Simulator Adversary Y Public key query Setup Phase I Run Setup Public key Private key query (Xi; ∈ [1, 1 ] ) Run KeyGen(MSK,PP, Xi) Private key Challenge query (M0, M1, Y) Challenge B ← {0,1} . . ∉ {X i ; ∈ [1, 1 ]} Run Enc(PP, MB ,Y) Phase II Challenge Cipehrtext Private key query (Xi; ∈ [1 + 1, ]) Run KeyGen(MSK, PP, Xi) Guess Private key Guess? 0 or 1 . . ∉ {X i ; ∈ [1 + 1, ]} Partitioning Technique Key Space Key Space X1 X8 X2 X1 Phase I Phase II X8 X2 X9 X5 … Y X4 Xq X7 X6 X10 X9 Challenge X5 … Y X4 Xq X7 X6 X10 • Partitioning the key space => Only Selective Security if functionality of Public key scheme become complecate. (such as ABE, IPE, Spatial Encryption ,…) Dual System Encryption • Introduced by Waters [Crypto 2009] • It uses semi-functional ciphertext and semifunctional keys which are only used in the security proof. • In Dual System Encryption, the security of an encryption scheme is proved by showing following – Semi-functional ciphertext invariance – Semi-functional key invariance – Semi-functional security Semi-functionality Decrypt? Normal Key Semi-functional Key Normal Ciphertext Yes! Yes! Semi-functional Ciphertext Yes! No… • We must show that two security games are invariant – GameReal: All keys and the challenge ciphertext are normal – GameFinal: All keys and the challenge ciphertext are semifunctional. Additionally, the message are replaced by the random message. – Between both, Game0, Game1, Game2,… Gameq Semi-functional Ciphertext Invariance • Invariance between GameReal and Game0 Adversary Simulator Public key query Setup Public key Private key query (X) Phase I Private key Challenge query (M0, M1, Y) B ← {0,1} Semi-functional Challenge Cipehrtext (MB) Challenge Phase II Private key query (X) Private key Guess Guess? 0 or 1 GameReal ≈ (Invariant) Game0 Invariance of two games Mathematical Problem is hard Assume that two games are indistinguishable Assume there exists an adversary who distinguishes two games We can break mathematical hard problem using the adversary Show that distinguishing two games equals to mathematical hard problem. Semi-functional Ciphertext Invariance • Invariance between Game0 and Gameq Adversary Simulator Phase I Game0 ≈ Private key query (X1) Semi-functional Private key 1 Game1 Private key query (X2) Semi-functional Private key 2 Game2 ≈ … Challenge query (M0, M1, Y) B ← {0,1} Semi-functional Challenge Cipehrtext (MB) Challenge … … Phase II Private key query (Xq) Semi-functional Private key q ≈ Gameq Semi-functional Key Invariance • Semi-functional Key Invariance – Mathematical Induction • We already showed Game0 is invariant with GameReal • We now show Gamek is invariant with Gamek-1 – This is a critical part of the security proof because the relation between kth key and challenge ciphertext is changed. – We must proof the normal key which can decrypt the normal CT is indistinguishable from the semifunction key which cannot. Semi-functional Key Invariance • Invaraiace between Gamek-1 and Gamek Assume there exists an adversary who distinguishes two games Show that distinguishing two games equals to mathematical hard problem. We can break mathematical hard problem using the adversary No limitation for the simulator in the security model! + The simulator can distinguish the kth key by generating valid semifunctional ciphertext for kth key and trying to decrypt it with the kth key. Dual System Encryption • How to prevent this paradox – In Waters’ construction, – If the simulator generate the semi-functional ciphertext to distinguish Tagc must be equal to Tagk. • Tagc = F(IDY) = A·IDY + B • Tagk = F(IDX) = A·IDX + B – But, this is hidden by pair wise independent argument because IDX does not equal to IDY if A and B are initially information theoretically hidden. Nominally Semi-functionality • Introduced by Lewko and Waters[TCC 2010] • Similar with Water’s Construction – If the simulator generates a semi-functional ciphertext for testing whether kth key is semifunctional or normal, semi-functional part is going to be cancel out. • So, kth key is nominally semi-functional because it can decrypt the semi-functional challenge ciphertext. How to hide the Nominality • We also must show that this nominally semi-functional key is invariant with Semi-functional key. • In other words, we must show that the correlation between semi-functional parts in the nominally semifunctional key and the challenge ciphertext is hidden. • By using following – Pair wise independent – n-wise independent – Linearly independent – Information Theoretically Hidden Maybe there are some more but not so many! Hidden Lemma • General Lemma for semi-functional key invariance Assume there exists an adversary who distinguishes Gamek-1 and Gamek We can break mathematical hard problem(SD) using the adversary • But, this is the abstract of two lemmas Nominally Semi-functionality • IBE in composite order – KeyGen(PP, MSK, ID) -> SKID = {K1, K2} • K1:= g1α + r(A ID + B) Z1, K2:= g1 r Z2 – Enc(PP, ID) -> CTID = {C, C1, C2} • C:= M · e(g1, g1)αs, C1:= g1 s, C2:= g1 s(A ID +B) – SFKeyGen(PP, MSK, ID) -> SKID = {K1, K2} • K1:= g1α + r(A ID + B) g2r’a Z1, K2:= g1 r g2 r’ Z2 – SFEnc(PP, ID) -> CTID = {C, C1, C2} • C:= M · e(g1, g1)αs, C1:= g1 s g2 s’, C2:= g1 s(A ID +B) g2 s’ b Hidden Lemmas • Let Gamek’ is the game identical with Gamek-1 , but the kth key is nominally semi functional. Assume there exists an adversary who distinguishes Gamek-1 and Gamek‘ We can break mathematical hard problem using the adversary NSFKeyGen(PP, MSK, ID) -> SKID = {K1, K2} K1:= g1α + r(A ID + B) g2r’(A’ ID + B’) Z1, K2:= g1 r g2 r’ Z2 SFEnc(PP,ID) -> CTID = {C, C1, C2} C:= M · e(g1, g1)αs, C1:= g1 s g2 s’, C2:= g1 s(A ID +B) g2 s’ (A’ ID +B’) Hidden Lemmas • Let Gamek’ is the game identical with Gamek-1 , but the kth key is nominally semi functional. Assume there exists an adversary who distinguishes Gamek‘ and Gamek We can break information theoretically hidden argument using the adversary NSFKeyGen(PP, MSK, ID) -> SKID = {K1, K2} K1:= g1α + r(A ID + B) g2r’(A’ IDa +B’)Z1, K2:= g1 r g2 r’ Z2 SFEnc(PP, ID) -> CTID = {C, C1, C2} C:= M · e(g1, g1)αs, C1:= g1 s g2 s’, C2:= g1 s(A ID +B) g2 s’ (A’ IDb+ B’) Why this is possible? • The semi-functional parts of private key and ciphertext are just twins of their normal parts • But, why is applying information hidden argument possible? Public key and other semifunctional keys does not reveal any information about the semifunctional parts! Semi-functional Security • Invariance between Gameq and GameFinal Adversary Simulator Setup Phase I Public key query Public key Private key query (X) Semi-functionalPrivate key Challenge query (M0, M1, Y) R: RandBmessage ← {0,1} Semi-functional Challenge Cipehrtext (MRB) Challenge Phase II Guess Private key query (X) Semi-functional Private key Guess? 0 or 1 Gameq ≈ (Invariant) GameFinal DSE via Encodings • Pair Encoding [Eurocrypto 2014] and Predicate Encoding [TCC 2014] – Many public key schemes proved by Dual System Encryption share a same proof strategy. – It means it can be formalized! => New direction of the security proof! • We only need our new scheme satisfy following properties – Linearity – Parameter Vanishing – Perfect Master key hiding DSE via Encoding • Linearity – K(α’;x,h,r’) + K(α’’;x,h,r’’) = K(α’ +α’’;x,h,r’+r’’) • Parameter vanishing – K(α;x,h,0) = K(α;x,h’,0) • Perfect master key hiding – Given c(s;y,h), for all α, α’, If R(x,y)=0, K(α;x,h,r) and K(α’;x,h,r) are statistically invariant. Encoding example (IBE) • Construction – Setup(λ) -> N = p1p2p3, PP = { g1A, g1B }, MSK = {α, X3} – KeyGen(PP, MSK, ID) -> SKID = {K1, K2} • K1:= g1α + r(A ID + B) Z1, K2:= g1 r Z2 – Enc(PP, ID) -> CTID = {C, C1, C2} • C:= M · e(g1, g1)αs, C1:= g1 s, C2:= g1 s(A ID +B) – Dec(SKID, CTID) • M = C · e(K2, C2)/e(K1, C1) Encoding example • Encoding – K(α;ID,(A,B),r) = (α + r(A ID + B), r) – c(s;ID,(A,B)) = (s, s(A ID + B)) • Linearity – (α+ r(A ID + B), r) + (α’ + r’(A ID + B), r’) =(α + α’ + (r+r’) (A ID + B), r+r’) • Parameter vanishing – (α+ 0 (A ID + B), 0) + (α + 0(A’ ID + B’), 0) Encoding example • Encoding – K(α;ID,(A,B),r) = (α + r(A ID + B), r) – c(s;ID,(A,B)) = (s, s(A ID + B)) • Perfect Master key hiding – Given (s, s(A ID* + B)) – For ID which does not equal to ID*, A ID + B is randomly distributed (pairwise independent). – Hence, (α + r(A ID + B),r) is statistically invariant with (α’ + r(A ID + B),r) to the adversary References • [Eurocrypto 2014] N. Attrapadung. Dual system encryption via doubly selective security: Framework, fully secure functional encryption for regular languages, and more. In P. Q. Nguyen and E. Oswald, editors, EUROCRYPT, volume 8441 of Lecture Notes in Computer Science, pages 557{577. Springer, 2014. • [Crypto 2009] B. Waters. Dual system encryption: Realizing fully secure ibe and hibe under simple assumptions. In S. Halevi, editor, CRYPTO, volume 5677 of Lecture Notes in Computer Science, pages 619{636. Springer, 2009. • [TCC 2014] H. Wee. Dual system encryption via predicate encodings. In Y. Lindell, editor, TCC, volume 8349 of Lecture Notes in Computer Science, pages 616{637. Springer, 2014. • [TCC 2010] A. Lewko and B. Waters. New techniques for dual system encryption and fully secure hibe with short ciphertexts. In TCC, 2010.